NeighborJoiningTreeBuilder.php
Builds an unrooted phylogenetic tree from a distance matrix via neighbor-joining Freely inspired by BioPHP's project biophp.org Created 30 September 2026 Last modified 9 October 2026
Table of Contents
Classes
- NeighborJoiningTreeBuilder
- Implements the classic Saitou & Nei (1987) algorithm. At each step, among the currently active clusters, it joins the pair (i, j) minimizing Q(i,j) = (n-2)*D(i,j) - r_i - r_j, where r_i is the sum of i's distances to every other active cluster ; this is what makes neighbor-joining prefer a pair that is close to each other AND far from everything else, rather than simply the closest pair (which is what UPGMA does, and which assumes a molecular clock this algorithm does not need). Ties in Q keep the first pair encountered, in the order of the active clusters (the labels first, then each cluster joined, appended last) - an arbitrary but deterministic choice, the same kind already made by this project's alignment tie-breaking.