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

zbMATH Keywords

phylogenetic inferenceNP-completebiochemistrydissimilarity matrixamino acid sequencingFarris's f statisticleast-squares-fit criterionunrooted phylogenies

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Physiological, cellular and medical topics (92Cxx)

• The computational complexity of inferring rooted phylogenies by parsimony
• Inferring Evolutionary History From DNA Sequences
• On the complexity of constructing evolutionary trees
• scientific article; zbMATH DE number 1088267
• On the hardness of inferring phylogenies from triplet-dissimilarities

• scientific article; zbMATH DE number 3504320 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Distance matrix of a graph and its realizability
• NP-hard problems in hierarchical-tree clustering
• Reconstructing the shape of a tree from observed dissimilarity data
• The Steiner problem in phylogeny is NP-complete
• The computational complexity of inferring rooted phylogenies by parsimony
• Unlikelihood that minimal phylogenies for a realistic biological study can be constructed in reasonable computational time
• Unrooted trees for numerical taxonomy

(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
• Modeling the distribution of distance data in Euclidean space
• 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
• 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)