Amalgamating Source Trees with Different Taxonomic Levels

Vincent Berry 1 Olaf Bininda-Emonds 2 Charles Semple 3, *
* Auteur correspondant
1 MAB - Méthodes et Algorithmes pour la Bioinformatique
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : Supertree methods combine a collection of source trees into a single parent tree or supertree. For almost all such methods, the terminal taxa across the source trees have to be non-nested for the output supertree to make sense. Motivated by Page, the first supertree method for combining rooted source trees where the taxa can be hierarchically nested is called AncestralBuild. In addition to taxa labeling the leaves, this method allows the rooted source trees to have taxa labeling some of the interior nodes at a higher taxonomic level than their descendants (e.g., genera vs. species). However, the utility of AncestralBuild is somewhat restricted as it is mostly intended to decide if a collection of rooted source trees is compatible. If the initial collection is not compatible, then no tree is returned. To overcome this restriction, we introduce here the MultiLevelSupertree (MLS) supertree method whose input is the same as that for AncestralBuild, but which accommodates incompatibilities among rooted source trees using a MinCut-like procedure. We show that MLS has several desirable properties including the preservation of common subtrees among the source trees, the preservation of ancestral relationships whenever they are compatible, as well as running in polynomial time. Furthermore, application to a small test data set (the mammalian carnivore family Phocidae) indicates that the method correctly places nested taxa at different taxonomic levels (reflecting vertical signal), even in cases where the input trees harbor a significant level of conflict between their clades (i.e., in their horizontal signal).
Liste complète des métadonnées

Littérature citée [34 références]  Voir  Masquer  Télécharger

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00804769
Contributeur : Vincent Berry <>
Soumis le : mardi 30 avril 2013 - 19:25:58
Dernière modification le : jeudi 11 janvier 2018 - 06:26:13
Document(s) archivé(s) le : jeudi 1 août 2013 - 04:04:17

Fichier

supertree-23-10-12.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Vincent Berry, Olaf Bininda-Emonds, Charles Semple. Amalgamating Source Trees with Different Taxonomic Levels. Systematic Biology, Oxford University Press (OUP), 2013, 62 (2), pp.231-249. 〈http://sysbio.oxfordjournals.org/content/62/2/231.abstract〉. 〈10.1093/sysbio/sys090〉. 〈lirmm-00804769〉

Partager

Métriques

Consultations de la notice

129

Téléchargements de fichiers

222