Service
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.
- NewickReader
- A small recursive-descent parser over the Newick grammar (J. Felsenstein's specification) :
tree := subtree ";"
subtree := ("(" subtree ("," subtree)* ")")? label? (":" number)?
Blanks, tabs and newlines may appear anywhere but inside an unquoted label or a branch length,
and so may comments in square brackets, NHX annotations ("[&&NHX:S=human]") included : both are
skipped. A quoted label ('Homo sapiens (human)') may hold any character, a single quote being
written twice. An unquoted label runs until the next structural character, blank or comment.
- 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.