The computational complexity of inferring rooted phylogenies by parsimony

DOI10.1016/0025-5564(86)90161-6zbMath0607.92002OpenAlexW2084289491MaRDI QIDQ1086183

David S. Johnson, David Sankoff, William H. E. Day

Publication date: 1986

Published in: Mathematical Biosciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0025-5564(86)90161-6

zbMATH Keywords

computational complexityNP-completeevolutionary treesbinarymultistatequalitativeCamin-Sokal and Dollo parsimony criteriacladisticevolutionary changerooted phylogenies

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Problems related to evolution (92D15) Genetics and epigenetics (92D10) General biology and biomathematics (92B05) Computational methods for problems pertaining to biology (92-08)

Related Items (19)

The computational complexity of inferring rooted phylogenies by parsimony ⋮ An \(O(n)\) algorithm for finding an optimal position with relative distances in an evolutionary tree ⋮ Computational complexity of inferring phylogenies from dissimilarity matrices ⋮ Probabilistic models in cluster analysis ⋮ Is the protein model assignment problem under linked branch lengths NP-hard? ⋮ \textsc{FlipCut} supertrees: towards matrix representation accuracy in polynomial time ⋮ Optimizing phylogenetic supertrees using answer set programming ⋮ An Improved Fixed-Parameter Algorithm for Minimum-Flip Consensus Trees ⋮ Computing weighted solutions in ASP: representation-based method vs. search-based method ⋮ Topology reconstruction using time series data in telecommunication networks ⋮ Inferring phylogenetic trees using answer set programming ⋮ A GRASP/VND heuristic for the phylogeny problem using a new neighborhood structure ⋮ Adaptive memory programming: local search parallel algorithms for phylogenetic tree construc\-tion ⋮ Comparison of strings belonging to the same family ⋮ On the approximability of the Steiner tree problem in phylogeny ⋮ How to Infer Ancestral Genome Features by Parsimony: Dynamic Programming over an Evolutionary Tree ⋮ Scatter search with path relinking for phylogenetic inference ⋮ An algorithm for the maximum likelihood problem on evolutionary trees ⋮ Landscapes on spaces of trees

Cites Work

• Unnamed Item
• The computational complexity of inferring rooted phylogenies by parsimony
• The Steiner problem in phylogeny is NP-complete
• Unlikelihood that minimal phylogenies for a realistic biological study can be constructed in reasonable computational time
• Parallel concepts in graph theory

This page was built for publication: The computational complexity of inferring rooted phylogenies by parsimony