The computational complexity of inferring rooted phylogenies by parsimony
From MaRDI portal
Publication:1086183
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
computational complexityNP-completeevolutionary treesbinarymultistatequalitativeCamin-Sokal and Dollo parsimony criteriacladisticevolutionary changerooted phylogenies
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
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
