Accelerated likelihood surface exploration: The likelihood ratchet
Accelerated likelihood surface exploration: The likelihood ratchet
复制标题
DOI：
10.1080/10635150390196993
复制
发表时间：
2003-06-01
影响因子：
6.5
通讯作者：
Vos, RA
中科院分区：
文献类型：
--
作者：
Vos, RA
多重似然最大值的存在要求算法探索大部分树空间。然而，由于计算的限制，基于逐步加法的树搜索方法不允许在合理的时间内进行这种探索。在这里，我提出了一种算法，可以提高探索可能性景观的速度。该迭代算法将基于距离的树构造方法的计算速度与基于最优性准则的分支交换方法的精度相结合，以改善起始树的结果。该算法通过对底层序列数据集随机抽取的样本进行重新加权，迭代地扰动树木景观，从而在局部最优点之间移动。在模拟和真实数据集上的测试表明，使用本文提出的算法可以更快地找到基于逐步加法的启发式搜索得到的最优解。对先前发布的在最大似然条件下确定存在树岛的数据集进行的测试表明，该算法在比使用逐步加法所需的时间更短的时间内识别相同的树岛。该算法可以很容易地应用于系统发育推理的标准软件。
The existence of multiple likelihood maxima necessitates algorithms that explore a large part of the tree space. However, because of computational constraints, stepwise addition-based tree-searching methods do not allow for this exploration in reasonable time. Here, I present an algorithm that increases the speed at which the likelihood landscape can be explored. The iterative algorithm combines the computational speed of distance-based tree construction methods to arrive at approximations of the global optimum with the accuracy of optimality criterion based branch-swapping methods to improve on the result of the starting tree. The algorithm moves between local optima by iteratively perturbing the tree landscape through a process of reweighting randomly drawn samples of the underlying sequence data set. Tests on simulated and real data sets demonstrated that the optimal solution obtained using stepwise addition-based heuristic searches was found faster using the algorithm presented here. Tests on a previously published data set that established the presence of tree islands under maximum likelihood demonstrated that the algorithm identifies the same tree islands in a shorter amount of time than that needed using stepwise addition. The algorithm can be readily applied using standard software for phylogenetic inference.