Algorithms for the calculation and visualisation of phylogenetic networks [Elektronische Ressource] / vorgelegt von Tobias Klöpper

Tobias Kloepper

Sujets

• Biologie

Informations

• Publié par: eberhard_karls_universitat_tubingen
• Publié le: 01 janvier 2008
• Nombre de lectures: 29
• Langue: Deutsch
• Poids de l'ouvrage: 3 Mo

Extrait

Algorithms for the Calculation
and Visualisation of
Phylogenetic Networks
Dissertation
der Fakult¨at fu¨r Informations- und Kognitionswissenschaften
der Eberhard-Karls-Universit¨at Tu¨bingen
zur Erlangung des Grades eines
Doktors der Naturwissenschaften
(Dr. rer. nat.)
vorgelegt von
Dipl.-Math. Tobias Kl¨opper
aus Bremen
Tu¨bingen
2008Tag der mu¨ndlichen Qualifikation: 02.05.2008
Dekan: Prof. Dr. M. Diehl
1. Berichterstatter: Prof. Dr. D. H. Huson
2. Berichterstatter: Prof. Dr. D. BryantErkl¨arung
Hiermit erkl¨are ich, dass ich diese Schrift selbst¨andig und nur mit den ange-
gebenen Hilfsmitteln angefertigt habe und dass alle Stellen, die im Wortlaut
oder dem Sinne nach anderen Werken entnommen sind, durch Angaben der
Quellen kenntlich gemacht sind.
Tu¨bingen, Januar 2008 Tobias Kl¨opperivZusammenfassung
DieEvolutionstheoriebeschreibtdieEntwicklungderArtenalseinenstetigen
Prozess der Anpassung andie Umwelt. Imklassischen Modellentwickelt sich
eineSpeziesdurchMutationenundSpeziationweiter. DieseEreignisselassen
sich durch phylogenetische B¨aume darstellen. Wird das evolution¨are Mod-
ell jedoch um Ereignisse, wie zum Beispiel Rekombination, erweitert kann
dieses nicht mehr anhand eines Baumes dargestellt werden. Phylogenetis-
che Netzwerke sind eine Klasse von Graphen, welche entwickelt wurden, um
diesezus¨atzlichen Ereignissezumodellieren. DieseNetzwerke k¨onneninzwei
Klassenunterteilt werden: dieexplizitenNetzwerke, welche dieevolution¨aren
Abl¨aufe direkt modellieren und die impliziten Netzwerke, welche nicht di-
rekt die evolution¨aren Abl¨aufe modellieren, sondern die von den Abl¨aufen
erzeugten Signale.
Gegenstand dieser Arbeit ist die Entwicklung von neuen Algorithmen
zurRekonstruktion und Visualisierung vonexplizitenphylogenetischen Netz-
werken. Dabei wird eine L¨osung bei der Rekonstruktion als optimal angese-
hen, wenn sie den evolution¨aren Aufwand minimiert. Ein Problem, welches
bei der Rekonstruktion dieser Netzwerke auftritt, ist die hohe Anzahl an
m¨oglichen Graphen, von welchen gew¨ahlt werden kann, um eine optimale
L¨osung zu erhalten, und daß es keine M¨oglichkeit gibt, diese Wahl effizient
zu gestalten. Ein Weg die Anzahl von Graphen, welche betrachtet wer-
den mu¨ssen dennoch zu reduzieren, ist die Zerlegung des Problems in kleine
voneinander unabh¨angige Einheiten.
DurcheineintelligenteReduzierungderbetrachtetenGraphenklasse, kon-
nte gezeigt werden, daß eine eindeutige Zerlegung des Problems in unabh¨an-
gigeTeilprobleme m¨oglich ist. Desweiteren wurde ein effizienter Algorithmus
entwickelt, welcher dieBerechnung deroptimalen L¨osungenfu¨rdieunabh¨an-
gigen Teilprobleme erm¨oglicht.
Außerdem wurdeeinAlgorithmusentwickelt, welcher eserlaubt, explizite
phylogenetische Netzwerke zu zeichnen. Die Entwicklung des Algorithmus
wurde so gestaltet, daß vorhandene Algorithmen zur Visualisierung von phy-
logenetischen B¨aumen erweitert werden. Hierzu wird eine Modifizierung des
phylogenetischen Netzwerks durchgefu¨hrt und eine Optimierung zur Min-
imierung sich u¨berschneidener Kanten entwickelt.
Im weiteren Teil der Arbeit werden zwei Softwareprojekte vorgestellt,
welche zum Ziel haben, die Erreichbarkeit von neuen Methoden und die
Aussagekraft von großen phylogenetischen Graphen zu verbessern. In dem
ersten Projekt wurde ein Managementsystem fu¨r Plugins entwickelt, welches
erlaubt,eineinstallierteSoftwarenachtr¨aglichmitneuenMethoden(Plugins)vi
zu erweitern. In dem zweiten Projekt wurde eine Software entwickelt, welche
phylogenetische Graphen mit zus¨atzlichen Informationen zu annotieren er-
laubt.Abstract
Evolution describes the development of species as a steady adaption to the
environment. In the classical model, a species develops by mutation and
speciation events, which can be modelled using phylogenetic trees. How-
ever, if the evolutionary model is generalized by integrating events such as
recombination, a tree can no longer describe the process. Phylogenetic net-
works are a class of graphs that have been developed to describe these more
complex processes. These networks can be divided into two groups: those
networks that model evolutionary events explicitly and those networks that
do so implicitly.
In this thesis, we focus on the development of new algorithms for the
reconstruction and visualization of explicit phylogenetic networks. A recon-
struction is called optimal if it minimizes the evolutionary costs. The large
number of possible graphs from which one can choose an optimal solution
presents one of the hardest problems in the reconstruction, since no possibil-
ity exists to choose the right one efficiently. One possible way to reduce the
number of graphs one has to choose from, is to break down the problem into
smaller independent sub-problems.
By carefully reducing the class of phylogenetic networks under consider-
ation, we were able to show that indeed the main problem can be broken
up into smaller parts. Furthermore, we developed an efficient algorithm for
calculating all optimal solutions for each independent sub-problem.
Inaddition, wedevelopedanalgorithmthatiscapableofdrawingexplicit
phylogenetic networks. The algorithm was designed in such a way that the
algorithms available for drawing phylogenetic trees can be generalized to
draw explicit phylogenetic networks. To do so, we modified the explicit
phylogenetic network and extended the tree drawing algorithm by adding an
optimization step, which minimizes the number of crossing edges.
Furthermore, we present two software projects which aim at extending
theavailabilityofnewphylogeneticmethodswithinSplitsTreeandincreasing
the useablility of large phylogenetic graphs. In the first project, we imple-
mented a management system for plugins, which allows the application to
dynamically integrate new methods that are stored on a database in the
Internet. In the second project, we developed software that allows for the
annotation of phylogenetic graphs within SplitsTree.viiiAcknowledgments
I am tremendously thankful to Daniel Huson, who has given me the chance
to write this PhD on the very interesting field of phylogenetic networks.
He not only made this thesis possible, but also provided a perfect working
environment inevery respect. Atalltimes, Danielencouragedandsupported
my scientific career. Whenever I got lost in my research, he listened to my
problemsandprovidedclues tobringmeclosertothesolution. Furthermore,
hesupportedmyinterestinscientificprojectsnotdirectlyrelatedtomythesis
and for this, I am extremely thankful. I am also indebted to David Bryant
for the co-supervision of this thesis.
Inadditiontomytwosupervisors, IamverythankfultoKayNieselt,who
was the first person to introduce me to the research field of phylogenetics.
I would also like to thank all former and current staff of the department
of Algorithms in Bioinformatics - namely Marine Gaudefroy-Bergmann, Jan
Schulze, Regula Rupp, Alexander Auch, Christan Rausch, Juliane Damaris
Klein, Suparna Mitra, Olaf Delgado Friedrichs andTobias Dezulian fora fun
and productive time together. Thereby, I am especially indebted to Daniel
Richter for sharing an office with me, and his good sense of humor. Besides
themanypersonsIhavemetattheInstitute, IwouldliketothankC.Nickias
Kienle, Georg Zeller andAndreas Schmidt forlong talks aboutfootball,even
longer nights playing poker and all the fruitful scientific discussions. Fur-
thermore, I thank Dirk Fasshauer, Anand Radhakrishnan and Stefan Pabst
for their interest in my scientific work.
I am especially attached to my family, who have supported me my whole
life and who have given me the possibility and strength to walk this road.
My whole love is devoted to my wife Katrin, who has supported me all this
years and who fills my life with joy.
Finally, I would like to thank my good luck for this great life!x
Inaccordancewiththestandardscientificprotocol,Iwillusethepersonal
pronoun “we” to indicate the reader and the writer, or (as explained in
Appendix B) my scientific collaborators and myself.