Stochastic search strategy for estimation of maximum likelihood phylogenetic trees
Stochastic search strategy for estimation of maximum likelihood phylogenetic trees
复制标题
DOI：
10.1080/106351501750107413
复制
发表时间：
2001-02-01
影响因子：
6.5
通讯作者：
Pearl, DK
中科院分区：
文献类型：
--
作者：
Salter, LA;Pearl, DK
系统发育树构建的最大似然 (ML) 方法不像其他树构建方法（例如简约法、邻接法）那样广泛使用，因为当考虑的序列数量很大时，查找 ML 树所需的时间非常长。为了克服这个困难，我们提出了一种基于模拟退火算法的随机搜索策略来估计 ML 树。该算法的工作原理是通过“局部重排”策略在树空间中移动，以便始终接受提高似然性的拓扑，而接受那些降低似然性的拓扑，其概率与似然性的成比例下降相关。除了大大减少估计 ML 树所需的时间之外，与现有的 ML 树估计算法相比，随机搜索策略不太可能陷入局部最优。我们通过将改进的模拟退火算法与两个现有算法（Swofford 的 PAUP' 和 Felsenstein 的 DAMLK）进行比较，通过几个理论和实际数据示例来证明其成功。
The maximum likelihood (ML) method of phylogenetic tree construction is not as widely used as other tree construction methods (e.g., parsimony, neighbor-joining) because of the prohibitive amount of time required to find the ML tree when the number of sequences under consideration is large. To overcome this difficulty, we propose a stochastic search strategy for estimation of the ML tree that is based on a simulated annealing algorithm. The algorithm works by moving through tree space by way of a "local rearrangement" strategy so that topologies that improve the likelihood are always accepted, whereas those that decrease the likelihood are accepted with a probability that is related to the proportionate decrease in likelihood. Besides greatly reducing the time required to estimate the ML tree, the stochastic search strategy is less likely to become trapped in local optima than are existing algorithms for ML tree estimation. We demonstrate the success of the modified simulated annealing algorithm by comparing it with two existing algorithms (Swofford's PAUP' and Felsenstein's DNAMLK) for several theoretical and real data examples.