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

unsigned integers representing markers. For example, (123)(

) is a
genome constituted of one circular and one linear chromosome. Note that all genomes
are considered unsigned in this paper w.l.o.g, because block interchange operations do
not modify the signs of markers.

◦ 4567 ◦

Definition 1. A totally duplicated genome is a genome in which each marker appears
twice.

In a totally duplicated genome, two copies of a same marker are called paralogs.
We distinguish paralogs by denoting one marker by x and its paralog by x . By con-
vention x = x . For example, the following genome is a totally duplicated genome:
( ◦ ) .

An adjacency in a genome is a pair of consecutive markers. For example, the genome

1 13245667382 4 598 7 9 ◦

( ) ,and (3 4) , (4 5) , (5 3) .The

linear or circular order of the markers in a chromosome naturally induces an order on the
adjacencies that we denote by < . For example in the previous genome the order induced
on the adjacencies is: ( ◦ 1) < (1 2) < (2 ◦ ) ,and (3 4) < (4 5) < (5 3) < (3 4) .
A double-adjacency in a genome G is an adjacency ( ab ) such that ( a b ) is an
adjacency of G as well. Note that a genome always has an even number of double-
adjacencies. For example, the four double-adjacencies in the following genome are in-
dicated by dots :

◦ 12 ◦ )(3 4 5) has six adjacencies, ( ◦ 1) , (1 2) , (2 ◦

G =( ◦ 1 132 · 4 · 5667382 · 4 · 598 7 9 ◦ )

A consecutive sequence of double-adjacencies can be rewritten as a single marker; this
process is called reduction . For example, genome G can be reduced by rewriting 2 · 4 · 5

and 2 · 4 · 5 as 10 and 10 , yielding the following genome:

G r =(

◦ 1 13106673810 9 8 7 9 ◦ )

Definition 2. A single tandem duplicated genome is a totally duplicated genome com-
posed of a single linear chromosome which can be reduced to a chromosome of the form
( ◦ x x ◦ ) .

In other words, a single tandem duplicated genome is composed of a single linear chro-
mosome where all adjacencies, except the two containing the marker

◦ and the central

adjacency, are double-adjacencies. For example, the genome ( ◦ 1 · 2 · 3 · 4 1 · 2 · 3 · 4 ◦ )

is a single tandem duplicated genome that can be reduced to ( ◦ 5 5 ◦ ) by rewritting

1 · 2 · 3 · 4 and 1 · 2 · 3 · 4 as 5 and 5 .

Definition 3. A perfectly duplicated genome is a totally duplicated genome such that
each adjacency is a double-adjacency.

For example, the genome (1 2 1 2) ( ) is a perfectly duplicated

genome composed of one single circular chromosome and two linear chromosomes.
In other words, a single tandem duplicated genome is the representation of a du-
plicated segment resulting from a tandem-duplication of a genomic sequence, and a
perfectly duplicated genome represents the result of a whole-genome duplication event
that has duplicated all chromosomes.

◦ 34 ◦ )( ◦ 3 4 ◦