期刊
JOURNAL OF COMPUTATIONAL BIOLOGY
卷 16, 期 1, 页码 105-117出版社
MARY ANN LIEBERT, INC
DOI: 10.1089/cmb.2008.0084
关键词
coevolution; cophylogeny; computational complexity; NP-completeness
类别
资金
- School of Information Technology at the University of Sydney, Australia
- Mellon Foundation.
The cophylogeny reconstruction problem is that of finding minimal cost explanations of differences between evolutionary histories of ecologically linked groups of biological organisms. We present a proof that shows that the general problem of reconciling evolutionary histories is NP-complete and provide a sharp boundary where this intractability begins. We also show that a related problem, that of finding Pareto optimal solutions, is NP-hard. As a byproduct of our results, we give a framework by which meta-heuristics can be applied to find good solutions to this problem.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据