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

系统发育推断的最大似然（ML）准则[17]已多次被证明是最准确的系统发育重建模型之一。搜索算法和高性能计算的最新进展导致了新一代基于机器学习的系统发育推断程序，其规模可达数千个分类群。因此，现在可以解决新的挑战：当前的系统发育分析是基于使用常规比对工具的分子序列的固定输入比对。然而，随着问题规模的增加，排列变化对系统发育分析的影响变得更加显著。因此，需要新颖的程序能够同时优化树的拓扑结构和对齐。少数现有的程序允许同时构建和对齐树，但它们只能用于非常小的问题。因此，拟议项目的一个主要目标将是设计、实现和并行化模型和算法，以便在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.