A robust model for finding optimal evolutionary trees
A robust model for finding optimal evolutionary trees
复制标题
DOI：
10.1145/167088.167132
复制
发表时间：
1993-06
期刊：
影响因子：
--
通讯作者：
Martín Farach-Colton;Sampath Kannan;T. Warnow
中科院分区：
文献类型：
--
作者：
Martín Farach-Colton;Sampath Kannan;T. Warnow
为物种集建造进化树是计算生物学中的一个基本问题。其中一个标准模型假定能够计算每对物种之间的距离，并试图找到一个边缘加权的风程，其中在树中距离的ij t距离叶子之间的距离与物种相对应的叶子与观察到的距离完全等于所观察到的距离， D IJ。当存在这样的树时，这在生物学文献中表达了距离函数或矩阵的addivate，并且树木可以从添加距离矩阵In0（n 2）时间构造。真实的距离数据几乎是任何增添的，因此我们需要建模寻找最佳拟合树作为优化问题的问题。
Constructing evolutionary trees for species sets is a fundamental problem in computational biology. One of the standard models assumes the ability to compute distances between every pair of species, and seeks to find an edge-weighted treeT in which the distanced ij T in the tree between the leaves ofT corresponding to the speciesi andj exactly equals the observed distance,d ij . When such a tree exists, this is expressed in the biological literature by saying that the distance function or matrix isadditive, and trees can be constructed from additive distance matrices in0(n 2) time. Real distance data is hardly ever additive, and we therefore need ways of modeling the problem of finding the best-fit tree as an optimization problem.