UpgmaTreeBuilder.php
Builds a rooted, ultrametric tree from a distance matrix via UPGMA Freely inspired by BioPHP's project biophp.org Created 30 September 2026 Last modified 2 October 2026
Table of Contents
Classes
- UpgmaTreeBuilder
- Migrated from biotools' Service/DistanceAmongSequencesManager.php::upgmaClustering(), with one deliberate scientific correction : the legacy newArray() always averages a merged cluster's two distances 50/50 - ($d[k][x] + $d[k][y]) / 2 - regardless of how many original taxa x and y already represent. That is WPGMA (Weighted Pair Group Method, despite the name a SIMPLE, unweighted average at every step), not UPGMA ; true UPGMA weights the average by cluster size - (|x|*d[k][x] + |y|*d[k][y]) / (|x|+|y|) - which is what makes it equal the average of every original pairwise distance between the two merged groups. This class implements genuine, size-weighted UPGMA. At each step it merges the two active clusters with the smallest distance (ties keep the first pair encountered, the same deterministic convention NeighborJoiningTreeBuilder already uses) into a new cluster at height = distance/2, giving each side a branch length of (newHeight - thatSide'sOwnHeight) - the defining "ultrametric" property of a UPGMA tree : every leaf ends up exactly as far from the root as every other leaf.