Double Cut and Join with Insertions and Deletions

Theorem 1 (Bergeron et al., 2006)

Given two genomes A and B without duplicated markers, we have \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$d_{DCJ} (A, B) = \mid {\cal G} \mid - c - \frac {b} {2} $$ \end{document} , where \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${\cal G}$$ \end{document} is the set of common markers between A and B, and c and b are, respectively, the number of cycles and of AB-paths in AG(A, B).

A DCJ operation is optimal when it either increases the number of cycles by one, or the number of AB-paths by two (decreasing the DCJ distance by one). In the same way, a neutral DCJ operation does not affect the number of cycles and AB-paths, while a counter-optimal DCJ operation either decreases the number of cycles by one, or the number of AB-paths by two. The problem of finding an optimal sequence of operations that do a DCJ-sorting of A into B can be solved with a simple greedy linear time algorithm (Bergeron et al., 2006).

Proposition 1

If γ₁γ₂ is a clean \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${\cal G}$$ \end{document} -adjacency in a DCJ-unsorted component C of AG(A, B), such that neither γ₁ nor γ₂ are telomeres, then it is always possible to extract a clean cycle from C with an optimal DCJ operation.

Proof

If γ₁γ₂ is in \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$V_{\cal G} (B)$$ \end{document} , we apply a DCJ on the two vertices γ₁ℓ₁γ₃ and γ₂ℓ₂γ₄ of \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$V_{\cal G} (A)$$ \end{document} that are neighbors of γ₁γ₂, creating the two new vertices \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\gamma_3 \overline{\ell}_1 \ell_2 \gamma_4$$ \end{document} and γ₁γ₂. Observe that the vertex γ₁γ₂ in \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$V_{\cal G} (B)$$ \end{document} and the new vertex γ₁γ₂ in \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$V_{\cal G} (A)$$ \end{document} are extracted into a clean cycle. Analogously, if γ₁γ₂ is in \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$V_{\cal G} (A)$$ \end{document} , we do the same procedure using the two vertices of \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$V_{\cal G} (B)$$ \end{document} that are neighbors of γ₁γ₂.   ▪

Proposition 2

A run can be entirely accumulated in the label of one single \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${\cal G}$$ \end{document} -adjacency with optimal DCJ operations.

Proof

A run that is not yet accumulated is distributed over two or more \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${\cal G}$$ \end{document} -adjacencies in one genome. The \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${\cal G}$$ \end{document} -adjacencies in the other genome within the run are clean. We can thus apply optimal DCJs that extract clean cycles (Proposition 1) and accumulate the entire run in the label of one \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${\cal G}$$ \end{document} -adjacency.   ▪

Proposition 2 immediately gives an upper bound for the distance:

Lemma 1

Given two genomes A and B without duplicated markers, we have \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} \begin{align*} d_{DCJ}^{id} (A, B) \leq d_{DCJ} (A, B) + \sum_{C \in AG (A, B)} \Lambda (C). \end{align*} \end{document}

For some instances of A and B, the upper bound of Lemma 1 gives the exact number of steps required to sort A into B. However, since two runs can be merged together with a DCJ operation, the DCJ-indel distance is often smaller than this upper bound. Given a DCJ operation ρ, let Λ₀ and Λ₁ be, respectively, the number of runs in AG(A, B) before and after ρ. We define ΔΛ(ρ) = Λ₁ − Λ₀.

Proposition 3

Given any DCJ operation ρ, we have ΔΛ(ρ) ≥ −2.

Proof

If ρ cuts between an \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${\cal A}$$ \end{document} -run r₁ and a \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${\cal B}$$ \end{document} -run r₂ and between an \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${\cal A}$$ \end{document} -run r₃ and a \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${\cal B}$$ \end{document} -run r₄, with r₁ ≠ r₃ and r₂ ≠ r₄, and joins r₁ with r₃ and r₂ with r₄, then ΔΛ(ρ) = −2. As a DCJ has at most two cuts and two joins, it is not possible to do better, that is ΔΛ(ρ) ≥ −2.   ▪

