title: Amalgamating source trees with different taxonomic levels.
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).
authors.affiliation: Méthodes et Algorithmes pour la Bioinformatique MAB team, Université Montpellier 2, L.I.R.M.M. - C.N.R.S., 161 rue Ada, 34095 Montpellier Cedex 5, France.
authors.forename: Vincent
authors.initials: V
authors.lastname: Berry
authors.forename: Olaf R P
authors.initials: OR
authors.lastname: Bininda-Emonds
authors.forename: Charles
authors.initials: C
authors.lastname: Semple
mesh_terms: D000465:Algorithms; D000818:Animals; D002965:Classification / Q000379:methods*; D008954:Models, Biological; D010802:Phylogeny; D046048:Seals, Earless / Q000145:classification