A fixed-parameter algorithm for the maximum agreement forest problem on multifurcating trees
A fixed-parameter algorithm for the maximum agreement forest problem on multifurcating trees
复制标题
多叉树最大一致性森林问题的固定参数算法
DOI：
10.1007/s11432-015-5355-1
复制
发表时间：
2016
影响因子：
8.8
通讯作者：
Jianer Chen
中科院分区：
文献类型：
--
作者：
Feng Shi;Jianxin Wang;Yufei Yang;Qilong Feng;Weilong Li;Jianer Chen
The Maximum Agreement Forest (MAF) problem on two given phylogenetic trees is an important NP-hard problem in the field of computational biology. In this paper, we study the parameterized version of the MAF problem: given two unrooted (multifurcating) phylogenetic trees T1 and T2 with the same leaf-label set L, and a parameter k, either construct an agreement forest of at most k trees for T1 and T2, or report that no such a forest exists. Whether there is a fixed-parameter tractable algorithm for this problem was posed as an open problem several times in the literature. In this paper, we resolve this open problem by presenting a parameterized algorithm of running time O(4kn5) for the problem.
