Maximum Agreement and Compatible Supertrees

Vincent Berry 1, * François Nicolas 1
* Auteur correspondant
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 leaf-labelled trees with identical leaf sets, the MAST problem, respectively MCT problem, consists of finding a largest subset of leaves such that all input trees restricted to these leaves are isomorphic, respectively compatible. In this paper, we propose extensions of these problems to the context of supertree inference, where input trees have non-identical leaf sets. This situation is of particular interest in phylogenetics. The resulting problems are called SMAST and SMCT. A sufficient condition is given that identifies cases where these problems can be solved by resorting to MAST and MCT as subproblems. This condition is met, for instance, when only two input trees are considered. Then we give algorithms for SMAST and SMCT that benefit from the link with the subtree problems. These algorithms run in time linear to the time needed to solve MAST, respectively MCT, on an instance of the same or smaller size. It is shown that arbitrary instances of SMAST and SMCT can be turned in polynomial time into instances composed of trees with a bounded number of leaves. SMAST is shown to be W[2]-hard when the considered parameter is the number of input leaves that have to be removed to obtain the agreement of the input trees. A similar result holds for SMCT. Moreover, the corresponding optimization problems, that is the complements of SMAST and SMCT, cannot be approximated in polynomial time within any constant factor, unless P = NP. These results also hold when the input trees have a bounded number of leaves. The presented results apply to both collections of rooted and unrooted trees.
Type de document :
Article dans une revue
Journal of Discrete Algorithms, Elsevier, 2007, 5 (3), pp.564-591
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00194239
Contributeur : Vincent Berry <>
Soumis le : jeudi 6 décembre 2007 - 10:14:13
Dernière modification le : jeudi 24 mai 2018 - 15:59:22
Document(s) archivé(s) le : lundi 12 avril 2010 - 06:21:23

Fichier

Identifiants

  • HAL Id : lirmm-00194239, version 1

Collections

Citation

Vincent Berry, François Nicolas. Maximum Agreement and Compatible Supertrees. Journal of Discrete Algorithms, Elsevier, 2007, 5 (3), pp.564-591. 〈lirmm-00194239〉

Partager

Métriques

Consultations de la notice

142

Téléchargements de fichiers

161