In order to obtain the exact formula for the DCJ-indel distance, we will first analyze the components of the adjacency graph separately. Given two genomes A and B and a component \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$C \in AG (A, B)$$ \end{document} , we denote by d_DCJ(C) the minimum number of DCJ operations required to do a separate DCJ-sorting in C, applying DCJs only on vertices of C (or vertices that result from DCJs applied on vertices that were in C). From Braga and Stoye (2010), we know that it is possible to do a separate DCJ-sorting using only optimal DCJs in any component of AG(A, B), or, in other words, \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$d_{DCJ} (A, B) = \sum \nolimits_{C \in AG (A, B)}d_{DCJ} (C)$$ \end{document} .

We then define the indel-potential of a component C, denoted by λ(C), as the minimum number of runs that we can obtain doing a separate DCJ-sorting in C with optimal DCJ operations. The indel-potential of a component C can be computed with a simple formula that depends only on the number of runs in C:

Proposition 4

Given a component C in AG(A,B), the indel-potential of C is given by \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\lambda (C) = \left\lceil \frac {\Lambda(C) + 1} {2} \right\rceil,$$ \end{document} if Λ(C) ≥ 1. Otherwise λ(C) = 0.

Proof

The proof is by induction on i = Λ(C) and the hypothesis is \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$T (i) = \left\lceil \frac {i + 1} {2} \right\rceil$$ \end{document} . A labeled DCJ-sorted component can have one or two runs, thus we need two base cases, T(1) = 1 and T(2) = 2. These cases can be easily verified. More intricate is the inductive step, for i ≥ 3.

If i = 3, the best we can do is to merge the first and the last runs with an optimal DCJ, obtaining a cycle with two runs. This gives \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$T (3) = T (2) = \left\lceil \frac {2 + 1} {2} \right\rceil = \left\lceil \frac {3 + 1} {2} \right\rceil$$ \end{document} . If i = 4, any optimal DCJ merging runs would split the original component C into a cycle with two runs and another component with only one run. This gives \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$T (4) = T (2) + T (1) = 3 = \left\lceil \frac {4 + 1} {2} \right\rceil$$ \end{document} .

If i ≥ 5, the best we can do is to use a DCJ with ΔΛ = −2, that extracts three consecutive runs into a cycle of two runs and leaves the other component with i − 4 runs. We then have \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$T (i) = T (2) + T (i - 4) = 2 + \left\lceil \frac {i - 4 + 1} {2} \right\rceil = \left\lceil \frac {i - 4 + 1 + 4} {2} \right\rceil = \left\lceil \frac {i + 1} {2} \right\rceil$$ \end{document} .   ▪

If λ₀ and λ₁ are, respectively, the sum of the indel-potentials for the components of the adjacency graph before and after a DCJ operation ρ, we define Δλ(ρ) = λ₁ − λ₀. By the definition of λ, any optimal DCJ ρ acting on a single component has Δλ(ρ) ≥ 0. However, considering the case in which only one component is affected by ρ, we still need to investigate Δλ(ρ) when ρ is neutral or counter-optimal.

Proposition 5

Given a DCJ operation ρ acting on a single component, we have Δλ(ρ) ≥ 0, if ρ is counter-optimal, and Δλ(ρ) ≥ −1, if ρ is neutral.

Proof

The linearization of a cycle is the only counter-optimal DCJ that acts on a single component. This can decrease neither Λ, nor λ. Moreover, when Λ ≤ 2, it is not possible to decrease the indel-potential with any DCJ. When the component has Λ = 3, the best we can get with a neutral ρ is ΔΛ(ρ) = −1. This gives \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\lambda_1 = \left\lceil \frac {(3 - 1) + 1} {2} \right\rceil = \left\lceil \frac {3} {2} \right\rceil = \left\lceil \frac {3 + 1} {2} \right\rceil = \lambda_0$$ \end{document} , that is, Δλ(ρ) = 0. And when the component has Λ ≥ 4, we can get ΔΛ(ρ) = −2 with a neutral ρ, resulting in \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\lambda_1 = \left\lceil \frac {(\Lambda (C) - 2) + 1} {2} \right\rceil = \left\lceil \frac {\Lambda (C) + 1} {2} \right\rceil - 1 = \lambda_0 - 1$$ \end{document} , that is, Δλ(ρ) = −1.   ▪

