Your browser doesn't support javascript.
An efficient algorithm for testing the compatibility of phylogenies with nested taxa.
Algorithms Mol Biol ; 12: 7, 2017.
Artigo em Inglês | MEDLINE | ID: mdl-28331536


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].


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].


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.





Texto completo: Disponível Coleções: Bases de dados internacionais Base de dados: MEDLINE Tipo de estudo: Guia de prática clínica / Incidence_studies Idioma: Inglês Revista: Algorithms Mol Biol Ano de publicação: 2017 Tipo de documento: Artigo