Amalgamating Source Trees with Different Taxonomic Levels

Vincent Berry 1 Olaf Bininda-Emonds 2 Charles Semple 3, *
* Corresponding author
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).
Complete list of metadatas

Cited literature [34 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00804769
Contributor : Vincent Berry <>
Submitted on : Tuesday, April 30, 2013 - 7:25:58 PM
Last modification on : Thursday, May 24, 2018 - 3:59:22 PM
Long-term archiving on : Thursday, August 1, 2013 - 4:04:17 AM

File

supertree-23-10-12.pdf
Files produced by the author(s)

Identifiers

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⟩

Share

Metrics

Record views

282

Files downloads

618