We denote by \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$d_{DCJ}^{id} (C)$$ \end{document} the minimum number of DCJ and indel operations required to sort separately a component C of AG(A, B).

Proposition 6

If C is a component of AG(A, B), then we have \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$d^{id}_{DCJ} (C) = d_{DCJ} (C) + \lambda (C)$$ \end{document} .

Proof

By the definition of λ, the best we can do with optimal DCJs is d_DCJ(C) + λ(C). From Proposition 5, we know that Δλ(ρ) ≥ 0 if ρ is a counter-optimal DCJ, thus we can only get longer sorting scenarios if we use such operations. We also know that Δλ(ρ) ≥ −1 if ρ is neutral, and, since this kind of operation increases the sorting scenario by one with respect to the scenario with only optimal DCJs, this gives at least d_DCJ(C) + λ(C).   ▪

Proposition 6 gives a new upper bound for the DCJ-indel distance:

Lemma 2

Given two genomes A and B without duplicated markers, we have \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} \begin{align*} d_{DCJ}^{id} (A, B) \leq d_{DCJ} (A, B) + \sum_{C \in AG (A, B)} \lambda (C). \end{align*} \end{document}

Proof

We can sort the components separately with \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\sum \nolimits_{C \in AG (A, B)}d_{DCJ}^{id} (C)$$ \end{document} steps, which corresponds exactly to \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$d_{DCJ} (A, B) + \sum \nolimits_{C \in AG (A, B)} \lambda (C)$$ \end{document} .   ▪

Since λ(C) ≤ Λ(C), the upper bound given by Lemma 2 is tighter than the one given by Lemma 1, but can still be improved. Observe that a parsimonious scenario may not simply consist of optimal DCJ operations, insertions and deletions. Sometimes a neutral DCJ can lead to a shorter sequence of operations sorting one genome into another one, as we can see in Figure 5.

OPEN IN VIEWER

FIG. 5.

An optimal scenario sorting \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\{ \circ ab \circ, \circ cd \circ \} \ {\rm into} \ \{ \circ a \circ, \circ b \circ, \circ c \circ, \circ d \circ \}$$ \end{document} (i) and two different scenarios sorting \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\{ \circ axb \circ, \circ cyd \circ \} \ {\rm into} \ \{ \circ a \circ, \circ ub \circ, \circ c \circ, \circ vd \circ \} $$ \end{document} . In (ii) in addition to the two optimal DCJ operations (fissions) from (i) we have two insertions and two deletions, using six steps. In (iii), we first use a neutral DCJ operation (translocation) that allows us to do only one deletion and one insertion, achieving a total of five steps.

Proposition 7

Given any recombination ρ, we have Δλ(ρ) ≥ −2.

Proof

Only the recombinations that decrease or do not change the number of runs (ΔΛ ≤ 0) have to be analyzed (we can not have Δλ ≤ −1 if the number of runs increases). First consider the recombination of two paths with i and j runs, respectively, that results in two new paths with i′ and j′ runs. Observe that the best we can have is when i and j are even, i′ and j′ are odd and ΔΛ = −2, that gives: \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\lambda_1 = \left\lceil \frac {i^ {\prime} + 1} {2} \right\rceil + \left\lceil \frac {j^ {\prime} + 1} {2} \right\rceil = \frac {i^ {\prime} + j^ {\prime} + 2} {2} = \frac {i + j} {2} = \frac {i} {2} + \frac {j} {2} = \left\lceil \frac {i + 1} {2} \right\rceil - 1 + \left\lceil \frac {j + 1} {2} \right\rceil - 1 = \lambda_0 - 2$$ \end{document} . The analysis of recombinations involving cycles is analogous.   ▪

