• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>IEEE/ACM transactions on computational biology and bioinformatics >Merging Partially Labelled Trees:Hardness and a DeclarativeProgramming Solution
【24h】

Merging Partially Labelled Trees:Hardness and a DeclarativeProgramming Solution

机译：合并部分标记的树：硬度和声明性编程解决方案

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

摘要

Intraspecific studies often make use of haplotype networks instead of gene genealogies to represent the evolution of a set of genes. Cassens et al. proposed one such network reconstruction method, based on the global maximum parsimony principle, which was later recast by the first author of the present work as the problem of finding a minimum common supergraph of a set of $t$ partially labelled trees. Although algorithms have been proposed for solving that problem on two graphs, the complexity of the general problem on trees remains unknown. In this paper, we show that the corresponding decision problem is NP-complete for $t=3$. We then propose a declarative programming approach to solving the problem to optimality in practice, as well as a heuristic approach, both based on the idpsystem, and assess the performance of both methods on randomly generated data.
机译：种内研究通常利用单倍型网络而不是基因谱系来代表一组基因的进化。卡森斯等。提出了一种基于全局最大简约原则的网络重构方法，该方法后来被本工作的第一作者改写为发现一组$ t $部分标记树的最小公共上标的问题。尽管已经提出了用于在两个图上解决该问题的算法，但是树上一般问题的复杂性仍然未知。在本文中，我们证明了对于$ t = 3 $，相应的决策问题是NP完全的。然后，我们提出了一种声明式编程方法和一种启发式方法，以在实践中将问题解决到最佳状态，这两种方法都基于idpsystem，并评估了这两种方法在随机生成的数据上的性能。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号