Repository logo
 

Common Structure Among Maximum Agreement Forests of Phylogenetic Trees

Date

2021-09-01T18:07:27Z

Authors

Dempsey, Jordan

Journal Title

Journal ISSN

Volume Title

Publisher

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.

Description

Keywords

phylogenetics, theoretical computer science, algorithms, graph theory, agreement forests, combinatorics, cluster reduction, lateral gene transfer, branching algorithms, fixed-parameter tractability

Citation