Given a recombination ρ, let Δ _dcj (ρ) be respectively 0, +1 and +2 depending whether ρ is optimal, neutral or counter-optimal. Any recombination applied to a vertex of an AA-path and a vertex of a BB-path is optimal (Braga and Stoye, 2010). A recombination applied to vertices of two different AB-paths can be either neutral, when the result is also a pair of AB-paths, or counter-optimal, when the result is a pair composed of an AA-path and a BB-path. All other types of path recombinations are neutral. In addition, all recombinations involving at least one cycle are counter-optimal. We define Δd(ρ) = Δ _dcj (ρ) + Δλ(ρ). Any counter-optimal recombination has Δd ≥ 0, thus only path recombinations can have Δd ≤ −1.

Let \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${\cal A}$$ \end{document} (respectively \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${\cal B}$$ \end{document} ) be a sequence with an odd (≥1) number of runs, starting and ending with an \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${\cal A}$$ \end{document} -run (respectively \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${\cal B}$$ \end{document} -run). We can then make any combination of \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${\cal A} \ {\rm and} \ {\cal B}$$ \end{document} , such as \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${\cal AB}$$ \end{document} , that is a sequence with an even (≥2) number of runs, starting with an \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${\cal A}$$ \end{document} -run and ending with a \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${\cal B}$$ \end{document} -run. An empty sequence (with no run) is represented by ɛ. Then each one of the notations \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$AA_{\varepsilon}, AA_{\cal A}, AA_{\cal B}, AA_{\cal AB}, BB_{\varepsilon}, BB_{\cal A}, BB_{\cal B}, BB_{\cal AB}, AB_{\varepsilon}, AB_{\cal A}, AB_{\cal B}, AB_{\cal AB} \ {\rm and} \ AB_{\cal BA}$$ \end{document} represents a particular type of path (AA, BB or AB) with a particular structure of runs \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$(\varepsilon, {\cal A}, {\cal B}, {\cal AB} \ {\rm or} \ {\cal BA})$$ \end{document} . The complete set of path recombinations with Δd ≤ −1 is given in Table 1. In Table 2 we list recombinations with Δd = 0 that create at least one source of recombinations of Table 1. We denote by \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$AB_\bullet$$ \end{document} an AB-path that can not be a source of a recombination in Tables 1 and 2, such as \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$AB_{\varepsilon}, AB_{\cal A} \ and \ AB_{\cal B}$$ \end{document} .

Proposition 8

The recombinations with Δd = 0 involving cycles or circular singletons cannot create new components that can be used as sources of recombinations listed in Tables 1 and 2.

Proof

A recombination ρ with Δd = 0 involving a cycle or a circular singleton C would integrate C to another component C′ without changing the type or the structure of runs in C′. Thus, if C′ is a source of a recombination in these tables after ρ, C′ was already the same type of source before ρ. And if C′ was not a source before ρ, C′ cannot become a source after ρ.   ▪

With Proposition 8, we already have an exact formula to compute \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$d^{id}_{DCJ}$$ \end{document} for a particular set of instances. Given a \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${\cal G}$$ \end{document} -adjacency γℓ∘ of a genome A such that γ ≠ ∘, then γ is said to be a tail of a linear chromosome in A. Two genomes are co-tailed if their sets of tails are equal (this includes two genomes composed only of circular chromosomes).

Theorem 2

Given two co-tailed genomes A and B without duplicated markers, we have \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$d^{id}_{DCJ} (A, B) = d_{DCJ} (A, B) + \sum \nolimits_{C \in AG (A, B)} \lambda (C)$$ \end{document} .

Proof

