WPGMA

Uses your system voice; voice and rate in settings.

Snapshot

≈ 4 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

WPGMA (Weighted Pair Group Method with Arithmetic Mean) is a simple agglomerative (bottom-up) hierarchical clustering method, generally attributed to Sokal and Michener. The WPGMA method is similar to its unweighted variant, the UPGMA method.

WPGMA (Weighted Pair Group Method with Arithmetic Mean) is a simple agglomerative (bottom-up) hierarchical clustering method, generally attributed to Sokal and Michener. The WPGMA method is similar to its unweighted variant, the UPGMA method. d_{(i \cup j),k} = \frac{d_{i,k} + d_{j,k}}{2} The WPGMA algorithm produces rooted dendrograms and requires a constant-rate assumption: it produces an ultrametric tree in which the distances from the root to every branch tip are equal. This ultrametricity assumption is called the molecular clock when the tips involve DNA, RNA and protein data. 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 distance matrix D_1 into a new distance 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 averaging distances between each element of the first cluster (a,b) and each of the remaining elements: D_2((a,b),c)=(D_1(a,c) + D_1(b,c))/2=(21+30)/2=25.5 D_2((a,b),d)=(D_1(a,d) + D_1(b,d))/2=(31+34)/2=32.5 D_2((a,b),e)=(D_1(a,e) + D_1(b,e))/2=(23+21)/2=22 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. Here, D_2 ((a,b),e)=22 is the smallest value of D_2 , so we join cluster (a,b) and 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 length: \delta(a,v)=\delta(b,v)=\delta(e,v)=22/2=11 We deduce the missing branch length: \delta(u,v)=\delta(e,v)-\delta(a,u)=\delta(e,v)-\delta(b,u)=11-8.5=2.5 (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)=(D_2((a,b),c) + D_2(e,c))/2=(25.5 + 39)/2=32.25 Of note, this average calculation of the new distance does not account for the larger size of the (a,b) cluster (two elements) with respect to e (one element). Similarly: D_3(((a,b),e),d)=(D_2((a,b),d) + D_2(e,d))/2=(32.5 + 43)/2=37.75 The averaging procedure therefore gives differential weight to the initial distances of matrix D_1 . This is the reason why the method is weighted, not with respect to the mathematical procedure but with respect to the initial distances. 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)))/2=(32.25+37.75)/2=35 \delta(((a,b),e),r)=\delta((c,d),r)=35/2=17.5 We deduce the two remaining branch lengths: \delta(v,r)=\delta(((a,b),e),r)-\delta(e,v)=17.5-11=6.5 \delta(w,r)=\delta((c,d),r)-\delta(c,w)=17.5-14=3.5 \delta(a,r)=\delta(b,r)=\delta(e,r)=\delta(c,r)=\delta(d,r)=17.5 The dendrogram is therefore rooted by r , its deepest node.

Text derived from https://en.wikipedia.org/w/index.php?oldid=1340420136 under CC BY-SA 4.0; modifications have been made.

Sources cited in this revision

1 named source(s) extracted from the cited revision. A source with no author is shown by its publication; nothing is invented.