Computational complexity of inferring phylogenies from dissimilarity matrices

DOI10.1007/BF02458863zbMath0623.92018OpenAlexW4237132695WikidataQ69418195 ScholiaQ69418195MaRDI QIDQ1091978

William 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

NP-completephylogenetic inferencebiochemistrydissimilarity 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)

Related Items (22)

Optimality of the neighbor joining algorithm and faces of the balanced minimum evolution polytope ⋮ Testing metric properties ⋮ An \(O(n)\) algorithm for finding an optimal position with relative distances in an evolutionary tree ⋮ Facets of the balanced minimal evolution polytope ⋮ Computing the unrooted maximum agreement subtree in sub-quadratic time ⋮ Tree reconstruction from partial orders ⋮ A robust model for finding optimal evolutionary tree ⋮ On the edge \(l_{\infty }\) radius of Saitou and Nei's method for phylogenetic reconstruction ⋮ Tropical medians by transportation ⋮ UPGMA and the normalized equidistant minimum evolution problem ⋮ Modeling the distribution of distance data in Euclidean space ⋮ On the hardness of inferring phylogenies from triplet-dissimilarities ⋮ Compact mixed integer linear programming models to the minimum weighted tree reconstruction problem ⋮ The minimum evolution problem: Overview and classification ⋮ Mathematical models to reconstruct phylogenetic trees under the minimum evolution criterion ⋮ Steiner tree problems ⋮ Inferring evolutionary trees with strong combinatorial evidence ⋮ A lower bound on the edge \(l_{\infty }\) radius of Saitou and Nei's method for phylogenetic reconstruction ⋮ A reduction algorithm for approximating a (nonmetric) dissimilarity by a tree distance ⋮ An exact and polynomial distance-based algorithm to reconstruct single copy tandem duplication trees ⋮ Scatter search with path relinking for phylogenetic inference ⋮ \(l_\infty\)-approximation via subdominants.

Cites Work

• Unnamed Item
• Unnamed Item
• Reconstructing the shape of a tree from observed dissimilarity data
• The computational complexity of inferring rooted phylogenies by parsimony
• NP-hard problems in hierarchical-tree clustering
• The Steiner problem in phylogeny is NP-complete
• Unlikelihood that minimal phylogenies for a realistic biological study can be constructed in reasonable computational time
• Unrooted trees for numerical taxonomy
• Distance matrix of a graph and its realizability

This page was built for publication: Computational complexity of inferring phylogenies from dissimilarity matrices