Contents - Index

Clustering

GenEx offers module for hierarchical agglomerate clustering, which is the most common method for grouping data. The construction of a hierarchical agglomerative classification can be achieved by the following general algorithm:

1. Find the two closest objects and merge them into a cluster 

2. Find and merge the next two closest points, where a point is either an individual object or a cluster of objects

3. If more than one cluster remains, return to step 2.

In GenEx hierarchical clustering is represented either by dendrogram or heatmap analysis, both available under the clustering tab in the main window.

Clustering methods

The user can select among different clustering methods and distance measures. 

• Average linkage defines distance between groups as the average of the distances between all pairs of individuals in the two groups. It is sometimes also referred to as UPGMA (Unweighted Pair-Group Method using Arithmetic averages), and is a compromise between the single and complete linkage methods. 

• The complete linkage, also called the furthest neighbor method, is the opposite of the single linkage method. The distance between groups is now defined as the distance between their most remote pair of individuals.

• The single linkage, also called nearest neighbor method, can be used both with similarity measures and with distance measures. Groups are fused according to the distance between their nearest members.

• Ward's method groups to minimize the increase in the variance in distances in the new group. Internal variance is computed as the sum of distances between each sample in the group and the group's centroid. Ward's method tends to produce compact clusters. 

The figures below illustrate single linkage, complete linkage and average linkage methods.

Distance measures

The distances between objects can also be measured differently. Most common for continuous data, where we measure gene expression in copy number or Cq values, are the following.

• Euclidean distance  

• Euclidean squared distance

• Manhattan distance  

For discrete data, e.g. where we for each sample either have expression (1) or no expression (0), we generate distances measures from a contingency table which contains the counts. Here is a general example with two samples X and Y and corresponding formulas for the distance measures Dice coefficient and Jaccard coefficient.

• Dice coefficient = (b + c) / (a + b + c + d)
• Jaccard coefficient = (b + c) / (a + b + c)

We observe the following discrete data for the two samples, and it results in the contingency table given below.

     Sample X = ( 1 , 1 , 0 , 1 , 0 , 0 , 1 )

     Sample Y = ( 0 , 1 , 1 , 0 , 0 , 1 , 1 )

You can also use the following as distance measurements for both continues and discrete data.

• Pearson correlation
• Pearson magnitude = Abs( Pearson correlation) 

When performing hierarchical agglomerate clustering it is good practice to analyze the data with a few different methods to verify that the main clusters predicted are independent of method used, and also collect experience on what method suits the particular data best. Below, average linkage, complete linkage, and the Ward algorithm all predict three main clusters.

Note that data can be clustered as groups of genes or groups of samples. Genes that form a cluster have similar expression, while samples that are, e.g. negative and positive for a disease, should fall in different groups if proper expression markers are measured. Transpose the data to switch between classification of genes and classification of samples.

References

G.H. Lance and W.T. Williams (1966). A general theory of classificatory sorting strategies. I. Hierarchical Systems. The Computer Journal, 9(4), pp 373-380.

J. H. Ward (1963). Hierarchical grouping to optimize an objective function. Journal of Amer. Statist. Assoc. 58:  pp 236-244.