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

Genome Halving has been studied under several models: reversals [5], transloca-
tion/reversals [6], breakpoints [7]. Most of the results led to polynomial time algo-
rithms. Particularly, the Genome Halving by DCJ was studied in [8,9], and in [9] some
useful data structures were presented leading to a linear time algorithm for the Genome
Halving by DCJ. Following these results on the Genome Halving by DCJ, a natural
problem to consider is the Genome Halving by block interchange. However, as block
interchanges cannot split chromosomes, the original duplicated genome in this case
would rather be a single tandem duplicated genome , ie. we consider that the cause of
duplicated content was a tandem duplication event on the whole genome.
In this paper, we study the Single Tandem Halving by block interchange on a dupli-
cated genomic segment resulting from a tandem-duplication event, followed by block
interchange events that have scrambled the gene content of the segment. This dupli-
cated genomic segment is represented as a linear chromosome with duplicated gene
content w.l.o.g, and we search for a parsimonous scenario of block interchange opera-
tions transforming the linear chromosome into a linear tandem duplicated chromosome.
We answer yes to the question: Does there exist a parsimonious sequence of block in-
terchange operations, such that, replacing each block interchange by two consecutive
DCJ operations yields a parsimonious sequence of DCJ operations ? . Based on the
adequate data structure to represent potential DCJ operations and their overlapping re-
lations, we derive a quadratic time algorithm for the Single Tandem Halving by block
interchanges. Very recently, Kovac et al. [10] addressed the problem of reincorporating
the temporary circular chromosomes induced by DCJs immediately after their creation
considering the Genome Halving. This problem is obviously related to the problem ad-
dressed in the present paper, but the aim and results are different. We are interested
in linear genomes, not in multilinear ones, and we focus on pure block interchange
scenarios that can be simulated by particular types of DCJ operations called excisions
and integrations , whereas Kovac et al. focused on general DCJ scenarios simulating
reversals, translocation, fusion, fissions along with excisions, integrations, and block
interchanges.
Section 2 gives definitions. In Section 3, we first give a lower bound on the distance
with helpful properties for the rest of the paper. In Section 4, we prove the analytical
formula for the distance. We conclude in Section 5 with a quadratic time and space
algorithm to obtain a parsimonious scenario.

2 Preliminaries: Duplicated Genomes, Rearrangement, Genome

Halving Problems

In this section we give the main definitions and notations used in the paper.

2.1 Duplicated Genomes

A genome is composed of genomic markers organized in linear or circular chromosomes.
A linear chromosome is represented by an ordered sequence of unsigned integers, each
standing for a marker, surrounded by two abstract markers at each end indicating the

telomeres. A circular chromosome is represented by a circularly ordered sequence of

◦