Generalized Buneman Pruning for Inferring the Most Parsimonious Multi-State Phylogeny
Generalized Buneman Pruning for Inferring the Most Parsimonious Multi-State Phylogeny
复制标题
DOI：
10.1089/cmb.2010.0254
复制
发表时间：
2011-03-01
影响因子：
1.7
通讯作者：
Schwartz, Russell
中科院分区：
文献类型：
--
作者：
Misra, Navodit;Blelloch, Guy;Schwartz, Russell
精确重建基因组仍然是进化生物学的一个关键挑战。这个问题的大多数生物学上合理的公式形式上都是NP难的，没有已知的有效解。实践中的标准是快速的启发式方法，经验上已知这些方法通常工作得很好，但可能产生任意远离最优的结果。实用的精确方法，它产生指数最坏情况下的运行时间，但通常更好的时间在实践中，提供了一个重要的替代方案。我们报告在这个方向上的进展，通过引入一个可证明的最佳方法的加权多状态最大简约遗传问题。该方法是基于推广的布尼曼图的概念，有效的二进制序列的精确方法的建设关键，以便适用于序列与任意有限数量的状态与任意状态转移权重。我们实现了一个整数线性规划（ILP）的多状态问题的方法，使用这个广义的Buneman图，并证明了所得到的方法是能够解决的数据集，是棘手的先前的精确方法在运行时间与流行的算法。我们进一步表明，在一组难度较小的问题实例中，ILP方法导致平均情况下的运行时间大幅减少，相对于中等难度问题的领先的解决方案。我们的工作提供了第一种方法，可证明最佳的最大简约遗传推理，是实用的多状态数据集的几个字符。
Accurate reconstruction of phylogenies remains a key challenge in evolutionary biology. Most biologically plausible formulations of the problem are formally NP-hard, with no known efficient solution. The standard in practice are fast heuristic methods that are empirically known to work very well in general, but can yield results arbitrarily far from optimal. Practical exact methods, which yield exponential worst-case running times but generally much better times in practice, provide an important alternative. We report progress in this direction by introducing a provably optimal method for the weighted multi-state maximum parsimony phylogeny problem. The method is based on generalizing the notion of the Buneman graph, a construction key to efficient exact methods for binary sequences, so as to apply to sequences with arbitrary finite numbers of states with arbitrary state transition weights. We implement an integer linear programming (ILP) method for the multi-state problem using this generalized Buneman graph and demonstrate that the resulting method is able to solve data sets that are intractable by prior exact methods in run times comparable with popular heuristics. We further show on a collection of less difficult problem instances that the ILP method leads to large reductions in average-case run times relative to leading heuristics on moderately hard problems. Our work provides the first method for provably optimal maximum parsimony phylogeny inference that is practical for multi-state data sets of more than a few characters.