Skip to Main content Skip to Navigation
Conference papers

On the Approximation of Computing Evolutionary Trees

Vincent Berry 1 Sylvain Guillemot 1 Nicolas François 2 Christophe Paul 3
1 MAB - Méthodes et Algorithmes pour la Bioinformatique
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
3 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Résumé : Given a set of leaf-labelled trees with identical leaf sets, the well-known MAST problem consists of finding a subtree homeomorphi- cally included in all input trees and with the largest number of leaves. MAST and its variant called MCT are of particular interest in computa- tional biology. This paper presents positive and negative results on the approximation of MAST, MCT and their complement versions, denoted CMAST and CMCT. For CMAST and CMCT on rooted trees we give 3-approximation algo- rithms achieving significantly lower running times than those previously known. In particular, the algorithm for CMAST runs in linear time. The approximation threshold for CMAST, resp. CMCT, is shown to be the same whenever collections of rooted trees or of unrooted trees are considered. Moreover, hardness of approximation results are stated for CMAST, CMCT and MCT on small number of trees, and for MCT on unbounded number of trees.
Document type :
Conference papers
Complete list of metadatas

Cited literature [22 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00106451
Contributor : Christine Carvalho de Matos <>
Submitted on : Monday, October 16, 2006 - 8:29:19 AM
Last modification on : Friday, September 20, 2019 - 12:59:39 PM
Long-term archiving on: : Tuesday, April 6, 2010 - 7:40:54 PM

File

Identifiers

Collections

Citation

Vincent Berry, Sylvain Guillemot, Nicolas François, Christophe Paul. On the Approximation of Computing Evolutionary Trees. COCOON: Computing and Combinatorics Conference, Aug 2005, Kunming, China. pp.115-125, ⟨10.1007/11533719_14⟩. ⟨lirmm-00106451⟩

Share

Metrics

Record views

205

Files downloads

577