On simulated annealing phase transitions in phylogeny reconstruction.
On simulated annealing phase transitions in phylogeny reconstruction.
复制标题
DOI：
10.1016/j.ympev.2016.05.001
复制
发表时间：
2016-08
影响因子：
4.1
通讯作者：
Barker D
中科院分区：
文献类型：
--
作者：
Strobl MAR;Barker D
系统发育中模拟退火启发式搜索的综合研究。34个真实世界多重对准的比热和相变研究。每个多重对准产生一个独特的特定的热分布。特定的热分布将对算法优化具有诊断价值。基于全局准则的系统发育重建是np完全或np困难的，因此通常需要启发式搜索。我们研究了强大的，物理启发的，通用的启发式模拟退火，应用于系统发育重建。模拟退火模拟了物理退火过程，其中液体被轻轻冷却以形成晶体。在搜索过程中，会出现比热升高的时期，类似于物理相变。这些模拟退火相变在搜索结果中起着至关重要的作用。然而，对于系统发育或其他优化问题，它们得到的关注相对较少。我们分析了在搜索34个真实世界多重比对的最佳系统发育树时的模拟退火相变。以同样的方式，在熔化温度不同的材料，我们观察到不同的特定的热分布为每个输入文件。我们认为这反映了搜索领域的差异，可以作为问题难度和算法参数适用性的衡量标准。我们讨论了算法优化中的应用，并作为一种诊断方法，在计算成本高昂的大型系统发育重建启动之前评估参数化。虽然这里的重点在于最大限度地简化下的系统发育重建，但似乎我们的结果更广泛地适用于科学和工业中的优化程序。
Comprehensive study of the simulated annealing heuristic search in phylogeny. Investigation of specific heat and phase transitions for 34 real world multiple alignments. Each multiple alignment produces a unique specific heat profile. Specific heat profiles will have diagnostic value for algorithmic optimisation. Phylogeny reconstruction with global criteria is NP-complete or NP-hard, hence in general requires a heuristic search. We investigate the powerful, physically inspired, general-purpose heuristic simulated annealing, applied to phylogeny reconstruction. Simulated annealing mimics the physical process of annealing, where a liquid is gently cooled to form a crystal. During the search, periods of elevated specific heat occur, analogous to physical phase transitions. These simulated annealing phase transitions play a crucial role in the outcome of the search. Nevertheless, they have received comparably little attention, for phylogeny or other optimisation problems. We analyse simulated annealing phase transitions during searches for the optimal phylogenetic tree for 34 real-world multiple alignments. In the same way in which melting temperatures differ between materials, we observe distinct specific heat profiles for each input file. We propose this reflects differences in the search landscape and can serve as a measure for problem difficulty and for suitability of the algorithm’s parameters. We discuss application in algorithmic optimisation and as a diagnostic to assess parameterisation before computationally costly, large phylogeny reconstructions are launched. Whilst the focus here lies on phylogeny reconstruction under maximum parsimony, it is plausible that our results are more widely applicable to optimisation procedures in science and industry.