Models, Algorithms, and High Performance Computing for Phylogenetic Inference: Towards Simultaneous Alignment and Tree Building with Maximum Likelihood

用于系统发育推断的最大似然(ML)标准已被反复证明是最准确的系统发育重建模型之一。最近在搜索算法和高性能计算方面的进步导致了基于ML的新一代系统发育推断程序的出现，这些程序可以很好地扩展到数千个分类群。因此，现在可以解决新的挑战：目前的系统发育分析是基于使用传统比对工具对分子序列进行固定的输入比对。然而，随着问题规模的增大，比对变化对系统发育分析的影响变得更加显著。因此，需要能够同时优化树拓扑和比对的新程序。一些现有的程序允许同时构建和比对树，但它们只能用于非常小的问题。因此，拟议项目的一个主要目标将是设计、实现和并行化模型和算法，以便在ML下大规模同时构建和比对树。将使用两种替代方法来应对这一挑战：直接在RAxML(作者的ML推理软件，目前是实现这一目的最快的软件)中实现，以及迭代对齐改进/树构建方法。第二个主要目标是设计算法来更快地计算支持值和ML树搜索，并开发用于多基因比对的改进模型。次要研究领域涉及大量合作项目，包括具有挑战性的真实数据分析、系统发生学中的方法论研究，以及对新兴并行体系结构的应用驱动研究。

The Maximum Likelihood (ML) criterion for phylogenetic inference [17] has repeatedly been shown to be one of the most accurate models for phylogeny reconstruction. Recent advances in search algorithms and high-performance computing have lead to a new generation of programs for ML–based phylogenetic inference that scale well up to several thousand taxa. Thus, new challenges can now be tackled: Current phylogenetic analyses are based on a fixed input alignment of molecular sequences using conventional alignment tools. However, the impact of alignment variations on phylogenetic analyses grows more significant as the size of the problem increases. Thus, novel programs are required that are capable of optimizing the tree topology and the alignment simultaneously. A handful of existing programs allow for simultaneous tree building and alignment, but they can be used only on very small problems. Thus, one main goal of the proposed project will be to devise, implement, and parallelize models and algorithms for large-scale simultaneous tree building and alignment under ML. Two alternative approaches will be used to tackle this challenge: a direct implementation in RAxML (the author’s ML inference software, currently the fastest for this purpose), and an iterative alignment-improvement/tree-building approach. The second major goal is to devise algorithms for faster computation of support values and ML tree searches, and to develop improved models for multi–gene alignments. A secondary line of research deals with a large number of collaborative projects, including challenging real–data analyses, methodological studies in phylogenetics, and application–driven research on emerging parallel architectures.