Paper Info
Title
UPGMA and the normalized equidistant minimum evolution problem.
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(log2⁡n) of the optimum.
Year
DOI
Venue
2018
10.1016/j.tcs.2018.01.022
Theoretical Computer Science
Keywords
DocType
Volume
UPGMA,Minimum evolution,Balanced minimum evolution,Hierarchical clustering
Journal
721
ISSN
Citations 
PageRank 
0304-3975
0
0.34
References 
Authors
14
3
Name
Order
Citations
PageRank
Vincent Moulton1397.46
Andreas Spillner220749.13
Taoyang Wu37413.24