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

abstract

  • The Maximun Agreement Forest problem (maf) asks for a largest common subforest of a collection of phylogenetic trees. The maf problem on two binary phylogenetic trees has been studied extensively in the literature. In this paper, we present the first group of fixed-parameter tractable algorithms for the maf problem on multiple (i.e., two or more) binary phylogenetic trees. Our techniques work fine for the problem for both rooted trees and unrooted trees. The computational complexity of our algorithms is comparable with that of the known algorithms for two trees, and is independent of the number of phylogenetic trees for which a maximum agreement forest is constructed. 2013 Springer-Verlag Berlin Heidelberg.

name of conference

  • Computing and Combinatorics, 19th International Conference, COCOON 2013, Hangzhou, China, June 21-23, 2013. 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

  • 0

complete list of authors

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

publication date

  • October 2013