Dokument: Phylogenetic Trees from Large Datasets

Titel:Phylogenetic Trees from Large Datasets
URL für Lesezeichen:https://docserv.uni-duesseldorf.de/servlets/DocumentServlet?id=2597
URN (NBN):urn:nbn:de:hbz:061-20030730-000597-4
Kollektion:Dissertationen
Sprache:Englisch
Dokumententyp:Wissenschaftliche Abschlussarbeiten » Dissertation
Medientyp:Text
Autor: Schmidt, Heiko A. [Autor]
Dateien:
[Dateien anzeigen]Adobe PDF
[Details]989,1 KB in einer Datei
[ZIP-Datei erzeugen][PlugIn/Viewer Download]
Dateien vom 09.02.2007 / geändert 09.02.2007
Beitragende:Prof. Dr. Haeseler, Arndt von [Gutachter]
Prof. Dr. Martin, William [Gutachter]
Stichwörter:Stammbaumanalyse, große Datensätze, Quartet Puzzling, Parallelisierung, TREE-PUZZLE, gleichzeitige Analysephylogenetic analysis, large datasets, quartet puzzling, parallel computing, scheduling, TREE-PUZZLE, combined analysis, missing data
Dewey Dezimal-Klassifikation:000 Informatik, Informationswissenschaft, allgemeine Werke » 004 Datenverarbeitung; Informatik
Beschreibungen:Aufgrund effizienter Sequenziertechniken zeigen die Datenbanken für molekulare Sequenzdaten exponentielles Wachstum. Die vorhandenen Datenmengen führen vor allem zu zwei Arten von großen Datensätzen: vertikal groß, d.h. viele Taxa, und horizontal groß, d.h. lange oder viele Sequenzen pro Taxon. Es besteht ein gesteigerter Bedarf an Methoden um solche Datensätze effizient zu analysieren. In der vorliegenden Arbeit wurden, basierend auf dem Quartet Puzzling (QP) Algorithmus, verschiedene Verbesserungen und Methoden zur Analyse solcher Datensätze entwickelt.

Effizienter Puzzling Schritt: Zwei effiziente O(n^4) Algorithmen, ein Split-basierter sowie ein rekursiver Algorithmus, wurden entwickelt, um den sehr zeitintensiven Puzzling Schritt des QP Algorithmus zu beschleunigen. Laufzeitanalysen zeigten, daß diese Algorithmen schneller sind als der ursprüngliche Algorithmus sowie ein MRCA-basierter Algorithmus. Der beste dieser Algorithmen führt zu einer Zeitersparnis von mehr als 50% gegenüben dem ursprünglichen O(n^5) Algorithmus.

Parallelisierung des QP Algorithmus: Um die Laufzeit der Analyse zu verkürzen, wurde eine parallele Version des QP Algorithmus entwickelt und implementiert. Verschiedene Scheduling Algorithmen wurden untersucht, und eine Modifikation des GSS Algorithmus wurde entwickelt, um eine gleichmäßige Auslastung der Arbeitsprozessoren auch in heterogenen Workstation Clustern zu gewährleisten, da es sich hierbei um die häufigste Parallel-Plattform im Bereich der Molekular-Biologie handelt. Laufzeit-Analysen zeigten überzeugende Skalierbarkeit der parallelen Implementierung bei der Analyse großer Datensätze.

Stammbäume mit weniger Quartetten: Der ML-Schritt ist die zweite zeitintensive Komponente des QP Algorithmus. Es wird eine Methode vorgestellt, die durch Aufteilen des Datensatzes in überlappende Teilmengen die Anzahl der benötigten Quartette verringert. Die reduzierten Quartette werden dann mit einem geänderten Puzzling Schritt Algorithmus (ModPUZZLE) zu einem Baum verbunden. Ergebnisse zeigen, dass die Auflösung des Baumes von der Information in Form der benutzten Quartette abhängt sowie dass es mit dieser Methode möglich ist, die grobe Baumstruktur großer Datensätze zu rekonstruieren.

Gleichzeitige Stammbaum-Analyse verschiedener Gene: Eine Methode zur gleichzeitigen Stammbaum-Analyse unterschiedlicher und unvollständiger Gendatensätze wurde entwickelt. Diese Methode kombiniert die phylogenetische Information auf einer datennahen Zwischenebene, wodurch es möglich ist, für die einzelnen Gendatensätze geeignete Evolutionsmodelle zu benutzen sowie den Informationsverlust vor der Kombination zu verringern. Dies sind die Hauptkritikpunkte an Total-Evidence-Methoden einerseits und Supertree-Methoden andererseits. Die entwickelte Methode wurde auf den GPWG-Poaceae-Datensatz angewandt und zeigte Ergebnisse vergleichbar zu denen anderer Methoden zur kombinieren Stammbaum-Analyse.

Efficient sequencing techniques lead to exponentially growing amounts of molecular sequence data resulting mainly in two kinds of large datasets: vertically (large number of taxa) as well as horizontally large datasets (long or many sequences per taxon). The eminent need for efficient methods to analyze such datasets motivated the development and improvement of several approaches based on the Quartet Puzzling (QP) algorithm which were proposed in this thesis.

Accelerated Puzzling Step: Two efficient O(n^4) algorithms, one split-based and a recursive algorithm, were developed to accelerate the puzzling step since it demands a major runtime portion of the tree reconstruction by Quartet Puzzling. Runtime tests show that the new methods outperform the original as well as Berry's algorithm. The best performing algorithm is based on the recursive computation of the edge penalties. It requires about half the runtime of the original O(n^5) algorithm.

Parallelized Quartet Puzzling: To reduce the overall waiting time for the reconstruction of large trees, a parallel implementation was developed. For the parallel workflow several scheduling algorithms were investigated. At last, a GSS-based scheduling algorithm, modified to our needs, was devised to produce an even workload on heterogeneous workstation clusters which are the most abundant parallel platforms in molecular biology. Benchmark tests of the parallel implementation showed convincing scaling behavior for large datasets.

Phylogenetic Trees from Less Quartets: A second component of the QP algorithm which demands a large part of computation time is the ML step. An approach is suggested to reduce the number of required quartets. To that end the dataset is decomposed into overlapping subsets from which the sets of possible quartets are assembled into an overall tree applying a modified puzzling step algorithm called ModPUZZLE. Results show that the resolution one can gain depends on the overlap between the subsets which can be determined by the number of quartets one is willing to compute. The approach can be applied to reconstruct the rough tree topology of large datasets.

Combined Quartet Method for Overlapping Datasets: A method was presented to reconstruct overlapping datasets from different genes (genesets) with missing data. In contrary to total evidence approaches this method combines the datasets on a so-called medium level allowing to use evolutionary parameters specific for each geneset. The combination of the data is performed on the quartet level guided by the likelihoods computed from the sequences. Proceeding this way tries to minimize the loss of primary information before combining the genesets, a common criticism of the supertree methods. Different methods to combine genesets were applied to the biological dataset of the grasses. With regard to the GPWG taxonomic classification of the grasses, the combined quartet method performs comparable to the other methods.

Fachbereich / Einrichtung:Mathematisch- Naturwissenschaftliche Fakultät » WE Informatik
Dokument erstellt am:30.07.2003
Dateien geändert am:12.02.2007
Promotionsantrag am:28.07.2003
Datum der Promotion:28.07.2003
english
Benutzer
Status: Gast
Aktionen