Counting consistent phylogenetic trees is \#P-complete

DOI10.1016/J.AAM.2003.08.006MaRDI QIDQ1883389zbMATH OpenOpenAlexFDO

Authors Magnus Bordewich, Charles Semple, John Talbot

Publication date 12 October 2004

Published in Advances in Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.aam.2003.08.006, https://durham-repository.worktribe.com/output/1565693

zbMATH Keywords

\#P complete counting\(\#\)-\texttt{MON-2-SAT} problemNP-complete decision problem

Mathematics Subject Classification ID

Trees (05C05) Problems related to evolution (92D15)

Review text

The paper studies the complexity of counting rooted phylogenetic (super)trees consistent to a set of (possibly overlapping) rooted phylogenetic trees, and shows that it (similarly to two other related problems) is \#P-complete. The proof works through reducing the problem \(\#\)-\texttt{MON-2-SAT} to the problem at hand.

Recommendations

• Counting trees in a phylogenetic network is \#P-complete
• Counting trees in a graph is \(\# \text{P}\)-complete
• Enumeration of binary trees compatible with a perfect phylogeny
• On the combinatorics of rooted binary phylogenetic trees
• scientific article; zbMATH DE number 3891391
• Counting Unlabelled Subtrees of a Tree is #P-complete
• Neighborhoods of phylogenetic trees: exact and asymptotic counts
• Finite phylogenetic complexity and combinatorics of tables
• Counting general phylogenetic networks
• On the number of vertices of each rank in phylogenetic trees and their generalizations

Cites work

• An efficient algorithm for supertrees
• Counting linear extensions
• scientific article; zbMATH DE number 437298 (Why is no real title available?)
• scientific article; zbMATH DE number 1865935 (Why is no real title available?)
• Inferring a Tree from Lowest Common Ancestors with an Application to the Optimization of Relational Expressions
• Phylogenetic supertrees. Combining information to reveal the tree of life
• Random generation of combinatorial structures from a uniform distribution
• Reconstruction of rooted trees from subtrees
• The Complexity of Enumeration and Reliability Problems
• The complexity of reconstructing trees from qualitative characters and subtrees

Cited in

(8)

• Counting trees in a graph is \(\# \text{P}\)-complete
• Enumeration of binary trees compatible with a perfect phylogeny
• Recovering a phylogenetic tree using pairwise closure operations
• Counting trees in a phylogenetic network is \#P-complete
• Unique perfect phylogeny is NP-hard
• Counting Unlabelled Subtrees of a Tree is #P-complete
• The complexity of phylogeny constraint satisfaction
• The complexity of phylogeny constraint satisfaction problems

This page was built for publication: Counting consistent phylogenetic trees is \#P-complete

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