Algorithms for the Calculation and Visualisation of Phylogenetic Networks

DSpace Repository

Show simple item record

dc.contributor.advisor Huson, Daniel (Prof.) de_DE
dc.contributor.author Kloepper, Tobias Heinz de_DE
dc.date.accessioned 2008-05-02 de_DE
dc.date.accessioned 2014-03-18T10:18:38Z
dc.date.available 2008-05-02 de_DE
dc.date.available 2014-03-18T10:18:38Z
dc.date.issued 2008 de_DE
dc.identifier.other 279675755 de_DE
dc.identifier.uri http://nbn-resolving.de/urn:nbn:de:bsz:21-opus-33360 de_DE
dc.identifier.uri http://hdl.handle.net/10900/49159
dc.description.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 modeled using phylogenetic trees. However, if the evolutionary model is generalized by integrating events such as recombination, a tree can no longer describe the process. Phylogenetic networks 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 reconstruction 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 possibility 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 consideration, 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. In addition, we developed an algorithm that is capable of drawing explicit 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 the availability of new phylogenetic methods within SplitsTree and increasing the useablility of large phylogenetic graphs. In the first project, we implemented 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. en
dc.description.abstract Die Evolutionstheorie beschreibt die Entwicklung der Arten als einen stetigen Prozess der Anpassung an die Umwelt. Im klassischen Modell entwickelt sich eine Spezies durch Mutationen und Speziation weiter. Diese Ereignisse lassen sich durch phylogenetische Bäume darstellen. Wird das evolutionäre Modell jedoch um Ereignisse, wie zum Beispiel Rekombination, erweitert kann dieses nicht mehr anhand eines Baumes dargestellt werden. Phylogenetische Netzwerke sind eine Klasse von Graphen, welche entwickelt wurden, um diese zusätzlichen Ereignisse zu modellieren. Diese Netzwerke können in zwei Klassen unterteilt werden: die expliziten Netzwerke, welche die evolutionären Abläufe direkt modellieren und die impliziten Netzwerke, welche nicht direkt die evolutionären Abläufe modellieren, sondern die von den Abläufen erzeugten Signale. Gegenstand dieser Arbeit ist die Entwicklung von neuen Algorithmen zur Rekonstruktion und Visualisierung von expliziten phylogenetischen Netzwerken. Dabei wird eine Lösung bei der Rekonstruktion als optimal angesehen, wenn sie den evolutionären Aufwand minimiert. Ein Problem, welches bei der Rekonstruktion dieser Netzwerke auftritt, ist die hohe Anzahl an möglichen Graphen, von welchen gewählt werden kann, um eine optimale Lösung zu erhalten, und daß es keine Möglichkeit gibt, diese Wahl effizient zu gestalten. Ein Weg die Anzahl von Graphen, welche betrachtet werden müssen dennoch zu reduzieren, ist die Zerlegung des Problems in kleine voneinander unabhängige Einheiten. Durch eine intelligente Reduzierung der betrachteten Graphenklasse, konnte gezeigt werden, daß eine eindeutige Zerlegung des Problems in unabhängige Teilprobleme möglich ist. Desweiteren wurde ein effizienter Algorithmus entwickelt, welcher die Berechnung der optimalen Lösungen für die unabhängigen Teilprobleme ermöglicht. Außerdem wurde ein Algorithmus entwickelt, welcher es erlaubt, explizite phylogenetische Netzwerke zu zeichnen. Die Entwicklung des Algorithmus wurde so gestaltet, daß vorhandene Algorithmen zur Visualisierung von phylogenetischen Bäumen erweitert werden. Hierzu wird eine Modifizierung des phylogenetischen Netzwerks durchgeführt und eine Optimierung zur Minimierung sich ü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 für Plugins entwickelt, welches erlaubt, eine installierte Software nachträglich mit neuen Methoden (Plugins) zu erweitern. In dem zweiten Projekt wurde eine Software entwickelt, welche phylogenetische Graphen mit zusätzlichen Informationen zu annotieren erlaubt. de_DE
dc.language.iso en de_DE
dc.publisher Universität Tübingen de_DE
dc.rights ubt-podok de_DE
dc.rights.uri http://tobias-lib.uni-tuebingen.de/doku/lic_mit_pod.php?la=de de_DE
dc.rights.uri http://tobias-lib.uni-tuebingen.de/doku/lic_mit_pod.php?la=en en
dc.subject.classification Bioinformatik de_DE
dc.subject.ddc 004 de_DE
dc.subject.other Phylogenie de_DE
dc.subject.other Phylogeny , Phylogenetic networks , Evolutionary biology en
dc.title Algorithms for the Calculation and Visualisation of Phylogenetic Networks en
dc.title Algorithmen zur Berechnung und Visualisierung von Phylogenetischen Netzwerken de_DE
dc.type Dissertation de_DE
dc.date.updated 2008-05-02 de_DE
dcterms.dateAccepted 2008-05-02 de_DE
utue.publikation.fachbereich Informatik de_DE
utue.publikation.fakultaet 7 Mathematisch-Naturwissenschaftliche Fakultät de_DE
dcterms.DCMIType Text de_DE
utue.publikation.typ doctoralThesis de_DE
utue.opus.id 3336 de_DE
thesis.grantor 17 Fakultät für Informations- und Kognitionswissenschaften de_DE

Dateien:
Aufrufstatistik

This item appears in the following Collection(s)

Show simple item record