Algorithms for the Calculation and Visualisation of Phylogenetic Networks

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.

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.