Linear time 3-approximation for MAST problem - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Journal Articles ACM Transactions on Algorithms Year : 2009

Linear time 3-approximation for MAST problem

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.
Fichier principal
Vignette du fichier
talg-submission-revised.pdf (245.15 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

lirmm-00324073 , version 1 (23-09-2008)

Identifiers

Cite

Vincent Berry, Sylvain Guillemot, François Nicolas, Christophe Paul. Linear time 3-approximation for MAST problem. ACM Transactions on Algorithms, 2009, 5 (2), pp.1-18. ⟨10.1145/1497290.1497299⟩. ⟨lirmm-00324073⟩
327 View
443 Download

Altmetric

Share

Gmail Facebook X LinkedIn More