...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Discrete Applied Mathematics >Computing the minimum number of hybridization events for a consistent evolutionary history
【24h】

Computing the minimum number of hybridization events for a consistent evolutionary history

机译：计算一致进化史的最小杂交次数

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

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.
机译：现在有充分的文献证明，一组当今物种之间的进化关系结构不一定是树状的。这是因为网状事件（例如杂交）意味着物种是来自不同祖先的基因的混合物。由于此类事件相对罕见，因此生物学家的基本问题是确定在单个（混合）系统发育中解释给定（输入）数据集所需的最少数量的杂交事件。本文的主要结果表明，如果输入是当前物种集合上的系统发育树的集合，则计算该最小数量是APX困难的，因此是NP困难的。这回答了在最近的一次会议上提出的问题（系统发育组合与应用，乌普萨拉大学，2004年）。这些结果的结果是，在输入是二进制序列的集合的情况下，我们还纠正了以前发布的NP硬度证明，其中每个序列代表当今特定物种的属性。这些问题的APX难度意味着不可能有一种有效的算法来精确计算结果或将结果近似到任意精度。 （C）2006 Elsevier B.V.保留所有权利。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号