Incomplete Directed Perfect Phylogeny
Incomplete Directed Perfect Phylogeny
复制标题
不完全定向完美系统发育
DOI：
10.1007/3-540-45123-4_14
复制
发表时间：
2000
期刊：
影响因子：
--
通讯作者：
R. Sharan
中科院分区：
文献类型：
--
作者：
I. Pe’er;R. Shamir;R. Sharan
完美进化是研究进化的基本模型之一。我们研究以下问题的推广：输入是一个物种字符矩阵。字符是二进制的，并且是有向的，即，一个物种只能获得特征与标准的完全同源性的区别在于，对于某些物种，某些性状的状态是未知的。问题是，人们是否能以一种承认完美的遗传的方式来完成缺失的状态。这个问题出现在经典的系统发育研究中，当一些状态缺失或未确定时。最近，一些研究使用DNA中插入的重复元件来推断基因突变，也引起了同样的问题。最著名的算法的问题需要O（n2m）的时间为m字符和n物种。我们提供了一个接近最优的O（nm）时间算法的问题。
Perfect phylogeny is one of the fundamental models for studying evolution. We investigate the following generalization of the problem: The input is a species-characters matrix. The characters are binary and directed, i.e., a species can only gain characters. The difference from standard perfect phylogeny is that for some species the state of some characters is unknown. The question is whether one can complete the missing states in a way admitting a perfect phylogeny. The problem arises in classical phylogenetic studies, when some states are missing or undetermined. Quite recently, studies that infer phylogenies using inserted repeat elements in DNA gave rise to the same problem. The best known algorithm for the problem requires O(n2m) time for m characters and n species. We provide a near optimal O(nm)-time algorithm for the problem.