2014/11/01 by Feng Shi, Jianer Chen, Shi, Feng +7
Biochemistry, Genetics and Molecular Biology · Computer Science · #Data Mining Algorithms and Applications #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Genomics and Phylogenetic Studies #cs.DS
paper · pdf · doi:10.48550/arxiv.1411.0062
arxiv created 2014/11/01 · openalex publication_date 2014/11/01 · arxiv updated 2014/11/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The Maximum Agreement Forest (Maf) problem is a well-studied problem in evolutionary biology, which asks for a largest common subforest of a given collection of phylogenetic trees with identical leaf label-set. However, the previous work about the Maf problem are mainly on two binary phylogenetic trees or two general (i.e., binary and non-binary) phylogenetic trees. In this paper, we study the more general version of the problem: the Maf problem on multiple general phylogenetic trees. We present a parameterized algorithm of running time O(3k n2m) and a 3-approximation algorithm for the Maf problem on multiple rooted general phylogenetic trees, and a parameterized algorithm of running time O(4k n2m) and a 4-approximation algorithm for the Maf problem on multiple unrooted general phylogenetic trees. We also implement the parameterized algorithm and approximation algorithm for the Maf problem on multiple rooted general phylogenetic trees, and test them on simulated data and biological data.