Sorting by Reversals and the Theory of 4-Regular Graphs
Robert Brijder





calc,petri
snakes
patterns


external




plain
abbrv




theoremTheorem
lemma[theorem]Lemma
proposition[theorem]Proposition
corollary[theorem]Corollary
definition[theorem]Definition
example[theorem]Example
remark[theorem]Remark
ProofProof
proof
Example











Hasselt University, Belgium
[myfootnote]Postdoctoral fellow of the Research Foundation – Flanders (FWO).
robert.brijder@uhasselt.be



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.



sorting by reversals sorting by DCJ operations genome rearrangements 4-regular graphs local complementation 
gene assembly in ciliates









§ INTRODUCTION
 
Edit distance measures for genomes can be used to approximate evolutionary distance between their corresponding species. A number of genome transformations have been used to define edit distance measures. In this paper we consider the well-studied chromosome transformation called reversal, which is an inversion of part of a chromosome <cit.>. If two given chromosomes can be transformed into each other through reversals, then the difference between these two chromosomes can be represented by a permutation, where the identity permutation corresponds to equality. As a result, transforming one chromosome into the other using reversals is called sorting by reversals. The reversal distance is the least number of reversals needed to accomplish this transformation (i.e., to sort the permutation by reversals). In <cit.> a formula is given for the reversal distance, leading to an efficient algorithm to compute reversal distance. The proof of that formula uses a notion called the breakpoint graph. Subsequent streamlining of this proof led to the introduction of additional notions <cit.> such as the overlap graph and a corresponding graph operation. A reversal can be seen as a special case of a double-cut-and-join (DCJ) operation that can operate either within a chromosome or between chromosomes. Similar as for reversals, one can define a notion of DCJ distance, and a formula for DCJ distance is given in <cit.>.

The theory of circuit partitions of 4-regular multigraphs was initiated in <cit.> and is currently well-developed with extensions and generalizations naturally leading into the domains of, e.g., linear algebra and matroid theory. In this paper we show that this theory can be used to study sorting by reversals, and more generally sorting by DCJ operations. Moreover, we show how various aspects of the theory of circuit partitions of 4-regular multigraphs relate to the topic of sorting by reversals. In particular, we show that the notion of an overlap graph and its corresponding graph operation from the context of sorting by reversals <cit.> correspond to circle graphs and the (looped) local complementation operation, respectively, of the theory of circuit partitions of 4-regular multigraphs. This leads to a reformulation of the Hannenhalli-Pevzner theorem <cit.> to delta-matroids. We remark however that the theory of circuit partitions of 4-regular multigraphs is too broad to fully cover here, and so various references are provided in the paper for more information.



It has been shown that various other research topics can also be fit into the theory of circuit partitions of 4-regular multigraphs: examples include the theory of ribbon graphs (or embedded graphs) <cit.> and the theory of gene assembly in ciliates <cit.>. As such all these research topics arising from different contexts turn out to be strongly linked, and results from one research topic can often be carried over to another. Indeed, it is not surprising that the Hannenhalli-Pevzner theorem has been independently discovered in the context of gene assembly in ciliates <cit.>.

This paper is organized as follows. In Section <ref> we recall sorting by reversals and in Section <ref> we associate a 4-regular multigraph and a pair of circuit partitions to a pair of chromosomes (where one is obtainable from the other by reversals). This leads to a reformulation of a known inequality of the reversal distance in terms of 4-regular multigraphs. In Section <ref> we associate a circle graph to the two circuit partitions and we show that the adjacency matrix representation of this circle graph reveals essential information regarding the reversal distance. We recall local complementation in Section <ref> and the Hannenhalli-Pevzner theorem in Section <ref>, and reformulate the Hannenhalli-Pevzner theorem in terms of delta-matroids in Section <ref>. Before discussing delta-matroids, we also recall sorting by DCJ operations in Section <ref>. We discuss the close connection of sorting by reversals and gene assembly in ciliates in Section <ref>. Finally, a discussion is given in Section <ref>.



§ SORTING BY REVERSALS
 

In this section we briefly and informally recall notions concerning sorting by reversals. See, e.g., the text books <cit.> for a more formal and extensive treatment.







During the evolution of species, various types of modifications of the genome may occur. One such modification is the inversion (i.e., rotation by 180 degrees) of part of a chromosome, called a reversal. In Section <ref>, we recall that this inversion is the result of a so-called double-cut-and-join operation. The reversal distance between two given chromosomes is the minimal number of reversals needed to transform one into the other, and it is a measure of the evolutionary distance between the two species. Figure <ref> shows two toy chromosomes which have seven segments in common, but their relative positions and orientations differ (by, e.g., -5 we mean segment 5 in inverted orientation, i.e., rotated by 180 degrees). Figure <ref> shows that the reversal distance between the chromosomes of Figure <ref> is at most four.


