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

Definition 8. [9] The natural graph of a totally duplicated genome G , denoted by
NG ( G ) , is the graph whose vertices are the adjacencies of G , and for any marker u
there is one edge between ( uv ) and ( uw ) , and one edge between ( xu ) and ( y u ) .

Note that the number of edges in the natural graph of a genome G containing n distinct
markers, each one present in two copies, is always 2 n . Moreover, since every vertex
has degree one or two, then the natural graph consists only of cycles and paths. For
example, the natural graph of genome G =(

◦ 1 2 1 43432 ◦ ) is depicted in

figure 1.

◦ 1 2 ◦

2 1

34 32

1 2 1 4

43 4 3

.
Fig. 1. The natural graph of genome G =( ◦ 1 2 1 434 3 2 ◦ ) ; it is composed of one path
and two cycles

Definition 9. Given an integer k ,a k path ) in the natural graph of a

totally duplicated genome is a cycle (resp. path) that contains k edges. If k is even, the
cycle (resp. path) is called even , and odd otherwise.

− cycle (resp. k −

Based on the natural graph, a formula for the DCJ halving distance was given in [9].
Given a totally duplicated genome G such that the number of even cycles and the num-
ber of odd paths in NG ( G ) are respectively denoted by EC and OP, the DCJ halving
distance of G is:

OP
2

d p DCJ ( G )= n − EC −

In the case of the BI single tandem halving distance, some peculiar properties of the
natural graph need to be stated, allowing one to simplify the formula of the DCJ halving
distance, and leading to a lowerbound on the BI single tandem halving distance.
In the following properties, we assume that G is a genome composed of a single
linear chromosome containing n distinct markers, each one present in two copies in G .

Property 2. The natural graph NG ( G ) contains only even cycles and paths:

1. All cycles in the natural graph NG ( G ) are even.
2. The natural graph NG ( G ) contains only one path, and this path is even.