...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Discrete Applied Mathematics >New results on optimizing rooted triplets consistency
【24h】

New results on optimizing rooted triplets consistency

机译：优化生根三胞胎一致性的新结果

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

摘要

A set of phylogenetic trees with overlapping leaf sets is consistent if it can be merged without conflicts into a supertree. In this paper, we study the polynomial-time approximability of two related optimization problems called the maximum rooted triplets consistency problem (MAxRTC) and the minimum rooted triplets inconsistency problem (MINRTI) in which the input is a set R of rooted triplets, and where the objectives are to find a largest cardinality subset of R which is consistent and a smallest cardinality subset of R whose removal from R results in a consistent set, respectively. We first show that a simple modification to Wu's Best-Pair-Merge-First heuristic Wu (2004) [38] results in a bottom-up-based 3-approximation algorithm for MAxRTC. We then demonstrate how any approximation algorithm for MINRTI could be used to approximate MAxRTC, and thus obtain the first polynomial-time approximation algorithm for MAxRTC with approximation ratio less than 3. Next, we prove that for a set of rooted triplets generated under a uniform random model, the maximum fraction of triplets which can be consistent with any phylogenetic tree is approximately one third. We then provide a deterministic construction of a triplet set having a similar property which is subsequently used to prove that both MAxRTC and MINRTI are NP-hard even if restricted to minimally dense instances. Finally, we prove that unless P = NP, MINRTI cannot be approximated within a ratio of c . ln n for some constant c > 0 in polynomial time, where n denotes the cardinality of the leaf label set of R.
机译：如果可以将它们合并而不会冲突成为超级树，则具有重叠叶集的一组系统发育树就是一致的。在本文中，我们研究了两个相关的优化问题的多项式时间逼近度，这两个问题是最大根三元组一致性问题（MAxRTC）和最小根三元组不一致问题（MINRTI），其中输入是一组根三元组R目的是分别找到R的最大基数子集和R的最小基数子集。我们首先表明，对Wu的“最佳-对-合并-优先”启发式法Wu（2004）[38]的简单修改导致针对MAxRTC的基于自底向上的3近似算法。然后，我们演示如何将MINRTI的任何近似算法用于近似MAxRTC，从而获得近似比小于3的MAxRTC的第一个多项式时间近似算法。接下来，我们证明对于在均匀条件下生成的一组三重根在随机模型中，可以与任何系统发育树一致的三元组的最大分数约为三分之一。然后，我们提供具有相似属性的三元组的确定性构造，随后将其用于证明MAxRTC和MINRTI都是NP硬的，即使仅限于最小密度的实例。最后，我们证明除非P = NP，否则MINRTI不能在c的比率内近似。在多项式时间内某个常数c> 0的ln n中，其中n表示R的叶子标签集的基数。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号