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

Single Tandem Halving by Block Interchange

Antoine Thomas, Aıda Ouangraoua, and Jean-Stephane Varre

LIFL, UMR 8022 CNRS, Universite Lille 1
INRIA Lille, Villeneuve d'Ascq, France

Abstract. We address the problem of finding the minimal number of block inter-
changes required to transform a duplicated unilinear genome into a single tandem
duplicated unilinear genome. We provide a formula for the distance as well as a
polynomial time algorithm for the sorting problem. This is the extended version
of [1].

1 Introduction

Genomic rearrangements are known to play a central role in the evolutionary history
of the species. Several operations act on the genome, shaping the sequence of genes.
A number of rearrangement operations to sort a genome into another, and evaluate the
evolutionary distance between genomes, have been studied: reversals, transpositions,
translocations, block interchanges, fusions, fissions, and more recently Double-Cut-
and-Join (DCJ). In this paper, we focus on the block interchange operation, that consists
in exchanging two intervals of a genome.
Block interchanges scenarios have been studied for the first time by Christie [2]. He
proposed a O ( n 2 ) time algorithm for computing the minimum number of block inter-
changes for transforming a linear chromosome with unique gene content into another
one. Lin et al. [3] proposed later the best algorithm to date in O ( γn ) where γ is the
minimum number of block interchanges required for the transformation. Yancopoulos
et al. [4] introduced the DCJ operation which consist in cutting the genomes in two
points and joining the four resulting extremities in a different way. Interestingly, they
noticed that a block interchange can be simulated by two consecutive DCJ operations.
Another very important feature in genome evolution is that genomes often undergo
genome duplication events, both segmental and whole-genome duplications. For in-
stance, a tandem duplication event is a segmental duplication that duplicates a genomic
sequence and results in a segment made of two consecutive occurrences of the ge-
nomic sequence, called a tandem duplicated segment , in the genome. Genome dupli-
cation events are followed by other rearrangements events which result in a scrambled
genome. The Genome Halving problem introduced by El-Mabrouk et al. [5] consists
in finding the sequence of rearrangement events that allow one to go back from the
scrambled genome to the original duplicated one, when the duplication event is a whole
genome duplication event. The Single Tandem Halving problem we introduce consists
in finding the original single tandem duplicated genome, considering the duplication
event was a tandem duplication event. In this case however, as we are about to see, it
can be seen as a particular restriction of the Genome Halving problem, implied by the
block interchange rearrangement model.