An efficient algorithm for testing the compatibility of phylogenies with nested taxa

BACKGROUND: Semi-labeled trees generalize ordinary phylogenetic trees, allowing internal nodes to be labeled by higher-order taxa. Taxonomies are examples of semi-labeled trees. Suppose we are given collection [Formula: see text] of semi-labeled trees over various subsets of a set of taxa. The ancestral compatibility problem asks whether there is a semi-labeled tree that respects the clusterings and the ancestor/descendant relationships implied by the trees in [Formula: see text] . The running time and space usage of the best previous algorithm for testing ancestral compatibility depend on the degrees of the nodes in the trees in [Formula: see text] . RESULTS: We give a algorithm for the ancestral compatibility problem that runs in [Formula: see text] time and uses [Formula: see text] space, where [Formula: see text] is the total number of nodes and edges in the trees in [Formula: see text] . CONCLUSIONS: Taxonomies enable researchers to expand greatly the taxonomic coverage of their phylogenetic analyses. The running time of our method does not depend on the degrees of the nodes in the trees in [Formula: see text] . This characteristic is important when taxonomies—which can have nodes of high degree—are used.