Approximation Algorithms for Maximum Agreement Forest on Multiple Trees Conference Paper uri icon

abstract

  • Given a collection of phylogenetic trees with identical leaf label-set, the Maximum Agreement Forest problem (maf) asks for a largest common subforest of these input trees. The maf problem on two binary phylogenetic trees has been studied extensively in the literature. In this paper, we will be 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 previously best ratio 8 for the problem. Our 4-approximation algorithm for the maf problem on multiple unrooted trees is the first approximation algorithm for the problem. 2014 Springer International Publishing Switzerland.

name of conference

  • Computing and Combinatorics - 20th International Conference, COCOON 2014, Atlanta, GA, USA, August 4-6, 2014. Proceedings

published proceedings

  • Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

author list (cited authors)

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

citation count

  • 3

complete list of authors

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

publication date

  • January 2014