The graph AG(A, B) for co-tailed genomes A and B can have only cycles, singletons (that could be \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$AA_{\cal A} \ {\rm and} \ BB_{\cal B}$$ \end{document} ) and AB-paths of one edge (that could be \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$AB_{\cal AB}$$ \end{document} , but never \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$AB_{\cal BA}$$ \end{document} ). Observe that with these paths no recombination with Δd ≤ −1 is possible. From Proposition 8, we also know that cycles cannot lead to recombinations with Δd ≤ −1.   ▪

Now we continue the analysis for the general case. The two sources of a recombination can also be called partners. Looking at Table 1 we observe that all partners of \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$AB_{\cal AB} \ {\rm and} \ AB_{\cal BA}$$ \end{document} paths are also partners of \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$AA_{\cal AB} \ {\rm and} \ BB_{\cal AB}$$ \end{document} paths, all partners of \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$AA_{\cal A} \ {\rm and} \ AA_{\cal B}$$ \end{document} paths are also partners of \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$AA_{\cal AB}$$ \end{document} paths and all partners of \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$BB_{\cal A} \ {\rm and} \ BB_{\cal B}$$ \end{document} paths are also partners of \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$BB_{\cal AB}$$ \end{document} paths. Moreover, some resultants of recombinations in Tables 1 and 2 can be used in other recombinations. These observations allow the identification of recombination groups, as listed in Table 3.

The deductions shown in Table 3 can be computed with an approach that greedily maximizes the number of recombinations in P, Q, T, S, M and N in this order. The P part contains only one operation and is thus very simple. The same happens with Q, since the two groups in this part are mutually exclusive after applying P. The part T is only the application of all possible remaining groups of two operations with Δd = −2. Similarly, the part S is only the application of all possible remaining operations with Δd = −1. After S, the two groups in M are mutually exclusive and then the same happens to the six groups in N. Although some groups in T, S, M and N have some reusable resultants, those are actually never reused (if operations that are lower in the table use as sources resultants from higher operations, the sources of all referred operations would be previously consumed in operations that occupy even higher positions in the table). Due to this fact, the number of operations in P, Q, T, S, M and N depends only on the initial number of each type of component.

The results presented in this section give rise to the following theorem, which gives the exact formula for the DCJ-indel distance:

Theorem 3

Given two genomes A and B without duplicated markers, we have \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} \begin{align*} d^{id}_{DCJ} (A, B) = d_{DCJ} (A, B) + \sum_{C \in AG (A, B)} \lambda (C) - 2P - 3Q - 2T - S - 2M - N, \end{align*} \end{document}

where the values P, Q, T, S, M and N are computed as described above.

Both AG(A, B) and d_DCJ(A, B) can be computed in linear time (Bergeron et al., 2006). The runs can be obtained by a single walk through each component of AG(A, B), which is also linear. The algorithm to compute P, Q, T, S, M and N is a finite sequence of if and else statements, that depends only on the number of each type of labeled path in AG(A, B), thus the whole procedure takes linear time.

Proposition 9

Given two genomes A and B, and a pair of sequences s ₁ and s ₂ composed of DCJ and indel operations acting on both genomes A and B, transforming respectively A and B into an intermediate genome I, such that \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\mid s_1 \mid + \mid s_2 \mid = d_{DCJ}^{id} (A, B)$$ \end{document} , then \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$s_1s_2^{- 1}$$ \end{document} is an optimal sequence of DCJ and indel operations that transforms A into B.

Proof

First note that, since s₁ sorts A into I and \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$s_2^{- 1}$$ \end{document} sorts I into B, \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$s_1 s_2^{- 1}$$ \end{document} sorts A into B. Furthermore, \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$s_1 s_2^{- 1}$$ \end{document} has length \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$d^{id}_{DCJ} (A, B)$$ \end{document} and is an optimal sorting sequence. Otherwise, there would exist a sorting sequence shorter than \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$d^{id}_{DCJ} (A, B)$$ \end{document} , which is a contradiction.   ▪

