A mixed integer linear programming model to reconstruct phylogenies from single nucleotide polymorphism haplotypes under the maximum parsimony criterion
A mixed integer linear programming model to reconstruct phylogenies from single nucleotide polymorphism haplotypes under the maximum parsimony criterion
复制标题
DOI：
10.1186/1748-7188-8-3
复制
发表时间：
2013-01-23
影响因子：
1
通讯作者：
Schwartz, Russell
中科院分区：
文献类型：
--
作者：
Catanzaro, Daniele;Ravi, Ramamoorthi;Schwartz, Russell
背景：近年来，由于比对单倍型序列的系统发育估计在许多精细遗传数据分析中的重要性，它引起了越来越多的关注。其应用领域涵盖医学研究、药物发现、流行病学和人口动态。分子系统发育学文献提出了许多从合理的替代方案中选择系统发育的标准。通常，这样的标准可以通过目标函数来表达，并且优化它们的系统发育被称为最优的。最重要的估计标准之一是简约性，它规定一组公共可变位点上的 n 个单倍型序列的集合 H 的最佳系统发育 T* 满足以下要求：（i）它具有最短的长度，并且（ii）对于每对不同的单倍型 hi，hj 是 H 的一个元素，属于 T* 中从 hi 到 hj 的路径的边权重之和不小于观察到的hi 和 hj 之间的变化次数。寻找 H 的最简约的系统发育涉及到解决一个优化问题，称为最简约的系统发育估计问题 (MPPEP)，该问题在许多版本中都是 NP 困难的。 结果：在本文中，我们研究了 MPPEP 的最新版本，当输入数据由从共同基因组区域的个体群体中提取的单核苷酸多态性单倍型组成时，就会出现该版本。具体来说，我们探索了改进先前工作中使用的隐式枚举策略的前景，使用一种新颖的问题表述和一系列强化有效不等式和初步对称性破缺约束，以更精确地限制解空间并加速可能的最佳系统发育的隐式枚举。我们提出基本公式，然后引入一系列可证明的有效约束来减少解决方案空间。然后，我们证明这些约束通常可以导致最优解与其非整数线性规划界限之间的差距相对于现有技术显着减小，并且通常可以显着更快地处理中等困难的问题实例。结论：我们提供了这种最优枚举方法可能可行的条件的指示，表明这些策略可用于相对大量的分类单元，尽管对可变位点的数量有更严格的限制。因此，这项工作提供了适合某些难以证明所有先前方法的较困难实例的最佳解决方案的方法。
Background: Phylogeny estimation from aligned haplotype sequences has attracted more and more attention in the recent years due to its importance in analysis of many fine-scale genetic data. Its application fields range from medical research, to drug discovery, to epidemiology, to population dynamics. The literature on molecular phylogenetics proposes a number of criteria for selecting a phylogeny from among plausible alternatives. Usually, such criteria can be expressed by means of objective functions, and the phylogenies that optimize them are referred to as optimal. One of the most important estimation criteria is the parsimony which states that the optimal phylogeny T* for a set H of n haplotype sequences over a common set of variable loci is the one that satisfies the following requirements: (i) it has the shortest length and (ii) it is such that, for each pair of distinct haplotypes hi, hj is an element of H, the sum of the edge weights belonging to the path from hi to hj in T* is not smaller than the observed number of changes between hi and hj. Finding the most parsimonious phylogeny for H involves solving an optimization problem, called the Most Parsimonious Phylogeny Estimation Problem (MPPEP), which isNP-hard in many of its versions.Results: In this article we investigate a recent version of the MPPEP that arises when input data consist of single nucleotide polymorphism haplotypes extracted from a population of individuals on a common genomic region. Specifically, we explore the prospects for improving on the implicit enumeration strategy of implicit enumeration strategy used in previous work using a novel problem formulation and a series of strengthening valid inequalities and preliminary symmetry breaking constraints to more precisely bound the solution space and accelerate implicit enumeration of possible optimal phylogenies. We present the basic formulation and then introduce a series of provable valid constraints to reduce the solution space. We then prove that these constraints can often lead to significant reductions in the gap between the optimal solution and its non-integral linear programming bound relative to the prior art as well as often substantially faster processing of moderately hard problem instances.Conclusion: We provide an indication of the conditions under which such an optimal enumeration approach is likely to be feasible, suggesting that these strategies are usable for relatively large numbers of taxa, although with stricter limits on numbers of variable sites. The work thus provides methodology suitable for provably optimal solution of some harder instances that resist all prior approaches.