A structural EM algorithm for phylogenetic inference
A structural EM algorithm for phylogenetic inference
复制标题
DOI：
10.1089/10665270252935494
复制
发表时间：
2002-01-01
影响因子：
1.7
通讯作者：
Pupko, T
中科院分区：
文献类型：
--
作者：
Friedman, N;Ninio, M;Pupko, T
分子进化研究的一个中心任务是根据现有分类群的序列重建系统发育树。最成熟的树重建方法是最大似然（ML）分析。不幸的是，搜索最大似然系统发育树对于大型数据集来说在计算上是令人望而却步的。本文描述了一种利用结构期望最大化（EM）学习最大似然系统发育树的新算法。该算法类似于用于边缘估计的标准EM方法，只是在结构EM算法的迭代过程中，拓扑结构和边缘长度都得到了改进。我们的算法执行两个步骤的迭代。在e步中，我们使用当前的树拓扑和边长度来计算期望的足够统计量，从而总结数据。在m步中，我们搜索一个拓扑，使这些期望的充分统计量的似然最大化。我们表明，与标准的拓扑搜索方法相反，在m步内搜索更好的拓扑可以有效地完成。我们证明了该过程的每次迭代都会增加拓扑的似然性，因此该过程必须收敛。然而，这个收敛点可能不是最优的。为了避免这样的“局部最优”，我们通过加入模拟退火的移动来进一步增强我们的基本EM程序。我们在合成和真实序列数据上对这些新算法进行了评估，结果表明，对于蛋白质序列，即使是我们的基本算法，也比现有的搜索最大似然系统发生的方法找到了更合理的树。此外，我们的算法比这些方法快得多，首次能够在最大似然框架下对大型蛋白质数据集进行系统发育分析。
A central task in the study of molecular evolution is the reconstruction of a phylogenetic tree from sequences of current-day taxa. The most established approach to tree reconstruction is maximum likelihood (ML) analysis. Unfortunately, searching for the maximum likelihood phylogenetic tree is computationally prohibitive for large data sets. In this paper, we describe a new algorithm that uses Structural Expectation Maximization (EM) for learning maximum likelihood phylogenetic trees. This algorithm is similar to the standard EM method for edgelength estimation, except that during iterations of the Structural EM algorithm the topology is improved as well as the edge length. Our algorithm performs iterations of two steps. In the E-step, we use the current tree topology and edge lengths to compute expected sufficient statistics, which summarize the data. In the M-Step, we search for a topology that maximizes the likelihood with respect to these expected sufficient statistics. We show that searching for better topologies inside the M-step can be done efficiently, as opposed to standard methods for topology search. We prove that each iteration of this procedure increases the likelihood of the topology, and thus the procedure must converge. This convergence point, however, can be a suboptimal one. To escape from such "local optima," we further enhance our basic EM procedure by incorporating moves in the flavor of simulated annealing. We evaluate these new algorithms on both synthetic and real sequence data and show that for protein sequences even our basic algorithm finds more plausible trees than existing methods for searching maximum likelihood phylogenies. Furthermore, our algorithms are dramatically faster than such methods, enabling, for the first time, phylogenetic analysis of large protein data sets in the maximum likelihood framework.