Sorting by reversals and the theory of 4-regular graphs
Copyright policy )Sorting by reversals and the theory of 4-regular graphs
We show that the theory of sorting by reversals fits into the well-established theory of circuit partitions of 4-regular multigraphs (which also involves the combinatorial structures of circle graphs and delta-matroids). In this way, we expose strong connections between the two theories that have not been fully appreciated before. We also discuss a generalization of sorting by reversals involving the double-cut-and-join (DCJ) operation. Finally, we also show that the theory of sorting by reversals is closely related to that of gene assembly in ciliates.
25 pages, 16 figures
- Hasselt University Belgium
FOS: Computer and information sciences, gene assembly in ciliates, Discrete Mathematics (cs.DM), sorting by reversals, genome rearrangements, Applications of graph theory, 4-regular graphs, Sorting by reversals; Sorting by DCJ operations; Genome rearrangements; 4-Regular graphs; Local complementation; Gene assembly in ciliates, sorting by DCJ operations, Problems related to evolution, FOS: Mathematics, Mathematics - Combinatorics, local complementation, Combinatorics (math.CO), Genetics and epigenetics, Computer Science - Discrete Mathematics
FOS: Computer and information sciences, gene assembly in ciliates, Discrete Mathematics (cs.DM), sorting by reversals, genome rearrangements, Applications of graph theory, 4-regular graphs, Sorting by reversals; Sorting by DCJ operations; Genome rearrangements; 4-Regular graphs; Local complementation; Gene assembly in ciliates, sorting by DCJ operations, Problems related to evolution, FOS: Mathematics, Mathematics - Combinatorics, local complementation, Combinatorics (math.CO), Genetics and epigenetics, Computer Science - Discrete Mathematics
selected citations These citations are derived from selected sources.This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).0 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Average influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Average impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Average
Citations provided by BIP!Popularity provided by BIP!