UPGMA and the normalized equidistant minimum evolution problem

作者：Moulton Vincent; Spillner Andreas; Wu Taoyang^*

来源：Theoretical Computer Science, 2018, 721: 1-15.

DOI：10.1016/j.tcs.2018.01.022

• UPGMA
• Minimum evolution
• Balanced minimum evolution
• Hierarchical clustering

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.

• 出版日期2018-4-18