Improved Parametrized Complexity of Maximum Agreement Subtree and Maximum Compatible Tree problems

Vincent Berry 1 François Nicolas 1
1 MAB - Méthodes et Algorithmes pour la Bioinformatique
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : Given a set of evolutionary trees on a same set of taxa, the maximum agreement subtree problem (MAST), respectively maximum compatible tree problem (MCT), consists of finding a largest subset of taxa such that all input trees restricted to these taxa are isomorphic, respectively compatible. These problems have several applications in phylogenetics such as the computation of a consensus of phylogenies obtained from different datasets, the identification of species subjected to horizontal gene transfers and, more recently, the inference of supertrees, e.g. Trees Of Life. We provide two linear time algorithms to check the isomorphism, respectively compatibility, of a set of trees or otherwise identify a conflict between the trees with respect to the relative location of a small subset of taxa. Then, we use these algorithms as subroutines to solve MAST and MCT on rooted or unrooted trees of unbounded degree. More precisely, we give exact fixed-parameter tractable algorithms, whose running time is uniformly polynomial when the number of taxa on which the trees disagree is bounded. This improves on a known result for MAST and proves fixed-parameter tractability for MCT.
Type de document :
Article dans une revue
IEEE/ACM Transactions on Computational Biology and Bioinformatics, Institute of Electrical and Electronics Engineers, 2006, 3 (3), pp.289-302. 〈10.1109/TCBB.2006.39〉
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00131835
Contributeur : Vincent Berry <>
Soumis le : lundi 19 février 2007 - 15:18:39
Dernière modification le : jeudi 24 mai 2018 - 15:59:22
Document(s) archivé(s) le : mardi 6 avril 2010 - 22:40:13

Fichier

Identifiants

Collections

Citation

Vincent Berry, François Nicolas. Improved Parametrized Complexity of Maximum Agreement Subtree and Maximum Compatible Tree problems. IEEE/ACM Transactions on Computational Biology and Bioinformatics, Institute of Electrical and Electronics Engineers, 2006, 3 (3), pp.289-302. 〈10.1109/TCBB.2006.39〉. 〈lirmm-00131835〉

Partager

Métriques

Consultations de la notice

187

Téléchargements de fichiers

297