We can concisely describe the chromosomes of Figure <ref> by the sequences (1, -6, 7, 4, -2, -5, 3) and (1, 2, 3, 4, 5, 6, 7). These sequences are called signed permutations in the literature, and we will adopt this convention here (although we won't treat them as permutations in this paper). A signed permutation of the form (1, 2, ⋯, n) is called the identity permutation. The reversal distance of a single signed permutation π, denoted by d_r(π), is the minimal number of reversals needed to transform π into the identity permutation. Thus, for π = (1, -6, 7, 4, -2, -5, 3) of Figure <ref>, we have d_r(π) ≤ 4 by Figure <ref>.

Viewing the chromosome of species B of Figure <ref> as the “sorted” chromosome, the transformation using reversals of the chromosome of species A to the chromosome of species B is called sorting by reversals.



For any signed permutation π = (π_1, π_2, ⋯, π_n), the signed permutation π = (-π_n, -π_n-1, ⋯, -π_1) represents the same chromosome (just considered 180 degrees rotated). The reversal distance of π and π may however differ (this difference is, of course, at most one because π can be turned into π using one “full” reversal). Therefore, one could argue that a better notion of the reversal distance of π would be the minimum value of the reversal distances of both π and π. Equivalently, one could view both (1, 2, ⋯, n) and (-n, -(n-1), ⋯, -1) as identity permutations. We revisit this issue in Sections <ref> and <ref>.





§ FOUR-REGULAR MULTIGRAPHS
 

In this paper, graphs are allowed to have loops but not multiple edges, and multigraphs are allowed to have both loops and multiple edges. We denote the sets of vertices and edges of a (multi)graph G by V(G) and E(G), respectively. For graphs, each edge e ∈ E(G) is either of the form {v} (i.e., v is a looped vertex) or of the form {v_1,v_2} (i.e., there is an edge between v_1 and v_2). A vertex v is said to be isolated if no edge is incident to it (in particular, v is not looped). A 4-regular multigraph is a multigraph where each vertex has degree 4, a loop counting as two.

A standard tool for the calculation of the reversal distance is the so-called breakpoint graph of a signed permutation. In this section we instead assign a 4-regular multigraph and two of its circuit partitions to a signed permutation. The main reason for considering this graph instead of the breakpoint graph is that in this way we can use the vast amount of literature concerning the theory of circuit partitions of 4-regular multigraphs, which began with the seminal paper of Kotzig <cit.>, and extended, e.g., in <cit.>.

We also note that a drawback of using the breakpoint graph is that the identity of the vertices is important, while the theory of circuit partitions of 4-regular multigraphs is independent of the identity of the vertices.



























We now describe the construction of the 4-regular multigraph (along with two circuit partitions). As usual, the boundaries between adjacent segments of (the chromosomal depiction of) a signed permutation π are called breakpoints. Because reversals can also be applied on endpoints of a chromosome, we treat the endpoints of a signed permutation as breakpoints as well. We do this by circularizing the signed permutation, see Figure <ref>. Note, however, that the location of the endpoints is important. Indeed, e.g., the signed permutation (1, 2, ⋯, n), with n ≥ 2, has a different reversal distance than any of its proper conjugations (i.e., the signed permutations (i, i+1, ⋯, n, 1, 2, ⋯, i-1) for i ∈{2,…,n}). Therefore, we have anchored the two endpoints to a new segment, which is denoted by $. This corresponds to the usual procedure of framing the signed permutation in the theory of sorting by reversals, see, e.g., <cit.>. The next step, which we call here the expand step, is to insert an intermediate segment I_i between each two adjacent segments, see again Figure <ref>.







Next, we represent the circularized and expanded signed permutation by a digraph D_π. In D_π, each breakpoint is represented by a vertex and each segment is represented by an arrow. The arrow is labeled by the segment x it represents and goes from the left-hand breakpoint of x to the right-hand breakpoint of x, see Figure <ref>. Moreover, the boundaries/breakpoints of the original segments i and i+1 that coincide after the sorting procedure are given a common vertex label v_i. For example, the right-hand side breakpoint of segment 3 and the left-hand side breakpoint of segment 4 are given a common vertex label v_3, see again Figure <ref>. Notice that the orientation is important here: the right-hand side breakpoints of segment 1 and the right-hand side breakpoint of segment -2 are given a common vertex label because segment -2 is segment 2 in inverted orientation (i.e., rotated by 180 degrees). Since segment $ represents the endpoints, for the arrow corresponding to $, the head vertex is labeled by v_0 and the tail vertex is labeled by v_n.



From the digraph D_π of Figure <ref>, we construct a 4-regular multigraph, denoted by G_π, by turning each arrow into an undirected edge, removing the signs from the edge labels, and finally merging each two vertices with the same label, see Figure <ref>.

Let G be a multigraph and let l be the number of connected components of G. A (unoriented) circuit of G is a closed walk, without distinguished orientation or starting vertex, allowing repetitions of vertices but not of edges. A circuit partition of G is a set P of circuits of G such that each edge of G is in exactly one circuit of P. Note that |P| ≥ l. If |P| = l, then we say that P is an Euler system of G. Note that an Euler system contains an Eulerian circuit (i.e., a circuit visiting each edge exactly once) for each connected component of G. In particular, if G is connected, then an Euler system is a singleton containing an Eulerian circuit of G.





As illustrated in Figure <ref>, the circularized and expanded signed permutation of Figure <ref> belongs to a particular circuit partition P_A of the 4-regular multigraph G_π of Figure <ref> (this can also be verified by comparing Figure <ref> with Figure <ref>). In this way, P_A is the circuit partition belonging to the chromosome of species A. Notice that P_A is an Euler system, in fact, since G_π is connected for every signed permutation π, P_A contains an Eulerian circuit of G_π. Another circuit partition P_B is illustrated in Figure <ref>. It is the unique circuit partition that includes the circuit C = (1,2, ⋯,7,$). As such, P_B is the circuit partition belonging to the chromosome of species B. Notice that, besides C, P_B contains four other circuits in this example. Each of these four circuits consists of intermediate segments (recall that these are the segments of the form I_i for some i).

We remark that Figures <ref> and <ref> (corresponding to P_A and P_B, respectively) can be obtained from G_π by “splitting” each vertex in an appropriate way. This splitting is considered in <cit.> in the context of gene assembly in ciliates (we recall gene assembly in ciliates in Section <ref>).

While we do not recall the notion of a cycles of a signed permutation (see, e.g., <cit.>), we mention that it is easy to verify that these cycles correspond one-to-one to circuits of intermediate segments of the circuit partition P_B.

By using 4-regular multigraphs, we have given these cycles a more “physical” interpretation, cf. Figure <ref>.

Let c(π) be the number of cycles of a signed permutation π. The following result is well known (in fact, this result has been extended into an equality in <cit.>).
 
Let π be a signed permutation with n elements. Then d_r(π) ≥ n+1 - c(π).

The proof idea of Theorem <ref> is to show that (1) if π is the identity permutation, then c(π)=n+1 and (2) if π' is obtained from π by applying a single reversal, then c(π') - c(π) ∈{-1,0,1}.

