La lecture en ligne est gratuite
Le téléchargement nécessite un accès à la bibliothèque YouScribe
Tout savoir sur nos offres

Partagez cette publication

Universit at Ulm
Institut fur Theoretische Informatik
Leiter: Prof. Dr. Uwe Sch oning
GENOMEREARRANGEMENTALGORITHMS
DISSERTATION
zur Erlangung des Doktorgrades Dr.rer.nat.
der Fakult at fur Ingenieurwissenschaften und Informatik der
Universit at Ulm
vorgelegt von
Martin Bader
aus Friedrichshafen
2011Amtierender Dekan: Prof. Dr. Klaus Dietmayer
Gutachter: Prof. Dr. Enno Ohlebusch
Prof. Dr. Jacobo Tor an
Prof. Dr. Jens Stoye
Tag der Promotion: 6.5.2011Summary
With the increasing amount of sequenced genomes, a comparison of species based on
these data becomes more and more interesting. In contrast to the classical approach,
where only point mutations were considered, genome rearrangement problems ignore
small mutations and only consider large-scale mutations that change the gene order on
the chromosomes. This makes these problems a powerful tool when studying organisms
that have diverged millions of years ago, or very fast evolving genomes, like those of
cancerous cells.
A large variety of problems arises from genome rearrangements, like the calculation of
evolutionary distances, the reconstruction of evolutionary events and the gene order of
hypothetical ancestors, or even the reconstruction of whole phylogenetic trees. Due
to the high complexity of most of these problems, the algorithms are based on highly
simpli ed models of the reality. For example, most consider only a single
type or a small set of evolutionary events. Therefore, one biological problem results in
several algorithmic problems, depending on the chosen model.
Genome rearrangement problems are often very challenging. For many problems, it is
not known whether they can be solved exactly in polynomial time w.r.t. the size of the
genomes (like sorting by transpositions), others are known to be NP-hard even for the
most simple models, like the median problem or the multiple genome rearrangement
problem. For some problems, their complexity depends on the chosen model. Many of
the problems can be solved in polynomial time if every gene occurs in each genome
exactly once, but become NP-hard as soon as duplications are allowed.
From a computer scientist’s point of view, this raises both theoretical and algorithmic
tasks. For each problem, it is desirable either to nd an exact algorithm or to prove
that the problem is NP-hard. In some cases, the examination of a simpli ed version
of the and the connection between this simpli ed problem and the actual
problem can be helpful (actually, this approach helped Hannenhalli and Pevzner to
obtain their famous result about sorting by reversals). If a problem has been shown to
iiiSummary
be NP-hard, still many instances of the problem can be solved exactly and e ciently
by clever algorithms. Where even this strategy fails, we seek for e cient heuristic
algorithms.
The major results contained in this thesis are as follows:
We provide a linear time transformation from an arbitrary permutation into
its equivalent simple permutation, and an O(n logn) time back-transformation.
Transformations like these were used in several sorting-by-reversals algorithms,
and can give new insight into other genome rearrangement problems.
We prove the NP-completeness of the transposition median problem. As a direct
consequence, also the reversal and transposition median problem is NP-complete
if both operations are weighted equally.
We provide an exact branch and bound algorithm for the transposition median
problem and the weighted reversal and transposition median problem which is
fast enough to be used in practice. As a byproduct, we improve Christie’s exact
algorithm for sorting by transpositions, and extend it to sorting by weighted
reversals and transpositions.
We introduce a new pairwise distance measure which also considers operations
that change the genome content, namely tandem duplications and deletions. We
develop a lower bound for this distance and a greedy algorithm based on this
lower bound. We provide two versions of this algorithm, one for unichromosomal
circular genomes and one for multichromosomal linear genomes.
ivContents
Summary iii
Contents v
Preface ix
1 Introduction 1
1.1 Biological background . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.1.1 The structure of the genome . . . . . . . . . . . . . . . . . . . . 1
1.1.2 Genome dynamics . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.1.3 Prokaryotic and eukaryotic DNA . . . . . . . . . . . . . . . . . 3
1.1.4 Computational challenges and genome rearrangement problems 3
1.2 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.2.1 Elementary de nitions . . . . . . . . . . . . . . . . . . . . . . . 4
1.2.2 Relevance of the operations . . . . . . . . . . . . . . . . . . . . . 7
1.2.3 Circular versus linear genomes . . . . . . . . . . . . . . . . . . . 7
1.2.4 The breakpoint graph . . . . . . . . . . . . . . . . . . . . . . . 8
1.3 Genome rearrangement problems and distance measures . . . . . . . . 10
1.4 Simple permutations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.5 On median problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.6 Phylogenetic reconstruction . . . . . . . . . . . . . . . . . . . . . . . . 14
1.7 Genome rearrangements with duplications . . . . . . . . . . . . . . . . 15
2 Simple Permutations 17
2.1 Fundamental de nitions and results . . . . . . . . . . . . . . . . . . . . 17
2.2 Transforming a permutation into its equivalent simple permutation . . 19
2.2.1 The canonical labeling of cycles . . . . . . . . . . . . . . . . . . 19
vCONTENTS
2.2.2 (b;g)-splits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.2.3 The data structure . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.2.4 The algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.3 Transforming back the simple permutation . . . . . . . . . . . . . . . . 29
2.3.1 The data structure . . . . . . . . . . . . . . . . . . . . . . . . . 30
2.3.2 Transforming a reversal on into a reversal on . . . . . . 31simple
2.3.3 Update of the data structure . . . . . . . . . . . . . . . . . . . 32
3 On Median Problems 35
3.1 Fundamental de nitions and results . . . . . . . . . . . . . . . . . . . 35
3.1.1 The multiple breakpoint graph . . . . . . . . . . . . . . . . . . . 37
3.2 The transposition median problem is NP-complete . . . . . . . . . . . 40
3.2.1 Reduction from mdECD to oCMP . . . . . . . . . . . . . . . . . 41
3.2.2 from oCMP to TMP . . . . . . . . . . . . . . . . . . 48
3.3 A branch and bound algorithm . . . . . . . . . . . . . . . . . . . . . . 54
3.3.1 Exact calculation of pairwise distances . . . . . . . . . . . . . . 54
3.3.2 The median solver . . . . . . . . . . . . . . . . . . . . . . . . . 55
3.3.3 Adaption to the TMP . . . . . . . . . . . . . . . . . . . . . . . 60
3.3.4 Experimental results . . . . . . . . . . . . . . . . . . . . . . . . . 61
3.4 Conclusion and open problems . . . . . . . . . . . . . . . . . . . . . . 63
4 Phylogenetic Reconstruction 69
4.1 Fundamental de nitions . . . . . . . . . . . . . . . . . . . . . . . . . . 69
4.2 The algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
4.2.1 Creating the tree . . . . . . . . . . . . . . . . . . . . . . . . . . 70
4.2.2 the clouds . . . . . . . . . . . . . . . . . . . . . . . . 72
4.2.3 Improving the topology . . . . . . . . . . . . . . . . . . . . . . 73
4.2.4ving internal nodes . . . . . . . . . . . . . . . . . . . . . 74
4.2.5 Implementation details . . . . . . . . . . . . . . . . . . . . . . . 75
4.3 Experimental results . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
4.3.1 Data sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
4.3.2 Weight ratios . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
4.3.3 Other tools using the reversal distance . . . . . . . . . . . . . . . 77
4.3.4 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
4.4 Conclusion and discussion . . . . . . . . . . . . . . . . . . . . . . . . . 78
5 Rearrangement Distances with Duplications and Deletions 81
5.1 Sorting unichromosomal genomes . . . . . . . . . . . . . . . . . . . . . . 81
5.1.1 Problem de nition . . . . . . . . . . . . . . . . . . . . . . . . . . 81
5.1.2 Idea of the algorithm . . . . . . . . . . . . . . . . . . . . . . . . 82
5.1.3 The breakpoint graph revisited . . . . . . . . . . . . . . . . . . 82
viCONTENTS
5.1.4 A lower bound . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
5.1.5 The algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
5.2 Sorting multichromosomal genomes . . . . . . . . . . . . . . . . . . . . 94
5.2.1 Additional de nitions . . . . . . . . . . . . . . . . . . . . . . . 94
5.2.2 A further extension of the breakpoint graph . . . . . . . . . . . 95
5.2.3 A lower bound . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
5.2.4 The algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
5.3 Experimental results . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
5.3.1 Creating arti cial data . . . . . . . . . . . . . . . . . . . . . . . 103
5.3.2 Results on data . . . . . . . . . . . . . . . . . . . . . . 105
5.3.3 Evaluating the algorithm on cancer karyotypes . . . . . . . . . 105
5.4 Conclusion and Discussion . . . . . . . . . . . . . . . . . . . . . . . . . 114
List of Tables 117
List of Figures 119
List of Algorithms 123
List of Abbreviations 125
Bibliography 127
viiPreface
Acknowledgements
First of all I want to thank Enno Ohlebusch for supervising me. I am grateful for his
helpful comments and proofreading of all my papers, but also for his motivating words
during the last years.
I also would like to thank Sophia Yancopoulos and Michal Ozery-Flato. The discussions
we had on the RECOMB-CG workshop in San Diego laid the foundation for my work
on genome rearrangement distances with duplications.
Furthermore, I would like to thank Guillaume Bourque and Glenn Tesler for providing
MGR, Jijun Tang for providing GRAPPA-TP and DCM-GRAPPA, and Matthias Bernt for
providing amGRP. All of them also helped me to nd the best parameters for their
programs.
Finally, I would like to thank Holger Dammertz, Fabian Wagner, Thomas Schnattinger,
Dominikus Kruger, and my parents for proofreading this thesis.
List of Publications
Gog, S. and Bader, M. Fast algorithms for transforming back and forth between
a signed permutation and its equivalent simple permutation. Journal of Compu-
tational Biology 15(8):1-13, 2008.
The contents of this paper are presented in Chapter 2. The transformation into
an equivalent simple permutation was developed together with Simon Gog, who
contributed the main ideas of the algorithm.
Bader M., Abouelhoda, M.I., and Ohlebusch, E. A fast algorithm for the multiple
genome rearrangement problem with weighted reversals and transpositions. BMC
ixPreface
Bioinformatics 9:516, 2008.
The contents of this paper are presented in Chapter 4. The algorithm was
developed together with Mohamed Abouelhoda and Enno Ohlebusch, where
Mohamed had the initial idea of using clouds instead of a median solver.
Bader, M. Sorting by Reversals, Block Interchanges, Tandem Duplications, and
Deletions. BMC Bioinformatics 10(Suppl 1):S9, 2009.
The contents of this paper are presented in Section 5.1. However, the algorithm
has been adapted to circular genomes, so as to make it more consistent with the
rest of this thesis.
Bader, M. On Reversal and Transposition Medians. In Proceedings of World
Academy of Science, Engineering and Technology 54:667-675, 2009.
The contents of this paper are presented in Section 3.3. Our median solver has
been improved since the publication of the paper. These improvements are also
described in this section.
Bader, M. Genome rearrangements with duplications. BMC Bioinformatics
11(Suppl 1):S27, 2010.
The contents of this paper are presented in Section 5.2.
Bader, M. The Transposition Median Problem is NP-complete. To be published
in Theoretical Computer Science, doi:10.1016/j.tcs.2010.12.009.
The contents of this paper are presented in Section 3.2.
x

Un pour Un
Permettre à tous d'accéder à la lecture
Pour chaque accès à la bibliothèque, YouScribe donne un accès à une personne dans le besoin