Parallele Datenverarbeitung zu Stammbaumrekonstruktion

Bioinformatics is currently facing two challenges. Firstly, significant advances in sequencing techniques (454, Solexa) are generating an unprecedented amount of molecular data. Hence, data acquisition is no longer a problem but rather data analysis, especially in molecular evolution. Secondly, the field of parallel computing is facing the multi-core revolution on general purpose CPUs and a plethora of novel accelerator technologies such as GPUs (Graphics Processing Units). Therefore, parallel computing is becoming feasible at the level of personal computers. Nevertheless, biological data stored in public databases (e.g., GenBank) increases at a significantly higher rate than computational power. Thus, we need to substantially improve the respective models, data structures, and algorithms for data analysis. Here, we propose to tackle these challenges for the two closely related and intertwined fields of Statistical Multiple Sequence Alignment (sMSA) and Phylogenetic Inference (PI) via an integrated approach. We will develop a highly optimized, portable, parallelized, and versatile library for sMSA and PI. We will also improve statistical models for sMSA, search heuristics for PI, and integrate them in a next-generation bioinformatics tool for evolutionary biology. The underlying idea is to develop models and methods in such a way that they will be scalable on all modern multi-core, accelerator, and supercomputer architectures.

Im Rahmen der Fördermaßnahme wurden drei Ziele erreicht. Wir stellen eine open-source Library für phylogenetische Analysen basierend auf dem Maximum Likelihodd Prinzip zur Verfügung. Diese Library ist soweit optimiert, dass sie für paralleles Rechnen verwendet werden kann und dass sie wenig Rechenzeit benötigt. Diese Arbeiten wurden gemeinsam mit unserem Kollaborationspartner Alexandors Stamatakis (Heidelberg/Karlsruhe) durchgeführt. Zweitens, haben wir mit IQ-TREE einen neuartigen und extrem effizienten Algorithmus entwickelt, der es erlaubt phylogenetische Bäume aus DNA oder Aminosäuresequenzen in sehr kurzer Zeit zu berechnen. In IQ-TREE ist auch ein neuartiges Verfahren (UFBoot) zur Schätzung der Verlässlichkeit der geschätzten Stammbäume integriert worden, dass die Rechenzeit nochmals senkt. Damit ist IQ-TREE ein wichtiges Werkzeug für alle Labore, die sich mit evolutionsbiologischen Fragestellungen befassen. Im dritten Teil des Projekts wurde in Zusammenarbeit mit Dirk Metzler (München) ein Verfahren entwickelt, um die Unsicherheiten in multiplen Sequenz Alignments zu studieren. Grundlage für dieses Verfahren ist ein detailliertes Modell der Sequenzevolution.