Common Structure Among Maximum Agreement Forests of Phylogenetic Trees

Abstract

Reconciling sets of phylogenetic trees has become a problem of particular interest in both theoretical computer science and bioinformatics. The use of the maximum agreement forest as a tool by which to attain insight into the discrepancies in evolutionary paths between trees that model the same set of taxa has been well researched. However, to date there has not been any method by which to sample from the potentially large space of possible MAFs, and thus crucial information may be missed. To this end we introduce the notion of core maximum agreement forest, which provides us with the set of components preserved across the MAFs of a set of phylogenetic trees. Through the use of the established techniques of cluster partitioning and branching rules, we prove that this problem is fixed parameter tractable and present an efficient algorithm for computing this new structure in O(2.27^k * n) time.