It is also interesting to observe that the space of solutions of the sorting problem contains scenarios with different compositions and, using the same number of steps, one could look for a scenario with more indels and less DCJ operations, or for a scenario with less indels and more DCJ operations. Figure 7 shows examples of two different approaches: one that minimizes the number of DCJs, and one that minimizes the number of indels. Both approaches will be presented in the following.

OPEN IN VIEWER

FIG. 7.

Two optimal scenarios sorting \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\{ \circ axec \circ, \circ d \overline{y}b \circ \} \ {\rm into} \ \{ \circ aubcdve \circ \}$$ \end{document} . (i) Minimizing DCJs gives three DCJs and three indels. (ii) Minimizing indels gives four DCJs and two indels.

Proposition 10

Given a component C with Λ(C) ≥ 4, the best we can get with a neutral DCJ operation ρ acting only on C is ΔΛ(ρ) = −2 and Δλ(ρ) = −1.

Proof

When the component has Λ ≥ 4, the operation ρ can cut after the first and before the last run, and simply invert this segment. In this case we get ΔΛ(ρ) = −2, resulting in \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\lambda_1 = \left\lceil \frac {(\Lambda (C) - 2) + 1} {2} \right\rceil = \left\lceil \frac {\Lambda (C) + 1} {2} \right\rceil - 1 = \lambda_0 - 1$$ \end{document} . (Since we can apply only two cuts and two joins, it is not possible to do better.)   ▪

Proposition 10 guarantees that, with neutral DCJs, we can merge runs in any component C with Λ(C) ≥ 4, such that in the end of the process C has only two or three runs. In order to maximize the use of these neutral DCJs, a good strategy is to first regroup runs efficiently into one component. Thus, the recombinations in P, Q, T, S, M and N should be done such that one of the resultants, that should be an AB-path whenever it is possible, has zero or one run, and the other resultant has all the remaining runs (this can be done for all mentioned recombinations). In the following steps, we can regroup runs by using recombinations with Δd = 0, as those listed in Table 2. Additional recombinations with Δd = 0 are listed in Table 4, in which \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$O_{\cal AB}$$ \end{document} is a cycle with at least one \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${\cal A}$$ \end{document} -run and one \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${\cal B}$$ \end{document} -run, and \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$S_{\cal A} \ {\rm and} \ S_{\cal B}$$ \end{document} are circular singletons in genomes A and B, respectively. All recombinations in Table 4 regroup all remaining runs in one single component, thus they should be applied before the neutral DCJs from Proposition 10. The same happens with the neutral and optimal recombinations in Table 2. (Instead of using the two counter-optimal recombinations of Table 2 we use the two neutral recombinations of Table 4 that have the same sources, but regroup all remaining runs in one component.)

From the previous observations we can derive Algorithm 2, to sort a genome A into a genome B minimizing the number of insertions and deletions.

It is interesting to observe that Algorithm 2 merges into only two runs all runs from all components that have two or more runs, together with the runs from all paths that have only one run. On the other hand, the runs that appear in cycles that have only one run could only be merged with circular singletons.

Proposition 11

Given three genomes A, B and C without duplicated markers, such that A and B have no common marker that does not occur in C, \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$d^{id}_{DCJ} (A, B) \geq d^{id}_{DCJ} (A, C)$$ \end{document} and \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$d^{id}_{DCJ} (A, B) \geq d^{id}_{DCJ} (B, C)$$ \end{document} , then \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$d^{id}_{DCJ} (A, B) \leq d^{id}_{DCJ} (A, C) + d^{id}_{DCJ} (B, C)$$ \end{document} .

Proof

