Detailansicht
Phylogenomics
theory, algorithms and applications
Olga Chernomor
Art der Arbeit
Dissertation
Universität
Universität Wien
Fakultät
Zentrum für Molekulare Biologie
Studiumsbezeichnung bzw. Universitätlehrgang (ULG)
Doctor of Philosophy-Doktoratsstudium NAWI Bereich Lebenswissenschaften (Dissertationsgebiet: Molekulare Biologie, IK: Computational Sciences)
Betreuer*in
Arndt von Haeseler
DOI
10.25365/thesis.39935
URN
urn:nbn:at:at-ubw:1-30054.85757.556959-2
Link zu u:search
(Print-Exemplar eventuell in Bibliothek verfügbar)
Abstracts
Abstract
(Deutsch)
In der Evolutionsbiologie wurde in den letzten Jahren durch Aufkommen der Phylogenomik ein neues Kapitel aufgeschlagen. Mit Hilfe genomweiter Analysen wird es zunehmend möglich, schwierige Fragestellungen zur Evolutionsgeschichten zu untersuchen, doch diese neuen Perspektiven sind gleichzeitig verbunden mit erhöhter Komplexität und anderen Schwierigkeiten bei der Stammbaumberechnung. Der Fokus dieser Dissertation ist es, Einblicke in Fragen aus der Theorie der Baumrekonstruktion sowie zu Algorithmen und Anwendungen der Phylogenomik zu geben.
Ein Hauptaugenmerk liegt hierbei auf der Untersuchung phylogenetischer Terrassen, dies Speziesbäume mit gleichen Maximum Likelihood oder Maximum Parsimonie Werten. Ein Problem bei der Suche nach optimalen Bäumen ist die Größe der Terrasse. Die Größe der Terrassen hängt dabei entscheidend von dem untersuchten multiple Sequenz Alignment ab.
Im Rahmen dieser Arbeit wird zunächst erklärt wie man Terrassen während der Baumsuche detektiert. Dazu studieren wir durch Partitionen induzierte Bäume und in welcher Weise topologische Umformungen am Speziesbaum Änderungen an den Partitionsbäumen bedingen. Sollte eine Änderung der Verzweigungsstruktur eines Speziesbaum keine Änderung an den mit ihm assoziierten induzierten Partitionsbäumen hervorrufen, gehören sowohl der gegenwärtige als auch der geänderte neue Speziesbaum zur selben Terrasse.
Es werden drei Propositionen bewiesen, die Kriterien definieren nach welchen verschiedene Umformungsoperationen, namentlich NNI (Nearest Neighbour Interchange), SPR (Subtree Pruning and Regrafting) und TBR (Tree Bisection and Reconnection), sich die induzierten Partitionsbäume verändern. Weiters wird das Konzept von Terrassen erweitert, in dem partielle Terrassen definiert werden und ihr Auftreten für echte Alignments unter NNI Umformungsoperationen untersucht wird.
Im zweiten Teil wird die Datenstruktur, PTA, (phylogenetic terrace aware data structure) vorgestellt, die eine effiziente Analyse verknüpfter multipler Alignments unter Berücksichtigung phylogenetischer Terrassen ermöglicht. Mit Hilfe von PTA und den Kriterien zur Erfassung (partieller) Terrassen ist es möglich, überflüssige Neuberechnungen der Maximum Likelihood oder Maximum Parsimonie Werte zu vermeiden und so die für die Baumsuche benötigte Rechenzeit zu verringern. Durch die Identifizierung partieller Terrassen wird im Vergleich zur Standardimplementierung eine bis zu 5-fache Beschleunigung von IQ-TREE festgestellt und nach der Implementierung der Terrassenidentifikation ist IQ-TREE in der Lage bis zu 6 Mal schneller Maximum-Likelihood-Bäume zu finden als RAxML. Die Datenstruktur PTA eignet sich für den Einsatz mit allen Partitionsmodellen und für alle üblichen topologischen Umformungen wie NNI, SPR und TBR.
Im Schlussteil dieser Arbeit werden Methoden für den Einsatz in Naturschutzbiologie und -ökologie eingeführt und diskutiert, wobei Phylogenomik herangezogen wird, um die evolutionäre Diversität verschiedener Spezies zu quantifizieren. Wir diskutieren die Aufgabe der Auswahl überlebensfähiger Taxa, ein Optimierungsproblem unter Einbeziehung von Räuber-Beute-Interaktionen. Zuerst wird dabei der Rahmen der Aufgabenstellung erweitert, um auch die Splitdiversität (SD) zu erfassen, ein Biodiversitätsmaß welches auf der evolutionären Distanz zwischen verschiedenen Spezies in Splitnetzwerken basiert. Danach erweitern wir die Definition von Lebensfähigkeit um die Nahrungszusammensetzung des Räubers miteinzubeziehen und so die Modellierung realistischer zu gestalten. Mit Hilfe der SD und unter Berücksichtigung eines realistischen Modells werden Spezies für Naturschutzmaßnahmen priorisiert. Obwohl derartige Optimierungsaufgaben in den Bereich NP-schwerer Probleme fallen, zeige ich, dass sie mit Hilfe von ILP (Integer Linear Programming) in überschaubarer Zeit gelöst werden können. In dieser Arbeit werden ILP-Ansätze für alle darin diskutierten Problemstellungen beschrieben sowie eine Implementierung im Software Paket PDA bereitgestellt.
Abstract
(Englisch)
In the recent years phylogenomics opened a new chapter in evolutionary biology. The analysis of the genome-scale data sets has the potential of answering the most difficult and intriguing questions for evolutionary histories. However, such perspectives come with a higher complexity and difficulties for the phylogenomic inference. The focus of this thesis is exploring and providing insights into some of the questions arisen from theory, algorithms and applications of phylogenomics.
The main contributions of the thesis deal with phylogenetic terraces, which represent sets of species trees in tree space with identical score (likelihood or parsimony).
Firstly, we provide the rules to detect terraces during the tree search. To this end we study the induced partition trees and how topological rearrangements on species tree drive changes on partition trees. If the tree rearrangement operation applied to the current species tree does not change any of its associated induced partition trees, then the current and a new species trees belong to one terrace. We proof three propositions defining the rules when Nearest Neighbour Interchange (NNI), Subtree Pruning and Regrafting (SPR) and Tree Bisection and Reconnection (TBR) operations change the induced partition trees. We further generalize the concept of terraces to partial terraces and study their occurrence for real alignments using NNI neighbourhoods.
Secondly, we provide a phylogenetic terrace aware data structure (PTA) for the efficient analysis of concatenated multiple alignments. Using PTA and the rules developed to detect (partial) terraces in the presence of missing data one saves computational time by avoiding unnecessary recomputations. We implemented PTA in IQ-TREE and tested its performance on 11 real alignments. Identification of partial terraces speeded up the tree search with IQ-TREE for up to 5 and 6 times compared to the standard implementation (terrace-unaware) and RAxML, respectively. PTA is suitable for the use with all partition models and all common topological rearrangement operations, such as NNI, SPR and TBR.
Finally, we develop methods for conservation biology and ecology, where phylogenomics is used to quantify the evolutionary diversity of the species. We discuss the viable taxon selection problem, which incorporates predator-prey interactions to define viability constraints. First, we extend the problem to account for Split Diversity (SD), a biodiversity measure, which is based on the evolutionary distances between species on split networks. Second, to make the viability constraints more realistic we extend the viability definition to account for the diet composition of predators. SD with the viability constraints is used to prioritize species for the conservation actions. Though such optimization problems fall into the area of NP-hard problems, it is possible to solve them within reasonable amount of time using Integer Linear Programming (ILP), a well-known method for the decision-making problems. We provide the ILP formulations for all the discussed problems and implement them in the PDA software package. To exemplify the discussed methods we apply them to a real case study – the Caribbean Coral Reef community.
Schlagwörter
Schlagwörter
(Englisch)
phylogenetic terraces partial terraces induced partition trees viable taxon selection split diversity
Schlagwörter
(Deutsch)
phylogenetischer Terrassen partielle Terrassen Partitionen induzierte Bäume die Auswahl überlebensfähiger Taxa Splitdiversität
Autor*innen
Olga Chernomor
Haupttitel (Englisch)
Phylogenomics
Hauptuntertitel (Englisch)
theory, algorithms and applications
Publikationsjahr
2015
Umfangsangabe
X, 85 Seiten : Illustrationen, Diagramme
Sprache
Englisch
Beurteiler*innen
Dirk Metzler ,
Thomas Rattei
AC Nummer
AC12737106
Utheses ID
35380
Studienkennzahl
UA | 794 | 685 | 490 |