Algorithmen zur Rekonstruktion kophylogenetischer Ereignisse

Authors: 
Wieseke, Nicolas
Year: 
2008
Language: 
German
Abstract in English: 
The problem of reconstructing the common evolutionary development between host- and parasite species has been strongly discussed in research. Hereby a special meaning has been attributed to the complexity of such a calculation. In this thesis an algorithmic approach based on dynamic programming will be introduced, that creates a reconstruction of two phylogenetic genealogical trees and a given mapping of parasites on appropriate hosts. The foundation of this calaculation is an event-driven model of coevolution where costs are assigned to each event. The algorithm searches for reconstructions, which minimize the total costs of all occurred events. A method will be introduced which calculates the event-costs automatically. Therefore a quality rate has been developed, to evaluate different reconstructions concerning the used event-costs. Unlike present approaches genealogical trees with multiple branching nodes can be considered. The described approach has been implemented in a java program named DynamicTreeMap.
Abstract: 
Das Problem der Rekonstruktion einer gemeinsamen evolutionären Entwicklung zwischen Wirts- und Parasitenspezies ist in der Forschung weit diskutiert. Dabei wird der Komplexität einer solchen Berechnung besondere Bedeutung beigemessen. In dieser Arbeit wird ein algorithmischer Ansatz vorgestellt, welcher auf Basis dynamischer Programmierung eine Rekonstruktion zweier phylogenetischer Stammbäume und einer gegebenen Abbildung von Parasiten auf zugehörige Wirte erzeugt. Grundlage dieser Berechnung ist ein ereignis-basiertes Modell der Koevolution, bei dem jedem Ereignis ein Kostenwert zugeordnet ist. Gesucht wird nach Rekonstruktionen, welche die Gesamtkosten der aufgetretenen Ereignisse minimieren. Es wird eine Vorgehensweise vorgestellt, mit welcher sich die Kosten der Ereignisse automatisch berechnen lassen. Dazu wurde ein Gütemaß entwickelt, um verschiedene Rekonstruktionen bezüglich der bei ihrer Berechnung verwendeten Ereigniskostenverteilung bewerten zu können. Im Gegensatz zu bisherigen Arbeiten unterstützt der vorgestellte Ansatz zudem die Verwendung von Stammbäumen mit mehrfach verzweigenden Knoten. Die algorithmischen Überlegungen wurden in einem Javaprogramm namens DynamicTreeMap umgesetzt.
AttachmentSize
Nicolas Wieseke. Algorithmen zur Rekonstruktion kophylogenetischer Ereignisse. Diplomarbeit 2008.6.54 MB
diplomarbeit_nicolas_wieseke.pdf6.54 MB