© 2006 Society of Systematic Biologists
Fast Computation of Supertrees for Compatible Phylogenies with Nested Taxa
1 Département Informatique, L.I.R.M.M.–C.N.R.S. 161 rue Ada, 34392 Montpellier Cedex 5, France E-mail: vberry{at}lirmm.fr
2 Biomathematics Research Centre, Department of Mathematics and Statistics, University of Canterbury Christchurch, New Zealand E-mail: c.semple{at}math.canterbury.ac.nz
Edited by Olaf Emonds: Associate Editor
 |
Abstract |
|---|
Typically, supertree methods combine a collection of source trees in which just the leaves are labeled by taxa. In such methods the resulting supertree is also leaf labeled. 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 ANCESTRAL BUILD. Here, in addition to taxa labeling the leaves, the source trees may have taxa labeling some of their interior nodes. Taxa-labeling 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 labeled, ANCESTRAL BUILD is a polynomial-time algorithm for deciding the compatibility of a collection of source trees in which some of the interior nodes are also labeled by taxa. Although a more general method, in this paper we show that the original description of ANCESTRAL BUILD 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 ANCESTRAL BUILD is incorporated as a basic tool inside more general supertree methods (that is, methods that always output a tree regardless of the compatibility of the source trees). We apply the method to propose a comprehensive phylogeny of the strepsirrhines, a major group of the primates.
Keywords: Compatibility; nested taxa; phylogenetics, strepsirrhine phylogeny; supertree methods
Received July 4, 2005; Revised September 9, 2005; Accepted November 4, 2005
CiteULike 
Connotea 
Del.icio.us What's this?
This article has been cited by other articles:
|
|
 |
|
  V. Ranwez, V. Berry, A. Criscuolo, P.-H. Fabre, S. Guillemot, C. Scornavacca, and E. J. P. Douzery PhySIC: A Veto Supertree Method with Desirable Properties Syst Biol, October 1, 2007; 56(5): 798 - 817. [Abstract] [Full Text] [PDF]
|
|