We know that \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${\cal D} = \emptyset$$ \end{document} and, without loss of generality, we can also assume \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${\cal C} = \emptyset$$ \end{document} . Let s₁ be an optimal sequence sorting A into C. The sequence s₁ has some deletions of elements from \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${\cal A}$$ \end{document} , insertions of elements from \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${\cal E}$$ \end{document} and some DCJs. In the same way, an optimal sequence s₂ sorting C into B has some deletions of elements from \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${\cal F}$$ \end{document} , insertions of elements from \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${\cal B}$$ \end{document} and also some DCJs. Note that s₁s₂ is a valid sequence sorting A into B (no insertion or deletion of common markers is applied). Thus \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\mid s_1 s_2 \mid \geq d^{id}_{DCJ} (A, B)$$ \end{document} , otherwise there would be a valid sequence shorter than \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$d^{id}_{DCJ} (A, B)$$ \end{document} sorting A into B, which is a contradiction. Since \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\mid s_1 \mid = d^{id}_{DCJ} (A, C) \ {\rm and} \ \mid s_2 \mid = d^{id}_{DCJ} (B, C)$$ \end{document} , we have \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$d^{id}_{DCJ} (A, C) + d^{id}_{DCJ} (B, C) \geq d^{id}_{DCJ} (A, B)$$ \end{document}    ▪

In general, as we will see next, the triangle inequality holds for m if we take k ≥ 3/2.

Proposition 12

Given k ≥ 3/2 and any three genomes A, B and C without duplicated markers, such that \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$d^{id}_{DCJ} (A, B) \geq d^{id}_{DCJ} (A, C) \ and \ d^{id}_{DCJ} (A, B) \geq d^{id}_{DCJ} (B, C)$$ \end{document} , then m(A, B) ≤ m(A, C) + m(B, C).

Proof

Recall that, to prove that the triangle inequality holds for m, we only need to find a k such that \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$d^{id}_{DCJ} (A, B) \leq d^{id}_{DCJ} (A, C) + d^{id}_{DCJ} (B, C) + 2k \mid {\cal D} \mid$$ \end{document} holds. The case in which \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${\cal D} = \emptyset$$ \end{document} is covered by Proposition 11. It remains to examine the case in which \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${\cal D} \neq \emptyset$$ \end{document} , that is, when A and B have at least one common marker that does not occur in C. Here, the worst case would be to have an empty genome C. Note that in this case we have \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${\cal C} = {\cal E} = {\cal F} = {\cal G} = \emptyset$$ \end{document} . Let X_A, X_B be the number of chromosomes in A and B, L_A, L_B be the number of linear chromosomes in A and B, and S_A, S_B be the number of circular singletons in A and B. Since C is empty, we know that \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$d^{id}_{DCJ} (A, C) = X_A \ {\rm and} \ d^{id}_{DCJ} (B, C) = X_B$$ \end{document} . Moreover, \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$d_{DCJ} (A, B) \leq \mid {\cal D} \mid$$ \end{document} and the maximum number of indels between A and B is given by \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$2 \mid {\cal D} \mid + L_A + S_A + L_B + S_B$$ \end{document} (the circular singletons are obvious indels; furthermore, in each genome we can have one indel per element in \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${\cal D}$$ \end{document} and one extra indel per linear chromosome). This gives \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\mid {\cal D} \mid + 2 \mid {\cal D} \mid + L_A + S_A + L_B + S_B \leq X_A + X_B + 2k \mid {\cal D} \mid$$ \end{document} . Since X_A ≥ L_A + S_A and X_B ≥ L_B + S_B, we have \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$3 \mid {\cal D} \mid \leq 2k \mid {\cal D} \mid$$ \end{document} , that holds for any k ≥ 3/2.   ▪

As we could see here, when using the DCJ-indel distance to do a pairwise comparison of three genomes without duplicated markers, the triangle inequality can only be disrupted when two genomes have common markers that do not occur in the third genome. In general, a surcharge of at least 3/2 for each unique marker is enough to guarantee the triangle inequality. However, since the value of 3/2 was obtained by an overestimation of the maximum possible DCJ-indel distance between genomes A and B, we conjecture that a surcharge of 1 would be enough to this purpose. It is interesting to emphasize that this correction can be applied a posteriori, without interfering with the algorithms to compute the distance and sort genomes presented in the previous sections.