Efficient algorithms for inverting evolution
Efficient algorithms for inverting evolution
复制标题
逆进化的高效算法
DOI：
--
复制
发表时间：
1996
期刊：
影响因子：
--
通讯作者：
Sampath Kannan
中科院分区：
文献类型：
--
作者：
Martín Farach;Sampath Kannan
进化可以通过作用于物种 DNA 的随机过程进行数学建模。此类模型基于既定理论，即所有现存物种的 DNA 序列或基因组都是通过随机突变和自然选择过程从所有物种共同祖先的基因组衍生而来的。进化的随机模型可用于构建一组物种的系统发育或进化树。最大似然估计 (MLE) 方法寻找最有可能产生所考虑的 DNA 的进化树。虽然这些方法在智力上令人满意，但由于其计算困难性而尚未被广泛接受。在本文中，我们如下解决 MLE 方法的棘手问题。我们引入了进化随机过程模型的度量。我们通过证明为了让任何算法区分根据该度量接近的两个随机模型，需要给出许多观察结果，我们证明了该度量是有意义的。我们用一个简单而有效的算法来补充这个结果，用于反转进化的随机过程，即根据对两种状态特征的观察来构建树。 （我们在后续论文中使用了相同的技术来解决多状态字符的问题，从而从 DNA 序列数据构建一棵树。）在我们的指标中，我们构建的树被证明与生成数据的树很接近，并且随着更多的观察变得可用，我们构建的树会变得更接近。尽管对于寻找最有可能的树的良好近似值的问题提出了许多启发式方法，但我们的算法是第一个具有保证收敛速度的算法，而且该速度在我们建立的下界速度的多项式之内。我们的算法也是第一个被证明可以收敛到正确树的多项式时间算法。罗格斯大学； farach@cs.rutgers.edu； http://www.cs.rutgers.edu/∼farach；得到 NSF 职业发展奖和 Alfred P. Sloan 研究奖学金的支持。宾夕法尼亚大学； kannan@central.cis.upenn.edu； http://www.cis.upenn.edu/∼kannan/home.html；由 NSF CCR 96-19910 和 NSF SGER 9612829 支持
Evolution can be mathematically modelled by a stochastic process that operates on the DNA of species. Such models are based on the established theory that the DNA sequences, or genomes, of all extant species have been derived from the genome of the common ancestor of all species by a process of random mutation and natural selection. A stochastic model of evolution can be used to construct phylogenies, or evolutionary trees, for a set of species. Maximum Likelihood Estimations (MLE) methods seek the evolutionary tree which is most likely to have produced the DNA under consideration. While these methods are intellectually satisfying, they have not been widely accepted because of their computational intractability. In this paper, we address the intractability of MLE methods as follows. We introduce a metric on stochastic process models of evolution. We show that this metric is meaningful by proving that in order for any algorithm to distinguish between two stochatic models that are close according to this metric, it needs to be given many observations. We complement this result with a simple and efficient algorithm for inverting the stochastic process of evolution, that is, for building a tree from observations on two-state characters. (We have used the same techniques in a subsequent paper to solve the problem for multistate characters, and hence for building a tree from DNA sequence data.) The tree we build is provably close, in our metric, to the tree generating the data and gets closer as more observations become available. Though there have been many heuristics suggested for the problem of finding good approximations to the most likely tree, our algorithm is the first one with a guaranteed convergence rate, and further, this rate is within a polynomial of the lower-bound rate we establish. Ours is also the the first polynomial-time algorithm which is proven to converge at all to the correct tree. Rutgers University; farach@cs.rutgers.edu; http://www.cs.rutgers.edu/∼farach; Supported by an NSF Career Advancement Award and an Alfred P. Sloan Research Fellowship. University of Pennsylvania; kannan@central.cis.upenn.edu; http://www.cis.upenn.edu/∼kannan/home.html; Supported by NSF CCR 96-19910 and NSF SGER 9612829