A Fixed-parameter Algorithm For The Maximum Agreement Forest Problem On Multifurcating Trees

The Maximum Agreement Forest (MAF) problem on two given phylogenetic trees is an important NP-hard problem in the field of computational biology. The phylogenetic tree includes rooted and unrooted types. In this thesis, we only study the unrooted phylogenetic tree. Recent research in biology and evolution has shown that the majority of tree space in typical phylogenetic studies consists of multifurcating trees, and that multifurcations can introduce irresolvable problems for certain well-known tree-search algorithms (such as NNI algorithm). In additional, the problem the biology literature is attempting to solve is the SPR distance between unrooted multifurcating trees. The complexity of this problem is open. However, the computational complexity for the MAF problem on general (i.e. binary and non-binary) phylogenetic trees has not been studied as extensively as that on binary trees. Whether the MAF problem on unrooted multifurcating trees is fixed-parameter tractable was posed specifically as an open problem by Hallett and McCartin in2007, and was posed again by Whidden et al. for rooted and unrooted multifurcating trees in2011.In this thesis, we study the new structure-star quartet, which only exists in the multifurcating tree. Study the butterfly quartet and star quartet, the minimum incompatible quartet in the binary tree is extended to the general tree. Then, we claim a new characteristic structure conflicted chain. The aboved two kinds of characteristic structure studied have proven that solving the MAF problem in unrooted multifurcating trees is fixed-parameter tractable. Thus, we resolve this open problem. Finally, we admit a parameterized algorithm of running time O(4kn5) for this problem.