A fixed-parameter algorithm for the maximum agreement forest problem on multifurcating trees  

作　　者：Feng SHI Jianxin WANG Yufei YANG Qilong FENG Weilong LI Jianer CHEN 

机构地区：[1]School of Information Science and Engineering, Central South University [2]Department of Computer Science and Engineering, Texas A&M University, College Station

出　　处：《Science China(Information Sciences)》2016年第1期63-76,共14页中国科学（信息科学）（英文版）

基　　金：supported by National Natural Science Foundation of China(Grant Nos.61232001;61472449;61370172;61420106009);Research Fund for the Doctoral Program of Higher Education of China(Grant No.20130162130001)

摘　　要：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.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.

关 键 词：computational biology multifurcating phylogenetic tree maximum agreement forest TBR dis-tance fixed-parameter algorithm 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]