We remark that the inequality of Theorem <ref> usually takes the form d_r(π) ≥ n' - c(π), where n' is the number of segments of the framed/anchored signed permutation and is natural when segment $ is instead denoted by n' = n+1.

For our running example we see by Figure <ref> that c(π)=4. Thus d_r(π) ≥ 7+1-4=4. We have seen in Section <ref>, and in particular Figure <ref>, that d_r(π) ≤ 4. Consequently, d_r(π)=4.



Notice that a circuit partition takes, for each vertex of the 4-regular multigraph, one of three possible routes, see Figure <ref>. Since care must be taken in the case of loops, the four h_i's are not edges but actually “half-edges”, where two half-edges form an edge. If circuit partitions P_1 and P_2 take a different route at each vertex of G, then we say that P_1 and P_2 are supplementary. Notice that P_A and P_B are supplementary circuit partitions.

For a given circuit partition P and vertex v of G, let P' and P” be the circuit partitions obtained from P by changing the route of P at vertex v. It is well known that the cardinalities of two of {P,P',P”} are equal, to say k, and the third is of cardinality k+1.


In terms of 4-regular multigraphs, the issue discussed in Remark <ref> translates to the question of whether the anchor should be $ or -$ (in other words, $ in inverted orientation). We assume the former, but the latter anchor is equally valid and may sometimes obtain a reversal distance that is one smaller. We revisit this issue in Section <ref>.




§ CIRCLE GRAPHS
 





To study the effect of sequences of reversals, we turn to circle graphs. Let us fix two supplementary circuit partitions P_1 and P_2 of a 4-regular multigraph G, where P_1 is an Euler system.

A vertex v of G is called oriented for P_1 with respect to P_2 if the circuit partition P' obtained from P_1 by changing the route of P_1 at v to coincide with the route of P_2 at v, is an Euler system. We say that vertex v of G_π is oriented for a signed permutation π if v is oriented for P_A with respect to P_B. Thus {v_1,v_2,v_4,v_6} is the set of oriented vertices of our running example.



To construct the circle graph, we assume first, for convenience, that G is connected, i.e., P_1 contains a single Eulerian circuit C. We draw C as a circle and connect each two vertices with the same label by a chord to obtain a chord diagram. See Figure <ref> for the chord diagram of the Eulerian circuit of Figure <ref>. We construct a (looped) circle graph H for G with respect to P_1 and P_2 as follows. The set V(H) = V(G) and two distinct vertices of H are adjacent when the corresponding two chords intersect in the chord diagram. Finally, a loop is added for each vertex that is oriented for P_1 with respect to P_2. In the general case where G is not necessarily connected, the circle graph for G is the union of the circle graphs of each connected component of G. The circle graph H_π for signed permutation π is the circle graph of G_π with respect to P_A and P_B. The circle graph for our running example is depicted in Figure <ref>.

 
We remark that a circle graph is called an “overlap graph” in the literature of sorting by reversals. However, we use here the term circle graph because circle graph is the usual name for this notion in mathematics. Also, the vertices of an overlap graph in the literature on sorting by reversals are often decorated by white or black labels instead of loops (black labels correspond to loops). The rest of this section shows why using loops instead of vertex colors is very useful when going to other combinatorial structures and matrices.


We now recall the well-known notion of an adjacency matrix of a graph. First, the rows and columns of the matrices we consider in this paper are not ordered, but are instead indexed by finite sets X and Y, respectively. We call such matrices X × Y-matrices. Note that the usual notions of rank and nullity of such a matrix A are defined — they are denoted by r(A) and n(A), respectively. The adjacency matrix of a graph G, denoted by A(G), is the V(G) × V(G)-matrix over the binary field GF(2) where for v,v' ∈ V(G), the entry indexed by (v,v') is 1 if and only if v and v' are adjacent (a vertex v is considered adjacent to itself precisely when v has a loop).

The adjacency matrix A(H_π) of the circle graph H_π of Figure <ref> is as follows:

    A(H_π) =
        v_0     v_1     v_2     v_3     v_4     v_5     v_6     v_7 
    v_0       0       0       0       0       0       0       0       0 
    v_1       0       1       1       1       1       1       0       1 
    v_2       0       1       1       0       1       1       0       0 
    v_3       0       1       0       0       0       1       0       0 
    v_4       0       1       1       0       1       1       0       0 
    v_5       0       1       1       1       1       0       1       1 
    v_6       0       0       0       0       0       1       1       0 
    v_7       0       1       0       0       0       1       0       0 .


