Sorting by Reversals and the Theory of 4-Regular Graphs
arXiv:1701.07463
Abstract
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.
arXiv comment25 pages, 16 figures
References in corpus (6)
- The Group Structure of Pivot and Loop Complementation on Graphs and Set Systems
- Matroids, Delta-matroids and Embedded Graphs
- Reducibility of Gene Patterns in Ciliates using the Breakpoint Graph
- Maximal Pivots on Graphs with an Application to Gene Assembly
- Nullity Invariance for Pivot and the Interlace Polynomial
- Context Directed Reversals and the Ciliate Decryptome