Linear time 3-approximation for MAST problem

Vincent Berry 1 Sylvain Guillemot 1 François Nicolas 1 Christophe Paul 2, *
* Auteur correspondant
1 MAB - Méthodes et Algorithmes pour la Bioinformatique
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
2 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : Given a set of leaf-labeled trees with identical leaf sets, the well-known Maximum Agreement Subtree (MAST) problem consists in finding a subtree homeomorphically included in all input trees and with the largest number of leaves. MAST and its variant called Maximum Compatible Tree (MCT) are of particular interest in computational biology. This paper presents a linear-time approximation algorithm to solve the complement version of MAST, namely identifying the smallest set of leaves to remove from input trees to obtain isomorphic trees. We also present an O(n^2 + kn) algorithm to solve the complement version of MCT. For both problems, we thus achieve significantly lower running times than previously known algorithms. Fast running times are especially important in phylogenetics where large collections of trees are routinely produced.
Type de document :
Article dans une revue
ACM Transactions on Algorithms, Association for Computing Machinery, 2009, 5 (2), pp.1-18
Liste complète des métadonnées

Littérature citée [21 références]  Voir  Masquer  Télécharger

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00324073
Contributeur : Vincent Berry <>
Soumis le : mardi 23 septembre 2008 - 19:39:59
Dernière modification le : jeudi 11 janvier 2018 - 06:26:13
Document(s) archivé(s) le : lundi 8 octobre 2012 - 13:26:03

Fichier

talg-submission-revised.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : lirmm-00324073, version 1

Collections

Citation

Vincent Berry, Sylvain Guillemot, François Nicolas, Christophe Paul. Linear time 3-approximation for MAST problem. ACM Transactions on Algorithms, Association for Computing Machinery, 2009, 5 (2), pp.1-18. 〈lirmm-00324073〉

Partager

Métriques

Consultations de la notice

371

Téléchargements de fichiers

173