QIAGEN Bioinformatics Manuals

Hierarchical Clustering of Samples

A hierarchical clustering of samples is a tree representation of their relative similarity.

The tree structure is generated by

letting each sample be a cluster
calculating pairwise distances between all clusters
joining the two closest clusters into one new cluster
iterating 2-3 until there is only one cluster left (which will contain all samples).

The tree is drawn so that the distances between clusters are reflected by the lengths of the branches in the tree. Thus, features with expression profiles that closely resemble each other have short distances between them, those that are more different, are placed further apart.

(See [Eisen et al., 1998] for a classical example of application of a hierarchical clustering algorithm in microarray analysis. The example is on features rather than samples).

To start the clustering:

Toolbox | Expression Analysis ()| Quality Control () | Hierarchical Clustering of Samples ()

Select a number of samples ( () or ()) or an experiment () and click Next.

This will display a dialog as shown in figure 25.32. The hierarchical clustering algorithm requires that you specify a distance measure and a cluster linkage. The similarity measure is used to specify how distances between two samples should be calculated. The cluster distance metric specifies how you want the distance between two clusters, each consisting of a number of samples, to be calculated.

Image sample_clustering_step2
Figure 25.32: Parameters for hierarchical clustering of samples.

There are three kinds of Distance measures:

Euclidean distance. The ordinary distance between two points - the length of the segment connecting them. If $u=(u_1,u_2,\dots, u_n)$ and $v=(v_1,v_2,\dots, v_n)$ , then the Euclidean distance between and is

$\displaystyle \vert u-v\vert = \sqrt{\sum_{i=1}^n (u_i-v_i)^2}.$
1 - Pearson correlation. The Pearson correlation coefficient between two elements and is defined as

$\displaystyle r = \frac{1}{n-1}\sum_{i=1}^n (\frac{x_i-\overline{x}}{s_x})*(\frac{y_i-\overline{y}}{s_y})$
where $\overline{x}/\overline{y}$ is the average of values in and is the sample standard deviation of these values. It takes a value $\in [-1,1]$ . Highly correlated elements have a high absolute value of the Pearson correlation, and elements whose values are un-informative about each other have Pearson correlation 0. Using $1-\vert Pearson correlation\vert$ as distance measure means that elements that are highly correlated will have a short distance between them, and elements that have low correlation will be more distant from each other.
Manhattan distance. The Manhattan distance between two points is the distance measured along axes at right angles. If $u=(u_1,u_2,\dots, u_n)$ and $v=(v_1,v_2,\dots, v_n)$ , then the Manhattan distance between and is

$\displaystyle \vert u-v\vert = \sum_{i=1}^n \vert u_i-v_i\vert.$

The possible cluster linkages are:

Single linkage. The distance between two clusters is computed as the distance between the two closest elements in the two clusters.
Average linkage. The distance between two clusters is computed as the average distance between objects from the first cluster and objects from the second cluster. The averaging is performed over all pairs , where is an object from the first cluster and is an object from the second cluster.
Complete linkage. The distance between two clusters is computed as the maximal object-to-object distance , where comes from the first cluster, and comes from the second cluster. In other words, the distance between two clusters is computed as the distance between the two farthest objects in the two clusters.

At the bottom, you can select which values to cluster (see Selecting transformed and normalized values for analysis).

Click Finish to start the tool.

Note: To be run on a server, the tool has to be included in a workflow, and the results will be displayed in a a stand-alone new heat map rather than added into the input experiment table.

Subsections

Result of hierarchical clustering of samples

Browse the manual

Hierarchical Clustering of Samples