.png){kind=icon}
返回
Computing a Smallest Multilabeled Phylogenetic Tree from Rooted Triplets
.png){kind=icon}
PRE
AI
DOI：10.1109/TCBB.2010.77.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
We investigate the computational complexity of inferring a smallest possible multilabeled phylogenetic tree (MUL tree) which is consistent with each of the rooted triplets in a given set. This problem has not been studied previously in the literature. We prove that even the very restricted case of determining if there exists a MUL tree consistent with the input and having just one leaf duplication is an NP-hard problem. Furthermore, we show that the general minimization problem is difficult to approximate, although a simple polynomial-time approximation algorithm achieves an approximation ratio close to our derived inapproximability bound. Finally, we provide an exact algorithm for the problem running in exponential time and space. As a by-product, we also obtain new, strong inapproximability results for two partitioning problems on directed graphs called ACYCLIC PARTITION and ACYCLIC TREE-PARTITION.
Keyword:
Phylogenetics
MUL tree
rooted triplet
acyclic tree-partition
inapproximability
dynamic programming
AI总结
对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。
期刊
I
IF:
3.4
论文数:
3.3K
被引数:
6.4K
机构
引用论文
.png){kind=icon}
分享收藏分享收藏
查看更多内容