On the Approximation of Computing Evolutionary Trees

Sylvain Guillemot 1
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 well-known MAST problem consists of finding a subtree homeomorphically included in all input trees and with the largest number of leaves. MAST and its variant called MCT are of particular interest in computational biology. This paper presents positive and negative results on the approximation on MAST, MCT and their complement versions, denoted CMAST and CMCT. For CMAST and CMCT on rooted trees we give 3-approximation algorithms 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, resp. MCT, on small number of trees, resp. on unbounded number of trees.
Type de document :
Communication dans un congrès
Lusheng Wang. COCOON'05: Computing and Combinatorics, Aug 2005, Kunming (China), Springer, pp.115-125, 2005, Lecture Notes in Computer Science. 〈http://www.lirmm.fr/~mab〉
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00145461
Contributeur : Sylvain Guillemot <>
Soumis le : jeudi 10 mai 2007 - 13:38:41
Dernière modification le : jeudi 24 mai 2018 - 15:59:22

Identifiants

  • HAL Id : lirmm-00145461, version 1

Collections

Citation

Sylvain Guillemot. On the Approximation of Computing Evolutionary Trees. Lusheng Wang. COCOON'05: Computing and Combinatorics, Aug 2005, Kunming (China), Springer, pp.115-125, 2005, Lecture Notes in Computer Science. 〈http://www.lirmm.fr/~mab〉. 〈lirmm-00145461〉

Partager

Métriques

Consultations de la notice

56