Approximating Maximum Agreement Forest on Multiple Binary Trees Academic Article uri icon

abstract

  • 2015, Springer Science+Business Media New York. Given a collection of phylogenetic trees on the same leaf label-set, the Maximum Agreement Forest problem (Maf) asks for a largest common subforest of these trees. The Maf problem on two binary phylogenetic trees has been studied extensively. In this paper, we are focused on the Maf problem on multiple (i.e., two or more) binary phylogenetic trees and present two polynomial-time approximation algorithms, one for the Maf problem on multiple rooted trees, and the other for the Maf problem on multiple unrooted trees. The ratio of our algorithm for the Maf problem on multiple rooted trees is 3, which is an improvement over the previous best ratio 8 for the problem. Our approximation algorithm of ratio 4 for the Maf problem on multiple unrooted trees is the first constant ratio approximation algorithm for the problem.

published proceedings

  • Algorithmica

author list (cited authors)

  • Chen, J., Shi, F., & Wang, J.

citation count

  • 13

complete list of authors

  • Chen, Jianer||Shi, Feng||Wang, Jianxin

publication date

  • December 2016