Anzeige
Erschienen in:
2013 | OriginalPaper | Buchkapitel
Parameterized Algorithms for Maximum Agreement Forest on Multiple Trees
verfasst von : Feng Shi, Jianer Chen, Qilong Feng, Jianxin Wang
Erschienen in: Computing and Combinatorics
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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.