Computational complexity of inferring phylogenies from dissimilarity matrices
DOI10.1007/BF02458863zbMATH Open0623.92018OpenAlexW4237132695WikidataQ69418195 ScholiaQ69418195MaRDI QIDQ1091978FDOQ1091978
Authors: W. H. E. Day 
Publication date: 1987
Published in: Bulletin of Mathematical Biology (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf02458863
Recommendations
phylogenetic inferenceNP-completebiochemistrydissimilarity matrixamino acid sequencingFarris's f statisticleast-squares-fit criterionunrooted phylogenies
Analysis of algorithms and problem complexity (68Q25) Physiological, cellular and medical topics (92Cxx)
Cites Work
- Reconstructing the shape of a tree from observed dissimilarity data
- Unrooted trees for numerical taxonomy
- Title not available (Why is that?)
- The Steiner problem in phylogeny is NP-complete
- Title not available (Why is that?)
- The computational complexity of inferring rooted phylogenies by parsimony
- Distance matrix of a graph and its realizability
- Unlikelihood that minimal phylogenies for a realistic biological study can be constructed in reasonable computational time
- NP-hard problems in hierarchical-tree clustering
Cited In (25)
- Testing metric properties
- An exact and polynomial distance-based algorithm to reconstruct single copy tandem duplication trees
- Optimality of the neighbor joining algorithm and faces of the balanced minimum evolution polytope
- Tree reconstruction from partial orders
- An \(O(n)\) algorithm for finding an optimal position with relative distances in an evolutionary tree
- On the edge \(l_{\infty }\) radius of Saitou and Nei's method for phylogenetic reconstruction
- Inferring evolutionary trees with strong combinatorial evidence
- \(l_\infty\)-approximation via subdominants.
- A lower bound on the edge \(l_{\infty }\) radius of Saitou and Nei's method for phylogenetic reconstruction
- Facets of the balanced minimal evolution polytope
- On the hardness of inferring phylogenies from triplet-dissimilarities
- A robust model for finding optimal evolutionary tree
- Modeling the distribution of distance data in Euclidean space
- The computational complexity of inferring rooted phylogenies by parsimony
- Steiner tree problems
- Performance of matrix representation with parsimony for inferring species from gene trees
- The minimum evolution problem: Overview and classification
- Computing the unrooted maximum agreement subtree in sub-quadratic time
- Phage typing sets
- Scatter search with path relinking for phylogenetic inference
- A reduction algorithm for approximating a (nonmetric) dissimilarity by a tree distance
- UPGMA and the normalized equidistant minimum evolution problem
- Mathematical models to reconstruct phylogenetic trees under the minimum evolution criterion
- Compact mixed integer linear programming models to the minimum weighted tree reconstruction problem
- Tropical medians by transportation
This page was built for publication: Computational complexity of inferring phylogenies from dissimilarity matrices
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1091978)
