NeighborJoiningTreeBuilder
in package
implements
NeighborJoiningInterface
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.
The reduction stops at exactly 3 active clusters rather than 2, because the classic pairwise branch-length formula needs an r_i computed over at least one OTHER active cluster besides the pair being joined ; with only 2 remaining there is none. The last 3 clusters are instead resolved directly into an unrooted, trifurcating root - the natural, un-arbitrary representation of an unrooted tree's last split, and the standard way a neighbor-joining tree is reported. A DistanceMatrix of exactly 1 or 2 taxa is handled as its own trivial case, needing no iteration at all.
On a distance matrix that is perfectly additive (exactly fits some tree), neighbor-joining is guaranteed to recover that tree's exact topology and branch lengths - this is the property this class's regression test fixture is built on and hand-verified against. Class NeighborJoiningTreeBuilder
Tags
Table of Contents
Interfaces
- NeighborJoiningInterface
- Interface NeighborJoiningInterface - builds an unrooted phylogenetic tree from a DistanceMatrix using the Saitou & Nei (1987) neighbor-joining algorithm.
Methods
Methods
build()
public
build(DistanceMatrix $oMatrix) : PhylogeneticNode
Parameters
- $oMatrix : DistanceMatrix