Fast compatibility testing for rooted phylogenetic trees

DOI10.4230/LIPICS.CPM.2016.12MaRDI QIDQ5369546zbMATH OpenOpenAlexFDO

Authors Yun Deng, David Fernández-Baca

Publication date 17 October 2017

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

zbMATH Keywords

computational biologyphylogenetics

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Problems related to evolution (92D15)

Abstract: We consider the following basic problem in phylogenetic tree construction. Let $mathcalP=T_1,ldots,T_k$ be a collection of rooted phylogenetic trees over various subsets of a set of species. The tree compatibility problem asks whether there is a tree $T$ with the following property: for each $iin1,dots,k$, $T_i$ can be obtained from the restriction of $T$ to the species set of $T_i$ by contracting zero or more edges. If such a tree $T$ exists, we say that $mathcalP$ is compatible. We give a $ildeO(M_{m}athcalP)$ algorithm for the tree compatibility problem, where $M_{m}athcalP$ is the total number of nodes and edges in $mathcalP$. Unlike previous algorithms for this problem, the running time of our method does not depend on the degrees of the nodes in the input trees. Thus, it is equally fast on highly resolved and highly unresolved trees.

Recommendations

• Fast compatibility testing for rooted phylogenetic trees
• Compatibility of unrooted phylogenetic trees is FPT
• Tree Compatibility and Inferring Evolutionary History
• Extension operations on sets of leaf-labelled trees

Cited in

(15)

• Fast compatibility testing for phylogenies with nested taxa
• The matroid structure of representative triple sets and triple-closure computation
• On compatibility and incompatibility of collections of unrooted phylogenetic trees
• Reconstructing gene trees from Fitch's xenology relation
• Extension operations on sets of leaf-labelled 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
• scientific article; zbMATH DE number 437563 (Why is no real title available?)
• Optimizing tree and character compatibility across several phylogenetic trees
• Tree Compatibility and Inferring Evolutionary History
• Finding a Maximum Compatible Tree for a Bounded Number of Trees with Bounded Degree Is Solvable in Polynomial Time
• Constructing a consensus phylogeny from a leaf-removal distance (extended abstract)
• Phylogenetic trees via Hamming distance decomposition tests
• Fast compatibility testing for rooted phylogenetic trees
• Compatibility of unrooted phylogenetic trees is FPT

This page was built for publication: Fast compatibility testing for rooted phylogenetic trees

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