Treffer: Distributed and Parallel Algorithms and Systems for Inference of Huge Phylogenetic Trees based on the Maximum Likelihood Method ; Verteilte und Parallele Algorithmen und Systeme zur Berechnung grosser phylogenetischer Baeume anhand der Maximum Likelihood Methode

The computation of large phylogenetic (evolutionary) trees from DNA sequence data based on the maximum likelihood criterion is most probably NP-complete. Furthermore, the computation of the likelihood value for one single potential tree topology is computationally intensive. This thesis introduces a number of algorithmic and technical solutions which for the first time enable parallel inference of large phylogenetic trees comprising up to 10.000 organisms with maximum likelihood. The algorithmic part includes a technique to accelerate the computation of likelihood values, as well as novel search-space heuristics which significantly accelerate the tree inference process and yield better final trees at the same time. The technical part covers technical solutions for the acquisition of the enormous amount of required computational resources such as parallel MPI-based and distributed seti@home-like implementations of the basic sequential algorithm. Finally, the program has been used to compute a biologically significant initial small "tree of life" containing 10.000 representative organisms from the three domains: Bacteria, Eukarya, and Archaea based on data from the ARB database. ; Die Berechnung grosser Stammbäume aus Alignments von DNA-Sequenzdaten anhand des Maximum-Likelihood Verfahrens ist höchstwahrscheinlich NP-Vollständig. Im Rahmen dieser Arbeit wurden neue Algorithmen entwickelt, welche wesentlich zur Beschleunigung der Berechnungen und gleichzeitigen Verbesserung der Endergebnisse beitragen. Diese Ideen wurden im sequentiellen Programm RAxML implementiert, welches als Open Source Code zur Verfügung gestellt wird. Weiterhin wurde eine Vielzahl paralleler und verteilter technischer Lösungen konzipiert, welche die Bereitstellung der benötigten Rechenleistung zur Berechnung sehr grosser Bäume ermöglichen. Das sequentielle Programm RAxML ist derzeit eine der schnellsten und exaktsesten Implementierungen zur Stammbaumberechnung anhand realer Daten. Die parallele Version wurde benutzt, um den derzeit grössten, ...