A supertree algorithm for higher taxa
Most supertree algorithms combine collections of rooted phylogenetic trees with overlapping leaf sets into a single rooted phylogenetic tree (for example, see [1, 4, 6, 7]). Implicit in all of these algorithms is that the leaves of all the input trees represent species of the same taxonomic rank. In practice, however, one often wants to combine rooted phylogenetic trees whose leaves have different taxonomic ranks. The result of such an amalgamation may mean that, in addition to all of the leafs being labelled, some of the interior vertices are also labelled. In this chapter, we describe a supertree algorithm for 'rooted semi-labelled trees'. A rooted semi-labelled tree is more general than a rooted phylogenetic tree in that not only are its leaves labelled, but some of its interior vertices may also be labelled. For our purposes, an interior vertex label corresponds to a taxa at a higher rank than any of its descendants. The algorithm is polynomial time and is motivated by a problem posed by Page  in an earlier chapter called 'Taxonomy, Supertrees, and the Tree of Life'.
SubjectsField of Research::01 - Mathematical Sciences::0102 - Applied Mathematics::010202 - Biological Mathematics
- Engineering: Reports