Computational and mathematical approaches for statistical sequence alignment and phylogenetic inference on emerging parallel architectures

生物信息学目前面临两大挑战。首先，测序技术的重大进步（454,Solexa）正在产生前所未有的大量分子数据。因此，数据采集不再是一个问题，而是数据分析，特别是在分子进化中。其次，并行计算领域正面临着通用cpu的多核革命和大量的新型加速器技术，如gpu（图形处理单元）。因此，并行计算在个人计算机层面变得可行。然而，存储在公共数据库（例如GenBank）中的生物数据的增长速度明显高于计算能力的增长速度。因此，我们需要从本质上改进各自的模型、数据结构和数据分析算法。在这里，我们建议通过一种集成的方法来解决统计多序列比对（sMSA）和系统发育推断（PI）这两个密切相关且相互交织的领域的这些挑战。我们将为sMSA和PI开发一个高度优化、可移植、并行化和通用的库。我们还将改进sMSA的统计模型，寻找PI的启发式方法，并将它们集成到下一代进化生物学的生物信息学工具中。其基本思想是开发模型和方法，使它们能够在所有现代多核、加速器和超级计算机体系结构上进行扩展。

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.