UPGMA and the normalized equidistant minimum evolution problem

DOI10.1016/J.TCS.2018.01.022MaRDI QIDQ1704587zbMATH OpenOpenAlexFDO

Authors Andreas Spillner, Taoyang Wu, Vincent Moulton

Publication date 12 March 2018

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1704.00497, https://ueaeprints.uea.ac.uk/id/eprint/66076/4/Accepted_manuscript.pdf

zbMATH Keywords

hierarchical clusteringbalanced minimum evolutionUPGMAminimum evolution

Mathematics Subject Classification ID

Classification and discrimination; cluster analysis (statistical aspects) (62H30) Problems related to evolution (92D15) Analysis of algorithms (68W40)

Abstract: UPGMA (Unweighted Pair Group Method with Arithmetic Mean) is a widely used clustering method. Here we show that UPGMA is a greedy heuristic for the normalized equidistant minimum evolution (NEME) problem, that is, finding a rooted tree that minimizes the minimum evolution score relative to the dissimilarity matrix among all rooted trees with the same leaf-set in which all leaves have the same distance to the root. We prove that the NEME problem is NP-hard. In addition, we present some heuristic and approximation algorithms for solving the NEME problem, including a polynomial time algorithm that yields a binary, rooted tree whose NEME score is within O(log^2 n) of the optimum. We expect that these results to eventually provide further insights into the behavior of the UPGMA algorithm.

Recommendations

• An improvement for unweighted pair group method with arithmetic mean and its application
• Optimal implementations of UPGMA and other common clustering algorithms
• Polyhedral combinatorics of UPGMA cones
• Approximating the balanced minimum evolution problem
• The minimum evolution problem: Overview and classification

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1865935 (Why is no real title available?)
• A robust model for finding optimal evolutionary tree
• A tight bound on approximating arbitrary metrics by tree metrics
• Approximating the balanced minimum evolution problem
• Computational complexity of inferring phylogenies from dissimilarity matrices
• Consistent formulas for estimating the total lengths of trees
• Cyclic permutations and evolutionary trees
• On the Approximability of Numerical Taxonomy (Fitting Distances by Tree Metrics)
• Performance analysis of hierarchical clustering algorithms
• Polyhedral combinatorics of UPGMA cones
• Robustness of phylogenetic inference based on minimum evolution
• The minimum evolution problem: Overview and classification
• The performance of neighbor-joining methods of phylogenetic reconstruction
• \(O(\sqrt{\log n})\) approximation to sparsest cut in \(\tilde{O}(n^2)\) time

Cited in

(4)

• An improvement for unweighted pair group method with arithmetic mean and its application
• UPGMA clustering revisited: a weight-driven approach to transitive approximation
• Optimal implementations of UPGMA and other common clustering algorithms
• Polyhedral combinatorics of UPGMA cones

This page was built for publication: UPGMA and the normalized equidistant minimum evolution problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1704587)