UPGMA tree of five bacteria

Distances between the 5S ribosomal RNAs of five bacteria, the classic example of the UPGMA method. UPGMA joins the two closest groups at each step and averages their distances, weighted by the size of the groups.

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
33
34
35
36

public function upgma(UpgmaTreeBuilderInterface $upgmaTreeBuilder)
{
    // Distances between the 5S ribosomal RNAs of five bacteria
    $oMatrix = new DistanceMatrix(
        ["Bacillus subtilis", "Bacillus stearothermophilus", "Lactobacillus viridescens",
            "Acholeplasma modicum", "Micrococcus luteus"],
        [
            [ 0, 17, 21, 31, 23],
            [17,  0, 30, 34, 21],
            [21, 30,  0, 28, 39],
            [31, 34, 28,  0, 43],
            [23, 21, 39, 43,  0],
        ]
    );
 
    $oTree = $upgmaTreeBuilder->build($oMatrix);
 
    // UPGMA assumes a molecular clock: every leaf is at the same distance from the root
    $aRootToLeaf = [];
    $fWalk = function (PhylogeneticNode $oNode, float $fDepth) use (&$fWalk, &$aRootToLeaf) {
        if ($oNode->isLeaf()) {
            $aRootToLeaf[$oNode->getName()] = $fDepth;
        }
        foreach ($oNode->getChildren() as $oChild) {
            $fWalk($oChild, $fDepth + $oChild->getBranchLength());
        }
    };
    $fWalk($oTree, 0.0);
 
    return $this->render('default/phylogeneticsUpgma.html.twig', [
        'matrix'     => $oMatrix,
        'tree'       => $oTree,
        'newick'     => $oTree->toNewick(),
        'rootToLeaf' => $aRootToLeaf,
    ]);
}
2

Result

Result returned by BioPHP for the demonstration data.

Distance matrix
Bacillus subtilisBacillus stearothermophilusLactobacillus viridescensAcholeplasma modicumMicrococcus luteus
Bacillus subtilis 017213123
Bacillus stearothermophilus 170303421
Lactobacillus viridescens 213002839
Acholeplasma modicum 313428043
Micrococcus luteus 232139430
Tree (branch lengths after each name) 
┐
├── ┐ : 5.5
│   ├── Micrococcus luteus : 11
│   └── ┐ : 2.5
│       ├── Bacillus subtilis : 8.5
│       └── Bacillus stearothermophilus : 8.5
└── ┐ : 2.5
    ├── Lactobacillus viridescens : 14
    └── Acholeplasma modicum : 14
Distance from the root to each leaf
Micrococcus luteus16.5
Bacillus subtilis16.5
Bacillus stearothermophilus16.5
Lactobacillus viridescens16.5
Acholeplasma modicum16.5

Every leaf lies at the same distance from the root: UPGMA builds an ultrametric tree, as if every lineage evolved at the same rate (molecular clock).

Newick 
(('Micrococcus luteus':11,('Bacillus subtilis':8.5,'Bacillus stearothermophilus':8.5):2.5):5.5,('Lactobacillus viridescens':14,'Acholeplasma modicum':14):2.5);

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.