Unweighted pair group method with arithmetic mean (UPGMA) is a phylogeny reconstruction method.
- Input
- Matrix of pairwise distances
- Output
- Phylogeny
- Algorithm
- Repeatedly merge the nearest two clusters. The distance between clusters is the average of all pairwise distances between them. When merging two clusters, the distances of the new cluster are the weighted averages of distances from the two clusters being merged.
- Complexity
- \(O(n^3)\) naive, \(O(n^2 \ln n)\) using heap.