A fixed-parameter algorithm for the maximum agreement forest problem on multifurcating trees Academic Article uri icon

abstract

  • 2016, Science China Press and Springer-Verlag Berlin Heidelberg. 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.

published proceedings

  • Science China Information Sciences

author list (cited authors)

  • Shi, F., Wang, J., Yang, Y., Feng, Q., Li, W., & Chen, J.

citation count

  • 2

complete list of authors

  • Shi, Feng||Wang, Jianxin||Yang, Yufei||Feng, Qilong||Li, Weilong||Chen, Jianer

publication date

  • January 2016