Computing the minimum number of hybridization events for a consistent evolutionary history
Computing the minimum number of hybridization events for a consistent evolutionary history
复制标题
DOI：
10.1016/j.dam.2006.08.008
复制
发表时间：
2007-04-15
影响因子：
1.1
通讯作者：
Semple, Charles
中科院分区：
文献类型：
--
作者：
Bordewich, Magnus;Semple, Charles
现在有充分的证据表明，一组现代物种之间的进化关系结构不一定是树状的。这样做的原因是，像杂交这样的网状事件意味着物种是来自不同祖先的基因的混合。由于这样的事件相对罕见，生物学家的一个基本问题是确定解释单一(杂交)系统发展史中给定(输入)数据集所需的最小杂交事件数量。本文的主要结果表明，计算这个最小数是APX困难的，因此是NP困难的，在输入是现代物种集合上的系统发育树的情况下。这回答了最近一次会议(乌普萨拉大学，2004年)上提出的一个问题。作为这些结果的结果，我们还纠正了以前发表的一个NP硬度证明，在输入是二进制序列的集合的情况下，其中每个序列代表特定当前物种的属性。这些问题的APX难度意味着，不太可能有一个有效的算法来精确计算结果或将其逼近到任意精度。(C)2006爱思唯尔B.V.保留所有权利。
It is now well-documented that the structure of evolutionary relationships between a set of present-day species is not necessarily tree-like. The reason for this is that reticulation events such as hybridizations mean that species are a mixture of genes from different ancestors. Since such events are relatively rare, a fundamental problem for biologists is to determine the smallest number of hybridization events required to explain a given (input) set of data in a single (hybrid) phylogeny. The main results of this paper show that computing this smallest number is APX-hard, and thus NP-hard, in the case the input is a collection of phylogenetic trees on sets of present-day species. This answers a problem which was raised at a recent conference (Phylogenetic Combinatorics and Applications, Uppsala University, 2004). As a consequence of these results, we also correct a previously published NP-hardness proof in the case the input is a collection of binary sequences, where each sequence represents the attributes of a particular present-day species. The APX-hardness of these problems means that it is unlikely that there is an efficient algorithm for either computing the result exactly or approximating it to any arbitrary degree of accuracy. (C) 2006 Elsevier B.V. All rights reserved.