Efficient FPT algorithms for (strict) compatibility of unrooted phylogenetic trees

DOI10.1007/s11538-017-0260-yzbMath1372.92069arXiv1604.03008OpenAlexW2339239829WikidataQ38936462 ScholiaQ38936462MaRDI QIDQ2408842

Christophe Paul, Julien Baste, Ignasi Sau, Celine Scornavacca

Publication date: 20 October 2017

Published in: Bulletin of Mathematical Biology, Algorithmic Aspects in Information and Management (Search for Journal in Brave)

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

zbMATH Keywords

dynamic programmingcompatibilityparameterized complexityFPT algorithmphylogeneticsunrooted phylogenetic trees

Mathematics Subject Classification ID

Problems related to evolution (92D15) Applications of graph theory (05C90) Computational methods for problems pertaining to biology (92-08)

Related Items

Treewidth distance on phylogenetic trees ⋮ Maximum parsimony distance on phylogenetic trees: a linear kernel and constant factor approximation algorithm ⋮ On compatibility and incompatibility of collections of unrooted phylogenetic trees ⋮ Treewidth of display graphs: bounds, brambles and applications

Cites Work

• Unnamed Item
• Unnamed Item
• Compatibility of unrooted phylogenetic trees is FPT
• Consensus supertrees: The synthesis of rooted trees containing overlapping sets of labeled leaves
• The complexity of reconstructing trees from qualitative characters and subtrees
• Treewidth. Computations and approximations
• Phylogenetic supertrees. Combining information to reveal the tree of life
• The complexity of first-order and monadic second-order logic revisited
• Reconstruction of rooted trees from subtrees
• A $c^k n$ 5-Approximation Algorithm for Treewidth
• Inferring a Tree from Lowest Common Ancestors with an Application to the Optimization of Relational Expressions
• The agreement problem for unrooted phylogenetic trees is FPT
• Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time

This page was built for publication: Efficient FPT algorithms for (strict) compatibility of unrooted phylogenetic trees