Neighbor-Joining versus UPGMA

These distances fit a tree exactly, but its lineages evolve at different rates: b, for instance, has a longer branch than a. Both trees are built from the same matrix, then the distances are read back on each tree, by adding up the branches between two leaves.

1

Starting code

This is the PHP code used by this example.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

public function neighborJoining(
    UpgmaTreeBuilderInterface $upgmaTreeBuilder,
    NeighborJoiningInterface $neighborJoining
) {
    // Distances that fit a tree exactly, but where the lineages evolve at different rates
    $oMatrix = new DistanceMatrix(
        ["a", "b", "c", "d", "e"],
        [
            [0,  5,  9,  9, 8],
            [5,  0, 10, 10, 9],
            [9, 10,  0,  8, 7],
            [9, 10,  8,  0, 3],
            [8,  9,  7,  3, 0],
        ]
    );
 
    $oNjTree = $neighborJoining->build($oMatrix);
    $oUpgmaTree = $upgmaTreeBuilder->build($oMatrix);
 
    // Read the distances back on each tree (sum of the branches between two leaves):
    // which one gives the matrix back?
    $aNjDistances = $this->treeDistances($oNjTree);
    $aUpgmaDistances = $this->treeDistances($oUpgmaTree);
 
    return $this->render('default/phylogeneticsNeighborJoining.html.twig', [
        'matrix'          => $oMatrix,
        'njTree'          => $oNjTree,
        'upgmaTree'       => $oUpgmaTree,
        'njDistances'     => $aNjDistances,
        'upgmaDistances'  => $aUpgmaDistances,
    ]);
}
2

Result

Result returned by BioPHP for the demonstration data.

Distance matrix
abcde
a 05998
b 5010109
c 910087
d 910803
e 89730
Neighbor-Joining 
┐
├── d : 2
├── e : 1
└── ┐ : 2
    ├── c : 4
    └── ┐ : 3
        ├── a : 2
        └── b : 3

(d:2,e:1,(c:4,(a:2,b:3):3):2);

PairMatrixOn the tree
a – b 5 5 ✓
a – c 9 9 ✓
a – d 9 9 ✓
a – e 8 8 ✓
b – c 10 10 ✓
b – d 10 10 ✓
b – e 9 9 ✓
c – d 8 8 ✓
c – e 7 7 ✓
d – e 3 3 ✓

Neighbor-joining gives every distance back: on distances that fit a tree, it recovers its topology and its branch lengths. The tree is unrooted, its last node joins three branches.

UPGMA 
┐
├── ┐ : 2.083
│   ├── a : 2.5
│   └── b : 2.5
└── ┐ : 0.833
    ├── c : 3.75
    └── ┐ : 2.25
        ├── d : 1.5
        └── e : 1.5

((a:2.5,b:2.5):2.083333333333333,(c:3.75,(d:1.5,e:1.5):2.25):0.833333333333333);

PairMatrixOn the tree
a – b 5 5 ✓
a – c 9 9.167 ✗
a – d 9 9.167 ✗
a – e 8 9.167 ✗
b – c 10 9.167 ✗
b – d 10 9.167 ✗
b – e 9 9.167 ✗
c – d 8 7.5 ✗
c – e 7 7.5 ✗
d – e 3 3 ✓

UPGMA forces every leaf to the same distance from the root: the distances do not come back, because the molecular clock it assumes does not hold here.

The code above is the one actually executed by this page. Find the other examples in the left-hand column, or the tools in BioTools.