We now recall the following result from <cit.>.

Let G be a 4-regular multigraph with l connected components and let P_1 and P_2 be supplementary circuit partitions of G with P_1 an Euler system. Let H be the circle graph for G with respect to P_1 and P_2. Then n(A(H))=|P_2|-c.


We have the following corollary to Theorem <ref>, which considers the case where H is of the form H_π.
 
Let π be a signed permutation. Then n(A(H_π)) = c(π).


By Theorem <ref>, n(A(H_π)) = |P_B|-|P_A| = |P_B|-1 since P_A contains an Eulerian circuit of G_π. Recall from Section <ref> that c(π) is the number of circuits of P_B excluding the circuit (1,…,n,$). Thus c(π) = |P_B|-1.

Corollary <ref> illustrates the usefulness of using loops instead of vertex colors for circle graphs (cf. Remark <ref>).

For our running example, we have that c(π) = |P_B|-1 = 5-1 = 4, so n(A(H_π)) = c(π) =4.

Using Corollary <ref>, we can translate the inequality of Theorem <ref> as follows.
 
Let π be a signed permutation with n elements. Then d_r(π) ≥ r(A(H_π)).


By Theorem <ref> and Corollary <ref>, d_r(π) ≥ n+1 - c(π) = n+1 - n(A(H_π)). The result follows by observing that |V(H_π)| = n+1.


 
Let π be a signed permutation. Then π is the identity permutation if and only if r(A(H_π)) = 0.


Let π have n elements. Note that π is the identity permutation if and only if each intermediate segment forms a circuit of length 1 if and only if c(π) = n+1. By Corollary <ref>, this is equivalent to n(A(H_π)) = n+1 and therefore equivalent to r(A(H_π)) = 0.


Note that r(A(H))=0 simply means that H contains no edges (i.e., consists of only isolated vertices).



§ LOCAL COMPLEMENTATION
 

In order to study the effect of reversals on circle graphs, we recall the following graph notions. For a graph H and vertex v, the neighborhood of v in H, denoted by N_H(v), is { v' ∈ V(G) |{v,v'}∈ E(H), v' ≠ v}.

Let H be a graph and v a looped vertex of H. The local complement of H at v, denoted by H*v, is the graph obtained from H by complementing the subgraph induced by N_H(v).

In other words, for all p ⊆ V(H) = V(H*v) with |p| ∈{1,2}, we have p ∈ E(H*v) if and only if either (1) p ∉ E(H) and p ⊆ N_H(v) or (2) p ∈ E(H) and p ⊈N_H(v).

Moreover, we denote by H*_c v the graph obtained from H*v by removing all edges incident to v (including the loop on v). Thus v is an isolated vertex of H*_c v. Equivalently, H *_c v complements the subgraph induced by the “closed neighborhood” { v' ∈ V(H) |{v,v'}∈ E(H)}. Finally, we denote by H|v the graph obtained from H*_c v by removing the isolated vertex v. Note that each of these three operations (* v, *_c v and |v) are only allowed on looped vertices v; we say that such an operation is applicable to H if v is a looped vertex of H.

The interest of local complement for the topic of sorting by reversals is that it corresponds to applying some particular type of reversal <cit.>.

Let π be a signed permutation and let π' be the signed permutation obtained from π by applying a reversal on the breakpoints corresponding to an oriented vertex v. Then H_π' = H_π *_c v.


It turns out that local complementation has interesting effects on the underlying adjacency matrix (see, e.g., <cit.>).

Let H be a graph and v a looped vertex of H. Then n(A(H|v)) = n(A(H)). In other words, r(A(H *_c v)) = r(A(H))-1.

While Lemma <ref> can be proved directly, another way is to (1) observe that A(H|v) is obtained from A(H) by applying the Schur complementation matrix operation <cit.> on the submatrix induced by {v} and (2) recall from, e.g., <cit.> that Schur complementation preserves nullity. We remark that while A(H|v) is obtained from A(H) by applying Schur complementation, A(H*v) is obtained from A(H) by applying the principal pivot transform matrix operation, which is a partial matrix inversion operation, see, e.g., <cit.>.

Let H be a graph and let σ = (v_1,…,v_k) be a sequence of mutually distinct vertices of H.

A sequence φ = *_c v_1 *_c v_2 ⋯ *_c v_k of *_c operations that is applicable to H (associativity of *_c is from left to right) is called an lc-sequence for H. We say that an lc-sequence is full if H φ contains only isolated vertices.

Since (1) by Lemma <ref>, *_c decreases rank by one and (2) a graph H contains only isolated vertices if and only if r(A(H))=0, we directly recover the following property observed in <cit.> (see also <cit.>).

Let H be a graph and let φ be an lc-sequence of length k for H. Then φ is full if and only if k = r(A(H)).

Note that if a full lc-sequence φ exists for H_π with π a signed permutation, then by
Theorem <ref> and Lemma <ref> we have that d_r(π) = r(A(H_π)). So, each full lc-sequence corresponds to an optimal sorting of π.



§ HANNENHALLI-PEVZNER THEOREM
 

We now recall the so-called Hannenhalli-Pevzner theorem which gives a precise criterion on arbitrary graphs H for the existence of a full lc-sequence. This theorem has been shown in <cit.> in terms of signed permutations π, but has later been extended to arbitrary graphs H (instead of essentially restricting to circle graphs H_π). Also, this result was shown independently in <cit.> in the context of gene assembly in ciliates (we recall this topic in Section <ref>). We give here another proof of this result, closely following the reasoning of <cit.>.

