Fast Computation of Supertrees for Compatible Phylogenies with Nested Taxa

Vincent Berry 1 Charles Semple 2
1 MAB - Méthodes et Algorithmes pour la Bioinformatique
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : Typically, supertree methods combine a collection of source trees in which just the leaves are labelled by taxa. In such methods the resulting supertree is also leaf-labelled. An underlying assumption in these methods is that, across all trees in the collection, no two of the taxa are nested ; for example, "buttercups'' and "plants'' are nested taxa. Motivated by Page, the first supertree algorithm for allowing the source trees to collectively have nested taxa is called AncestralBuild. Here, in addition to taxa labelling the leaves, the source trees may have taxa labelling some of their interior nodes. Taxa labelling interior nodes are at a higher taxonomic level than that of their descendants (for example, genera versus species). Analogous to the supertree method Build for deciding the compatibility of a collection of source trees in which just the leaves are labelled, AncestralBuild is a polynomial-time algorithm for deciding the compatibility of a collection of source trees in which some of the interior nodes are also labelled by taxa. Although a more general method, in this paper we show that the original description of AncestralBuild can be modified so that the running time is as fast as the current fastest running time for Build. Fast computation for deciding compatibility is essential if one is to make use of phylogenetic databases that contain thousands of trees on tens of thousands of taxa. This is particularly so as AncestorBuild is incorporated as a basic tool inside more general supertree methods. We apply the method to propose a comprehensive phylogeny of the strepsirrhines, a major group of the primates.
Type de document :
Article dans une revue
Systematic Biology, Oxford University Press (OUP), 2006, 55 (2), pp.U108-U126
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00131854
Contributeur : Vincent Berry <>
Soumis le : lundi 19 février 2007 - 15:41:04
Dernière modification le : jeudi 11 janvier 2018 - 06:26:12
Document(s) archivé(s) le : mercredi 7 avril 2010 - 02:48:12

Identifiants

  • HAL Id : lirmm-00131854, version 1

Collections

Citation

Vincent Berry, Charles Semple. Fast Computation of Supertrees for Compatible Phylogenies with Nested Taxa. Systematic Biology, Oxford University Press (OUP), 2006, 55 (2), pp.U108-U126. 〈lirmm-00131854〉

Partager

Métriques

Consultations de la notice

164

Téléchargements de fichiers

91