Linear time 3-approximation for MAST problem

Vincent Berry 1 Sylvain Guillemot 1 François Nicolas 1 Christophe Paul 2, *
* Corresponding author
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.
Document type :
Journal articles
Complete list of metadatas

Cited literature [21 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00324073
Contributor : Vincent Berry <>
Submitted on : Tuesday, September 23, 2008 - 7:39:59 PM
Last modification on : Thursday, May 24, 2018 - 3:59:22 PM
Long-term archiving on: Monday, October 8, 2012 - 1:26:03 PM

File

talg-submission-revised.pdf
Files produced by the author(s)

Identifiers

  • 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⟩

Share

Metrics

Record views

683

Files downloads

274