Let L be the set of looped vertices of a graph H. For all v ∈ V(H), we denote N^l_H(v) = N_H(v) ∩ L and N^ul_H(v) = N_H(v) ∖ L. Also, H is said to be loopless if L=∅.

 
Let H be a connected graph and let v ∈ V(H) be looped. If H' is a loopless connected component of H|v, then both (1) V(H') ∩ N^l_H(v) ≠∅ and (2) N^ul_H(v) ⊆ N^ul_H(w) and N^l_H(w) ⊆ N^l_H(v) for all w ∈ V(H') ∩ N^l_H(v).


Let H' be a loopless connected component of H|v. Since local complementation changes only edges between vertices of N_H(v), V(H') ∩ N_H(v) ≠∅. Because local complementation complements the loop status of each vertex of N_H(v) and H' is loopless, V(H') ∩ N^l_H(v) = V(H') ∩ N_H(v) ≠∅.

Let w ∈ V(H') ∩ N^l_H(v).

Firstly, let x ∈ N^ul_H(v). Then x is looped in H|v. Since H' is loopless, {x,w}∉ E(H|v). Thus {x,w}∈ E(H) (because x,w ∈ N_H(v)). Consequently, x ∈ N^ul_H(w). Thus N^ul_H(v) ⊆ N^ul_H(w).

Secondly, let x ∈ N^l_H(w). If x ∉ N^l_H(v), then x ∈ N^l_H|v(w) which contradicts the fact that w belongs to a loopless connected component of H|v. Thus N^l_H(w) ⊆ N^l_H(v).




For a vertex v of H, define s(v) = |N^ul_H(v)| - |N^l_H(v)|.
Let (H) be the set of looped vertices v of H such that s(w) ≤ s(v) for all w ∈ N^l_H(v). Note that for any graph H with looped vertices, (H) is nonempty since it contains all looped vertices that are (globally) maximal with respect to function s.




Let H be a connected graph and v ∈(H). Then each loopless connected component of H|v consists of only an isolated vertex.


Let H' be a loopless connected component of H|v. Since v ∈(H), we have by Lemma <ref>, N^ul_H(v) = N^ul_H(w) and N^l_H(w) = N^l_H(v) for some w ∈ V(H'). Since v and w are moreover looped and adjacent, we have that w, and therefore H', is an isolated vertex of H|v.


By iteration of Lemma <ref>, we obtain the following.

Let H be a graph. Then there is a full lc-sequence for H if and only if each loopless connected component of H consists of only an isolated vertex.



Let π be a signed permutation. If each connected component of H_π has at least one looped vertex or consists of only an isolated vertex, then d_r(π) = n+1 - c(π).




§ DCJ OPERATIONS AND MULTIPLE CHROMOSOMES
 













A reversal is a special case of a double-cut-and-join (DCJ for short) operation, also called recombination in other contexts. A DCJ operation is depicted in Figure <ref>. A DCJ operation consists of three stages: first two distinct breakpoints align, then both breakpoints are cut, and finally the ends are glued back together as depicted in Figure <ref>. Since we consider endpoints to be breakpoints as well, any of w, x, y and z may be nonexistent. From the alignment of Figure <ref> one observes that a reversal is a special case of a DCJ operation. DCJ operations are allowed to be intermolecular as well, and so sorting by DCJ operations may involve multiple chromosomes (for example a whole genome) and each chromosome may be linear or circular. The DCJ distance of two genomes g_A and g_B, denoted by d_DCJ(g_A,g_B), is the minimal number of DCJ operations needed to transform one genome into the other. A toy example of two genomes g_A and g_B of species A and B, respectively, consisting of both linear and circular chromosomes is given in Figure <ref>.



0.2cm
0.1cm
0.05cm
3


2






If g_A and g_B contain only circular chromosomes, then the method of Section <ref> to construct a 4-regular multigraph applies essentially unchanged — the only difference is that the circularization step is not done (and so no anchor $ is introduced) because the chromosomes are circular already. Thus, we directly apply the expand step to all chromosomes of g_A and then construct the 4-regular multigraph G as before.

It is now a special case of <cit.> that d_DCJ(g_A,g_B) = n-c, where n is the number of vertices of G (i.e., n is the number of segments in g_A and g_B) and c is the number of circuits containing intermediate segments of the circuit partition P_B belonging to g_B. The result in <cit.> is not stated in terminology of circuit partitions of a 4-regular multigraph, but instead in terms of a graph called an “adjacency graph”[The notion of adjacency graph is not to be confused with the different notion of adjacency matrix as recalled earlier in this paper.]. More precisely, in <cit.> c is defined as the number of cycles in the adjacency graph, and it can be readily verified that cycles in the adjacency graph correspond one-to-one to circuits of P_B containing intermediate segments.


While the construction of a 4-regular multigraph as outlined in Section <ref> works when both genomes have only circular chromosomes, there are issues for genomes containing linear chromosomes such as in Figure <ref>. Indeed, the circularization of the linear chromosomes of g_B in Figure <ref> leads to two anchors $_1 and $_2 which somehow need to be reconciled with the single anchor $ in the linear chromosome of g_A. Also, the issue discussed in Remarks <ref> and <ref> (which concerns the issue of whether to use $ or -$ as the anchor) is exasperated when there are several linear chromosomes. We leave it as an open problem to resolve this issue of the absence of a canonical 4-regular multigraph for two genomes. We mention that <cit.> is able to calculate the DCJ distance in this general setting (i.e., with linear chromosomes). The formula takes the form d_DCJ(g_A,g_B) = n-(c+i/2), where i is the number of connected components of the adjacency graph that are odd-length paths. Very roughly, one way to explain this formula in terms of 4-regular multigraphs is that each odd-length path corresponds to a side of a linear chromosome and an anchor (which increases n by one) can be introduced in such a way that both sides of a linear chromosome end up in different circuits (which increases c by two). So, the net effect of two sides of a linear chromosome is one, hence the contribution of i/2.

Recall that the construction of a circle graph from Section <ref> requires two supplementary circuit partitions P_A and P_B of a 4-regular multigraph G where P_A is an Euler system. While in the theory of sorting by reversals P_A is always an Euler system (in fact, P_A contains an Eulerian circuit of G_π), the circuit partition P_A belonging to a genome g_A is not necessarily a Euler system. In Section <ref> we recall the notion of a delta-matroid which can function as a substitute for circle graphs in scenarios where circle graphs do not exist. In fact, as we will see, delta-matroids are useful even in scenarios where circle graphs do exist, such as in the theory of sorting by reversals.



§ DELTA-MATROIDS
 
It was casually remarked in the discussion of <cit.> that the Hannenhalli-Pevzner theorem might be generalizable to the more general setting of delta-matroids, which are combinatorial structures defined by Bouchet <cit.>. Indeed, we recall now how delta-matroids can be constructed from circuit partitions in 4-regular multigraphs and from circle graphs. In this way, various results concerning the theory of sorting by reversals can be viewed in this more general setting.

A set system D = (V,S) is an ordered pair, where V is a finite set, called the ground set, and S a set of subsets of V. For set systems D_1 = (V_1,S_1) and D_2 = (V_2,S_2) with disjoint ground sets, we define the direct sum of D_1 and D_2, denoted by D_1 ⊕ D_2, as the set system (V_1 ∪ V_2, { X_1 ∪ X_2 | X_1 ∈ S_1, X_2 ∈ S_2 }). In this case we say that D_1 and D_2 are summands of D. A set system D is called connected if it is not the direct sum of two set systems with nonempty ground sets. Also, D = (V,S) is called even if the cardinalities of all sets in S are of equal parity. Let us denote symmetric difference by . A delta-matroid D = (V,S) is a set system where S is nonempty and, moreover, for all X,Y ∈ S and x ∈ X  Y, there is an y ∈ X  Y (possibly equal to x) with X {x,y}∈ S <cit.>.

Let G be a 4-regular multigraph and let P_1 and P_2 be two supplementary circuit partitions of G. Denote by 𝒟_G(P_1,P_2) the set system (V(G),S), where for X ⊆ V(G) we have X ∈ S if and only if the circuit partition P obtained from P_1 by changing, for each v ∈ X, the route of P_1 at v to coincide with the route of P_2 at v, is an Euler system.

The following result is stated in <cit.> (see also <cit.>).


Let G be a 4-regular multigraph and let P_1 and P_2 be two supplementary circuit partitions of G. Then 𝒟_G(P_1,P_2) is a delta-matroid.


 
Let G_π be from Figure <ref>, P_A = {C} be from Figure <ref> and P_B be from Figure <ref>. Then 𝒟_G_π(P_A,P_B) = (V(G),S), where

    S    =   {∅, {v_1}, {v_2}, {v_4}, {v_6}, {v_1,v_3}, {v_1,v_5}, {v_1,v_6}, {v_1,v_7}, {v_2,v_4}, {v_2,v_5},
            {v_2,v_6}, {v_3,v_5}, {v_4,v_5}, {v_4,v_6}, {v_5,v_6}, {v_5,v_7}, {v_1,v_2,v_3}, …}.




For a graph H and X ⊆ V(G), we denote by H[X] the subgraph of H induced by X (i.e., all vertices outside X are removed including their incident edges). Also, denote by 𝒟_H the set system (V(H),S), where for X ⊆ V(H), X ∈ S if and only if the matrix A(H[X]) is invertible. As usual, the empty matrix is invertible by convention.


Let H be a graph. Then 𝒟_H is a delta-matroid.

The delta-matroids of the form 𝒟_H for some graph H are called binary normal delta-matroids <cit.>.

We now recall the close connection between delta-matroids of circle graphs and of circuit partitions of 4-regular multigraphs.
 
Let H be the circle graph of a 4-regular multigraph G with respect to the supplementary circuit partitions P_1 and P_2 with P_1 an Euler system. Then 𝒟_H = 𝒟_G(P_1,P_2).


Note that G_π, P_A and P_B as used in Example <ref> are also used to construct the circle graph H_π of Figure <ref>. So, 𝒟_G_π(P_A,P_B) of Example <ref> is equal to 𝒟_H_π.

Notice, e.g., that the looped vertices of H precisely correspond to the singletons in 𝒟_G(P_1,P_2). Indeed, the adjacency matrix of a subgraph containing a single vertex v is invertible precisely when v is looped.

By Theorem <ref>, 𝒟_G(P_1,P_2) corresponds to a circle graph if P_1 an Euler system. Recall that in the case of the sorting of genomes by DCJ operations (see Section <ref>), the usual construction of a circle graph does not work since the input does not necessarily correspond to an Euler system. However, we can construct 𝒟_G(P_1,P_2) and so delta-matroids allow one to work with combinatorial structures similar to circle graphs in cases (such as in Section <ref>) where a corresponding circle graph does not seem to exist. This is one important reason for considering delta-matroids. Another reason is that delta-matroids are often more easy to work with than circle graphs (even in the cases where circle graphs exist) since the operation of local complementation (on looped vertices) is much more simple in terms of delta-matroids. We will recall this now.

For a set system D = (V,S) and X ⊆ V, define the twist of D on X, denote by D*X, as the set system (V,S') with S' = { X  Y | Y ∈ S}. Notice that (D*X)*X = D. Also, it is easy to verify that if D is a delta-matroid, then so is D*X.



Let H be a graph and v ∈ V(H) be looped. Then 𝒟_H*v = 𝒟_H*{v}.

By Theorem <ref>, 𝒟_H *_c v is obtained from 𝒟_H*{v} by removing all sets containing v.

We can translate the notion of a full lc-sequence for graphs to the realm of delta-matroids. Let D = (V,S) be a set system. A sequence σ = (v_1,v_2,…,v_k) of mutually distinct elements of V is a lc-sequence for D if for all i ∈{0,…,k}, {v_1,…,v_i}∈ S. Note that, in particular, ∅, {v_1,…,v_k}∈ S. An lc-sequence σ = (v_1,v_2,…,v_k) for D is said to be full if {v_1,…,v_k}∈max(S), where max(S) is the set of maximal elements of S with respect to inclusion.


 
Let H be a graph. Then σ = (v_1,v_2,…,v_k) is an lc-sequence for 𝒟_H if and only if φ = *_c v_1 *_c v_2⋯ *_c v_k is an lc-sequence for H. Moreover, in this case, σ is full if and only if φ is full.


We prove the first statement by induction on k. If k=0, then σ and φ are empty sequences and so the result holds trivially. Assume that k > 0 and that the result holds for k' = k-1.

First, let σ be an lc-sequence for 𝒟_H. In particular, σ' = (v_1,v_2,…,v_k-1) is an lc-sequence for 𝒟_H. By the induction hypothesis, φ' = *_c v_1 *_c v_2 ⋯ *_c v_k-1 is an lc-sequence for H. Assume to the contrary that φ is not an lc-sequence. Then v_k is not a looped vertex of H φ'. Thus {v_k} is not a set of 𝒟_H φ'. By the sentence below Theorem <ref>, {v_k} is not a set of 𝒟_H*{v_1,v_2,…,v_k-1}. In other words, {v_1,v_2,…,v_k} is not a set of 𝒟_H — a contradiction.

Second, let φ be an lc-sequence for H. In particular, φ' = *_c v_1 *_c v_2⋯ *_c v_k-1 is an lc-sequence for H. By the induction hypothesis, σ' = (v_1,v_2,…,v_k-1) is an lc-sequence for 𝒟_H. It suffices now to show that {v_1,v_2,…,v_k} is a set of 𝒟_H. By the sentence below Theorem <ref>, {v_k} is a set of 𝒟_H*{v_1,v_2,…,v_k-1}. Thus {v_1,v_2,…,v_k} is a set of 𝒟_H.

We now prove the second statement. By the strong principal minor theorem, see <cit.> and also <cit.>, each set in max(S) is of cardinality r(A(H)). Thus lc-sequence σ is full if and only if k = r(A(H)) if and only if φ is full (by Corollary <ref>).


We are now ready to rephrase Theorem <ref> in delta-matroid terminology as follows.

Let D be a binary normal delta-matroid. Then there is a full lc-sequence for D if and only if each even connected summand of D with nonempty ground set is of the form ({v},∅) for some element v in the ground set of D.


Since D is a binary normal delta-matroid, we have that D = 𝒟_H for some graph H. By Lemma <ref>, there is a full lc-sequence for D if and only if there is a full lc-sequence for H. Also observe that, if a graph H' consists of only an isolated vertex v, then 𝒟_H' = ({v},∅). By Theorem <ref>, it suffices to recall that (1) a graph H' is loopless if and only if 𝒟_H' is even (the if-direction is immediate and the only-if direction follows from the well-known fact that invertible zero-diagonal skew-symmetric matrices have even dimensions, see, e.g., <cit.>) and (2) for all X ⊆ V(G), the subgraph of H induced by X is a (possibly empty) union of connected components of H if and only if there is a summand of 𝒟_H with ground set X <cit.>.



Theorem <ref> does not hold for arbitrary delta-matroids. Indeed, the delta-matroid D = (V,S) with |V| = 3 and S = { X ⊆ V | |X| ≠ 1 } is connected but not even and so the right-hand side of the equivalence of Theorem <ref> trivially holds. However, D does not have a full lc-sequence since D does not contain any singletons. It would be interesting to see to which class of delta-matroids Theorem <ref> can be generalized.

We briefly mention that delta-matroids have been generalized to multimatroids in <cit.>. In this general setting, delta-matroids translate to a class of multimatroids called 2-matroids. Therefore, this section could also have been phrased in the setting of 2-matroids. Another class of multimatroids, called tight 3-matroids can also be associated to 4-regular multigraphs. See <cit.> for the case where the 4-regular multigraph is derived from the context of gene assembly in ciliates, which is a theory closely related to that of sorting by reversals, see Section <ref>. Although it is out of the scope of this paper, it would be interesting to study tight 3-matroids associated to 4-regular multigraphs from the context of sorting by reversals.



§ A CLOSELY RELATED THEORY: GENE ASSEMBLY IN CILIATES
 
Gene assembly is a process taking place during sexual reproduction of unicellular organisms called ciliates. During this process, a nucleus, called the micronucleus (or MIC for short), is transformed into another, very different, nucleus, called macronucleus (or MAC for short). Each gene in the MAC is one block consisting of a number of consecutive[Actually, the MDSs overlap slightly in the MAC (the overlapping regions are called pointers), but this is not relevant for this paper.] segments called MDSs. These MDSs also appear in the corresponding MIC gene, but they can appear there in (seemingly) arbitrary order and orientation with respect to the MAC gene and they are moreover separated by noncoding segments called IESs. A (toy) example of a gene consisting of seven MDSs M_1,…,M_7 is given in Figures <ref> and <ref>, where the IESs are denoted by I_1,…,I_8 and if an MDS M_i in the MIC gene is in inverted orientation (i.e., rotated by 180 degrees) with respect to the MAC gene, then this is denoted by M_i (this is the standard notation in this theory, and would of course be written with a minus sign, i.e., -M_i, in the theory of sorting by reversals).

The postulated way in which a MIC gene is transformed into its MAC gene is through DCJ operations (called DNA recombination in this context), where MDSs that are not adjacent in the MIC gene but are adjacent in the MAC gene are aligned, cut and glued back such that the two MDSs become adjacent like they appear in the MAC. For example, segments w and z of Figure <ref> may be MDSs M_i and M_i+1, respectively, and x and y IESs. In the intramolecular model, the application of DCJ operations is restricted in such a way that they cannot result in MDSs appearing in different molecules <cit.> (however, it is allowed to apply two DCJ operations simultaneously, when each of them separately would result in a split of the molecule).

Starting from the MIC gene, Figure <ref>, we can construct a 4-regular multigraph in a similar way as for the theory of sorting by reversals. However, unlike before, the left-hand side of the first MDS M_1 and the right-hand side of the last MDS M_7 are not considered breakpoints. Hence, in Figure <ref>, we merge adjacent segments I_1 and M_1 (M_7 and I_4, respectively) in the MIC gene into a single segment called I_1 M_1 (M_7 I_4, respectively). Moreover, recall that before we introduced an anchor segment $ during the circularization, because the endpoints of a chromosome are breakpoints too. In the case of MIC genes, there are no endpoints that are breakpoints and so we omit the anchor segment $. Instead, during the circularization the rightmost segment I_8 is merged with the leftmost segment I_1 M_1 in the MIC gene into a single segment called I_8;I_1M_1, see Figure <ref>. Finally, because the “signed permutation” of Figure <ref> already contains intermediate segments (the IESs), we also do not have an expand step like in Figure <ref>. In this way, the intermediate segments are physical, while they are “virtual” in the theory of sorting by reversals.

The construction of a 4-regular multigraph from Figure <ref> is now identical as in the theory of sorting by reversals. Due the similarity of the “signed permutations” of Figures <ref> and <ref>, we see that the circle graph corresponding to Figure <ref> is obtained from the circle graph of Figure <ref> by removing vertices v_0 and v_7. See <cit.> for more details on how the 4-regular multigraphs, circle graphs and delta-matroids can be used to study gene assembly in ciliates.

From the discussion above it is not surprising that the theory of sorting by reversals and the theory of gene assembly in ciliates partly overlap. For example, in both theories local complementation plays an important role — indeed, as we mentioned in Section <ref> the Hannenhalli-Pevzner theorem was discovered independently in both theories. We remark that links between gene assembly in ciliates and sorting by reversals have also been appreciated in <cit.>.

























0.8cm
0.65cm
0.08cm
12






§ DISCUSSION
 
We have shown that the theory of 4-regular multigraphs, including their accompanying combinatorial structures such as circle graphs and delta-matroids, can be applied to the topic of sorting by reversals. The fact that a notion such as local complementation has been rediscovered in the context of sorting by reversals signifies the importance of the theory of 4-regular multigraphs.

This paper may serve as an introduction to the theory of 4-regular multigraphs for the audience familiar with sorting by reversals. This paper has covered only very little of the extensive body of knowledge that the theory of 4-regular multigraphs provides and that can be applied to the topic of sorting by reversals. Indeed, we also mention for example the notion of touch graph <cit.> (see also, e.g., <cit.>) of a circuit partition P that is likely to be useful for sorting by reversals. Indeed, while omitting details, the touch graph of a circuit partition P_B belonging to species B in the context of sorting by reversals (and also in the context of gene assembly in ciliates) is of a very special form, that of a star graph, which likely have interesting consequences. Indeed, while only implicitly stated in <cit.>, this star graph property is key in the main result of <cit.> from the context of gene assembly in ciliates.

Since the theory of gene assembly in ciliates can also be fit into the theory of 4-regular multigraphs, we have also extended the links between the theories of gene assembly in ciliates and  sorting by reversals as observed in <cit.>.

Finally, we have formulated the open problem of using the theory of 4-regular multigraphs in the case of DCJ operations in the presence of linear chromosomes (see Section <ref>) and also the open problem of generalizing the Hannenhalli-Pevzner theorem from graphs to a suitable subclass of delta-matroids (see Section <ref>).





 §.§ Acknowledgements

We thank anonymous referees for their helpful comments on an earlier version of this paper.








