Fast compatibility testing for phylogenies with nested taxa

DOI10.1007/978-3-319-43681-4_8MaRDI QIDQ1708416zbMATH OpenOpenAlexFDO

Authors Yun Deng, David Fernández-Baca

Publication date 23 March 2018

Full work available at URL https://arxiv.org/abs/1605.02045

zbMATH Keywords

ancestral compatibility problemnested taxasemi-labeled trees

Mathematics Subject Classification ID

Taxonomy, cladistics, statistics in mathematical biology (92B10) Problems related to evolution (92D15)

Abstract: Semi-labeled trees are phylogenies whose internal nodes may be labeled by higher-order taxa. Thus, a leaf labeled Mus musculus could nest within a subtree whose root node is labeled Rodentia, which itself could nest within a subtree whose root is labeled Mammalia. Suppose we are given collection $mathcalP$ of semi-labeled trees over various subsets of a set of taxa. The ancestral compatibility problem asks whether there is a semi-labeled tree $mathcalT$ that respects the clusterings and the ancestor/descendant relationships implied by the trees in $mathcalP$. We give a $ildeO(M_{mathcalP})$ algorithm for the ancestral compatibility problem, where $M_{mathcalP}$ is the total number of nodes and edges in the trees in $mathcalP$. Unlike the best previous algorithm, the running time of our method does not depend on the degrees of the nodes in the input trees.

Recommendations

• Fast compatibility testing for rooted phylogenetic trees
• On the ancestral compatibility of two phylogenetic trees with nested taxa
• Fast compatibility testing for rooted phylogenetic trees
• Tree Compatibility and Inferring Evolutionary History
• scientific article; zbMATH DE number 437563

Cited in

(4)

• On compatibility and incompatibility of collections of unrooted phylogenetic trees
• Tree compatibility, incomplete directed perfect phylogeny, and dynamic graph connectivity: an experimental study
• On the ancestral compatibility of two phylogenetic trees with nested taxa
• Fast compatibility testing for rooted phylogenetic trees

This page was built for publication: Fast compatibility testing for phylogenies with nested taxa

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1708416)