Single Tandem Halving by Block Interchange - Biomedical Engineering Systems and Technologies - page 146

Proof. First, if ( ax ) is a vertex of the graph that belongs to a cycle C , then there exists
an edge between ( ax ) and a vertex ( ay ) . These two adjacencies are the only two
containing a copy of the marker a at the first position. So, if we consider the set of all
the first markers in all adjacencies contained in the cycle C , then each marker in this set
is present exactly twice. Therefore, the cycle C is an even cycle.
Secondly, the graph contains exactly two vertices (adjacencies) containing the
marker which are both necessarily ends of a path in NG ( G ) . Thus there can be only

one path in the graph. Since the number of edges in the graph is even and all cycles are
even, then the single path is also even.

◦

We now give a lowerbound on the minimum length of DCJ scenario transforming G
into a single tandem duplicated genome.

Lemma 1. Let d t DCJ ( G ) be the minimum DCJ distance between G and any single tan-
dem duplicated genome. If NG ( G ) contains C cycles then a lowerbound on d t DCJ ( G )
is given by:

d t DCJ ( G ) ≥ n − C − 1

Proof. First, since all cycles of NG ( G ) are even and NG ( G ) contains no odd path, then,
from the DCJ halving distance formula, the DCJ halving distance of G is d p DCJ ( G )=
n C .

Now, since any single tandem duplicated genome can be transformed into a perfectly
duplicated genome with one DCJ, then d t DCJ +1

−

d p DCJ . Therefore, we have d t DCJ ≥ ≥

d p DCJ − 1 ≥ n − C − 1 .

We are now ready to state a lowerbound on the BI single tandem halving distance of a
totally duplicated genome G .

Theorem 1. If NG ( G ) contains C cycles, then a lowerbound on the BI single tandem
halving distance is given by:

n

− C

d t BI ( G )

≥

2

Proof. We denote by ( S ) the length of a rearrangement scenario S .Let S BI be a BI
scenario transforming G into a single tandem duplicated genome. From property 1, we
have that S BI is equivalent to a DCJ scenario S DCJ such that ( S DCJ )=2

∗ ( S BI ) .

n − C n − C n − C − 1

Now, suppose that ( S BI ) <

2

,then ( S BI )

≤

2 −

1 ≤ − 1 .

2

n − C − 1

1 . Thus,
from Lemma 1 we have ( S DCJ ) <d t DCJ which contradicts the fact that d t DCJ is
the minimal number of DCJ operations required to transform G into a single tandem
duplicated genome.
In conclusion, we always have d t BI ( G )

This implies ( S DCJ ) ≤ 2 − 2 ≤ n − C − 2 <n − C −

2

n − C

≥

2

.