Reticulation in evolution [Elektronische Ressource] / vorgelegt von Simone Linz

Sujets

• Biologie

Informations

• Publié par: heinrich-heine-universitat_dusseldorf
• Publié le: 01 janvier 2008
• Nombre de lectures: 28
• Langue: English

Extrait

Reticulation in Evolution
Inaugural-Dissertation
zur
Erlangung des Doktorgrades der
Mathematisch-Naturwissenschaftlichen Fakulta¨t
der Heinrich-Heine-Universita¨t Dus¨ seldorf
vorgelegt von
Simone Linz
aus Rheinberg
Ma¨rz 2008Aus dem Institut fu¨r Bioinformatik
der Heinrich-Heine-Universit¨at Du¨sseldorf
Gedruckt mit der Genehmigung der
Mathematisch-Naturwissenschaftlichen Fakulta¨t der
Heinrich-Heine-Universita¨t Du¨sseldorf
Referent : Prof. Dr. Arndt von Haeseler
Korreferenten : Prof. Dr. Martin Lercher und Assoc. Prof. Dr. Charles Semple
Tag der mu¨ndlichen Pru¨fung: 30. April 2008Abstract
Molecular phylogenetics, the study of reconstructing evolutionary trees, is a well-estab-
lished field of scientific endeavor. However, in certain circumstances evolution is not com-
pletelytree-like. Forexample, acomparisonofgenetreesrepresenting aset ofpresent-day
species and reconstructed for different genetic loci often reveals conflicting tree topolo-
gies. These discrepancies are not always due to missampling or difficulties in the gene
tree reconstruction method, but rather due to reticulation events such as horizontal gene
transfer (HGT) and hybridization. During an HGT event, a DNA segment is transferred
from one organism to another which is not its offspring, whereas hybridization describes
the origin of a new species through a mating between two different species. Both pro-
cesses yield genomes that are mixtures of DNA regions derived from different ancestors.
Consequently, evolutionary relationships between species whose past includes reticulation
can often be better represented by using phylogenetic networks rather than trees.
Themainfocusofthisthesisistodevelopnewbiologicallymotivatedtheoreticalframe-
works that provide insight into the extent to which reticulation events have influenced
evolution. First, we have implemented the exact algorithmHybridNumber to compute
the minimum number of hybridization events for two rooted binary phylogenetic trees.
Thisapproachisbasedonthenotionofagreement forestsandusesthreerules thatreduce
thesize of theproblem instance, before calculating thehybridization number. We applied
HybridNumber to a grass data set and analyzed the extent of hybridization. We also
approached the question whether hybridization events have occurred relatively recently
or in the distant past. Furthermore, since many biological data sets lead to reconstructed
gene trees that are not fully resolved, we extended the above mentioned framework for
rootedphylogenetic trees and showed that calculating the minimum number of hybridiza-
tion events for two such trees is fixed-parameter tractable.
Second, we present a new likelihood framework to estimate a rate of HGT for a set of
taxa. To this end, we simulate an increasing number of HGT events on a species tree to
obtainatreedistributionthatcanbeusedtoestimateanHGTrateforaset ofgenetrees.
This framework was applied to the COG (Clusters of Orthologous Groups of Proteins)
data set and inaccuracies due to the gene tree reconstruction method were considered.
Finally, we give a new result on how to speed up the exact calculation of the rooted
subtree prune and regraft distance between two trees which is often used to model reticu-
lation events and end with two interesting examples that give rise to questions for future
research.
iiiAcknowledgments
I gratefully acknowledge the advice of many people who have supported me in various
kinds of ways over the last few years. Danke and thank you to:
New Zealand (South):
Charles Semple
Mike Steel
Be´ata Faller
Mareike Fischer
Dietrich Radel
Bhalchandra Thatte
Germany:Meghan Williams
Heinz and Doris LinzPeter Humphries
Bill MartinKlaas Hartmann
Martin LercherJoshua Collins
Achim RadtkeToshifumi Oba
Tal DaganJeff Cameron
Claudia KiometzisHelen Guang
Anja WalgeDavid Sun
Ingo Paulsen
Michael Rosskopf
Thomas Laubach
Lutz Voigt
Austria:Tanja GernhardNew Zealand (North):
Arndt von HaeselerRamona SchmidPete Lockhart
Tanja GesellSimon Joly Sandra Kleinenhammans
Andrea Fuhr¨ erCynthia Sharma
Heiko SchmidtManuela Dohle
USA:
Katherine St. John
Erick Matsen
Oliver Will
UK:
Magnus Bordewich
For financial support, I thank the Computer Science Department at the University of
Du¨sseldorf, the Department of Mathematics and Statistics at the University of Can-
terbury, the Allan Wilson Centre for Molecular Ecology and Evolution (AWCMEE), the
Deutsche Forschungsgemeinschaft (DFG),andthe IsaacNewton Institute for Mathemati-
cal Sciences in Cambridge.
ivCitations to Previously Published Work
Chapter 3 has been published as:
Magnus Bordewich, Simone Linz, Katherine St. John, Charles Semple (2007). A
reduction algorithm for computing the hybridization number of two trees. Evolu-
tionary Bioinformatics3:86-98.
Chapter 5 has been submitted as:
Simone Linz and Charles Semple. Hybridization in non-binary trees. submitted to
IEEE/ACM Transactions on Computational Biology and Bioinformatics, 2008.
Chapter 6 has been published as:
Simone Linz, Achim Radtke, Arndt von Haeseler (2007). A likelihood framework to
measure horizontal gene transfer. Molecular Biology and Evolution 24:1312-1319.
The algorithm HybridNumber (Chapter 3) and the software package to simulate and
estimate horizontal gene transfer (Chapter 6) are freely available for application at:
http://www.cs.uni-duesseldorf.de/NewMA/Personen/entry 43.
vContents
Abstract iii
Acknowledgments iv
Citations to Previously Published Work v
1 Introduction 1
1.1 Phylogenetic Trees and Networks . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Processes of Reticulate Evolution . . . . . . . . . . . . . . . . . . . . . . . 2
1.2.1 Hybridization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2.2 Horizontal Gene Transfer (HGT) . . . . . . . . . . . . . . . . . . . 3
1.3 Inferring Reticulate Evolution . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.4 Preliminary Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.4.1 Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.4.2 Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.4.3 Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.4.4 The Rooted Subtree Prune and Regraft Operation . . . . . . . . . . 10
1.5 Organization of this Thesis . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2 Measuring Hybridization for a Set of Phylogenetic Trees 14
2.1 Hybridization Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.2 Agreement Forests . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.3 Subtree and Chain Reduction . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.4 Cluster Reduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3 HybridNumber: A Reduction Algorithm for Hybridization 35
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
3.2 The Algorithm HybridNumber . . . . . . . . . . . . . . . . . . . . . . . 36
vi3.2.1 Reductions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
3.2.2 Exhaustive Search Strategy . . . . . . . . . . . . . . . . . . . . . . 40
3.3 The Grass (Poaceae) Data Set . . . . . . . . . . . . . . . . . . . . . . . . . 42
3.4 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
4 How Deep is a Hybridization Event? 49
4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
4.2 Reduced Forests . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
4.2.1 A Subtree-Reduced Forest . . . . . . . . . . . . . . . . . . . . . . . 51
4.2.2 A Chain-Reduced Forest . . . . . . . . . . . . . . . . . . . . . . . . 52
4.2.3 A Cluster-Reduced Forest and a Cluster-Pair Forest . . . . . . . . . 54
4.3 The Algorithm BuildForest . . . . . . . . . . . . . . . . . . . . . . . . . 59
4.4 Application . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
5 Hybridization in Non-Binary Trees 66
5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
5.2 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
5.3 Agreement Forests . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
′5.4 Characterizing h(T,T ) in Terms of Agreement Forests . . . . . . . . . . . 71
5.5 Reducing the Size of the Problem Instance . . . . . . . . . . . . . . . . . . 75
5.6 Minimum Hybridization is Fixed-Parameter Tractable . . . . . . . . . . 95
6 A Likelihood Framework to Measure Horizontal Gene Transfer 103
6.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
6.2 Materials and Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
6.2.1 Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
6.2.2 Modeling Horizontal Gene Transfer . . . . . . . . . . . . . . . . . . 105
6.2.3 Estimating the Probability Distribution of Gene Trees . . . . . . . 107
vii6.2.4 The COG Data Set . . . . . . . . . . . . . . . . . . . . . . . . . . . 108
6.2.5 Comparing Trees . . . . . . . . . . . . . . . . . . . . .