The computational complexity of inferring rooted phylogenies by parsimony
From MaRDI portal
Publication:1086183
In systematics, parsimony methods construct phylogenies, or evolutionary trees, in which characters evolve with the least evolutionary change. The Camin-Sokal and Dollo parsimony criteria are used to construct phylogenies from discrete characters. Variations of these problems depend on whether characters are: cladistic or qualitative, binary or multistate. The authors proved that the basic variants of these problems are all NP-complete.
Recommendations
- Computational complexity of inferring phylogenies from dissimilarity matrices
- Minimizing phylogenetic number to find good evolutionary trees
- The complexity of reconstructing trees from qualitative characters and subtrees
- Inferring Evolutionary History From DNA Sequences
- Algorithms for phylogeny reconstruction in a new mathematical model
Cites work
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- Parallel concepts in graph theory
- 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
Cited in
(31)- The computational complexity of inferring rooted phylogenies by parsimony
- Computational complexity of inferring phylogenies from dissimilarity matrices
- On the approximability of the Steiner tree problem in phylogeny
- Probabilistic models in cluster analysis
- The complexity of comparing multiply-labelled trees by extending phylogenetic-tree metrics
- Comparison of strings belonging to the same family
- Landscapes on spaces of trees
- Inferring phylogenetic trees using answer set programming
- Generalizations on the parsimony question in evolution
- Scatter search with path relinking for phylogenetic inference
- An algorithm for the maximum likelihood problem on evolutionary trees
- Is the protein model assignment problem under linked branch lengths NP-hard?
- An \(O(n)\) algorithm for finding an optimal position with relative distances in an evolutionary tree
- A GRASP/VND heuristic for the phylogeny problem using a new neighborhood structure
- The Complexity of Rooted Phylogeny Problems
- An Improved Fixed-Parameter Algorithm for Minimum-Flip Consensus Trees
- \textsc{FlipCut} supertrees: towards matrix representation accuracy in polynomial time
- Computing weighted solutions in ASP: representation-based method vs. search-based method
- Optimizing phylogenetic supertrees using answer set programming
- How to infer ancestral genome features by parsimony: dynamic programming over an evolutionary tree
- The Worst Case Complexity of Maximum Parsimony
- Adaptive memory programming: local search parallel algorithms for phylogenetic tree construc\-tion
- Parsimony, phylogeny, and genomics.
- Topology reconstruction using time series data in telecommunication networks
- On the approximability of the Steiner tree problem in phylogeny
- Parameterized algorithms for the Steiner arborescence problem on a hypercube
- A Sankoff-Rousseau-like algorithm for minimizing lateral gene transfers and losses on single origin characters
- Dynamic programming algorithms for fast and accurate cell lineage tree reconstruction from CRISPR-based lineage tracing data
- Topology reconstruction in telecommunication networks: embedding operations research within deep learning
- On approximability of Steiner tree in _p-metrics
- Bayesian inference of phylogenetic distances: revisiting the eigenvalue approach
This page was built for publication: The computational complexity of inferring rooted phylogenies by parsimony
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1086183)
