User:Manudouz/sandbox/Complete-linkage clustering

Working example[edit]

This working example is based on a JC69 genetic distance matrix computed from the 5S ribosomal RNA sequence alignment of five bacteria: Bacillus subtilis ( $a$ ), Bacillus stearothermophilus ( $b$ ), Lactobacillus viridescens ( $c$ ), Acholeplasma modicum ( $d$ ), and Micrococcus luteus ( $e$ ).^[1]^[2]

First step[edit]

First clustering

Let us assume that we have five elements $(a,b,c,d,e)$ and the following matrix $D_{1}$ of pairwise distances between them:

	a	b	c	d	e
a	0	17	21	31	23
b	17	0	30	34	21
c	21	30	0	28	39
d	31	34	28	0	43
e	23	21	39	43	0

In this example, $D_{1}(a,b)=17$ is the smallest value of $D_{1}$ , so we join elements $a$ and $b$ .

First branch length estimation

Let $u$ denote the node to which $a$ and $b$ are now connected. Setting $\delta (a,u)=\delta (b,u)=D_{1}(a,b)/2$ ensures that elements $a$ and $b$ are equidistant from $u$ . This corresponds to the expectation of the ultrametricity hypothesis. The branches joining $a$ and $b$ to $u$ then have lengths $\delta (a,u)=\delta (b,u)=17/2=8.5$ (see the final dendrogram)

First distance matrix update

We then proceed to update the initial proximity matrix $D_{1}$ into a new proximity matrix $D_{2}$ (see below), reduced in size by one row and one column because of the clustering of $a$ with $b$ . Bold values in $D_{2}$ correspond to the new distances, calculated by retaining the maximum distance between each element of the first cluster $(a,b)$ and each of the remaining elements:

$D_{2}((a,b),c)=max(D_{1}(a,c),D_{1}(b,c))=max(21,30)=30$

$D_{2}((a,b),d)=max(D_{1}(a,d),D_{1}(b,d))=max(31,34)=34$

$D_{2}((a,b),e)=max(D_{1}(a,e),D_{1}(b,e))=max(23,21)=23$

Italicized values in $D_{2}$ are not affected by the matrix update as they correspond to distances between elements not involved in the first cluster.

Second step[edit]

Second clustering

We now reiterate the three previous steps, starting from the new distance matrix $D_{2}$ :

	(a,b)	c	d	e
(a,b)	0	30	34	23
c	30	0	28	39
d	34	28	0	43
e	23	39	43	0

Here, $D_{2}((a,b),e)=23$ is the lowest value of $D_{2}$ , so we join cluster $(a,b)$ with element $e$ .

Second branch length estimation

Let $v$ denote the node to which $(a,b)$ and $e$ are now connected. Because of the ultrametricity constraint, the branches joining $a$ or $b$ to $v$ , and $e$ to $v$ , are equal and have the following total length: $\delta (a,v)=\delta (b,v)=\delta (e,v)=23/2=11.5$

We deduce the missing branch length: $\delta (u,v)=\delta (e,v)-\delta (a,u)=\delta (e,v)-\delta (b,u)=11.5-8.5=3$ (see the final dendrogram)

Second distance matrix update

We then proceed to update the $D_{2}$ matrix into a new distance matrix $D_{3}$ (see below), reduced in size by one row and one column because of the clustering of $(a,b)$ with $e$ :

$D_{3}(((a,b),e),c)=max(D_{2}((a,b),c),D_{2}(e,c))=max(30,39)=39$

$D_{3}(((a,b),e),d)=max(D_{2}((a,b),d),D_{2}(e,d))=max(34,43)=43$

Third step[edit]

Third clustering

We again reiterate the three previous steps, starting from the updated distance matrix $D_{3}$ .

	((a,b),e)	c	d
((a,b),e)	0	39	43
c	39	0	28
d	43	28	0

Here, $D_{3}(c,d)=28$ is the smallest value of $D_{3}$ , so we join elements $c$ and $d$ .

Third branch length estimation

Let $w$ denote the node to which $c$ and $d$ are now connected. The branches joining $c$ and $d$ to $w$ then have lengths $\delta (c,w)=\delta (d,w)=28/2=14$ (see the final dendrogram)

Third distance matrix update

There is a single entry to update: $D_{4}((c,d),((a,b),e))=(D_{3}(c,((a,b),e)),D_{3}(d,((a,b),e)))=(39,43)=43$

Final step[edit]

The final $D_{4}$ matrix is:

	((a,b),e)	(c,d)
((a,b),e)	0	43
(c,d)	43	0

So we join clusters $((a,b),e)$ and $(c,d)$ .

Let $r$ denote the (root) node to which $((a,b),e)$ and $(c,d)$ are now connected. The branches joining $((a,b),e)$ and $(c,d)$ to $r$ then have lengths: