Parallel computing for phylogenetic inference

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.

During the funding phase of the project we have attained three main goals. First, we developed and made available as open-source code a highly optimized and parallelized phylogenetic likelihood library (PLL) that is already being adopted by the phylogenetics community and has been integrated into respective tools. This was joined work with Alexandros Stamatakis (Heidelberg). Secondly, we introduced IQ-TREE, a fast and effective stochastic algorithm to infer ML trees and an ultrafast approximation for the phylogenetic bootstrap (UFBoot). Both tools were developed by the Austrian sub-project. Third, the sub project headed by Dirk Metzler (Munich) implemented functions for sampling multiple sequence alignments from their joint posterior probability distribution under an explicit model of sequence evolution.