Parameterized Algorithms for the Maximum Agreement Forest Problem on Multiple Rooted Multifurcating Trees

Abstract

The Maximum Agreement Forest problem has been extensively studied in phylogenetics. Most previous work is on two binary phylogenetic trees. In this paper, we study a generalized version of the problem: the Maximum Agreement Forest problem on multiple rooted multifurcating phylogenetic trees, from the perspective of fixed-parameter algorithms. By taking advantage of a new branch-and-bound strategy, two parameterized algorithms, with running times $O(2.42^k{m}^3{n}^4)$ and $O(2.74^k{m}^3{n}^5)$, respectively, are presented for the hard version and the soft version of the problem, which correspond to two different biological meanings to the polytomies in multifurcating phylogenetic trees.