Significance Analysis and Statistical Mechanics: An Application to Clustering

This Letter addresses the statistical significance of structures in random data: Given a set of vectors and a measure of mutual similarity, how likely is it that a subset of these vectors forms a cluster with enhanced similarity among its elements? The computation of this cluster $p$ value for randomly distributed vectors is mapped onto a well-defined problem of statistical mechanics. We solve this problem analytically, establishing a connection between the physics of quenched disorder and multiple-testing statistics in clustering and related problems. In an application to gene expression data, we find a remarkable link between the statistical significance of a cluster and the functional relationships between its genes.

Figure 1

Clustering a set of random vectors. In a set of randomly chosen vectors, subsets of highly similar elements can arise by chance. Here a cluster is shown with its center of mass pointing upwards, and the shading indicates score contributions. Large clusters with high similarity among their elements occur only in exponentially rare configurations of the random vectors.

Figure 2

Cluster score distributions in random data for fixed and optimal cluster directions. Analytical distributions $p(S)$ (solid lines) are plotted against the score per element, $s=S/N$, and are compared to normalized histograms obtained from numerical experiments with ${10}^6$ samples (symbols). (a) Distribution $p_c(S)$ of the cluster score (2) for a fixed cluster center and data sets of $N=6000$ vectors with $M=70$, with the parameter $\mu =0.1\sqrt{M}$. Error bars show the standard error due to the finite size of the sample. (b) Distribution of the maximum cluster score (6) with the parameter $\mu =0.1\sqrt{M}$ for $N=40$ (triangles), $N=80$ (circles), and $N=120$ (squares), keeping $M/N=0.5$ fixed.

Figure 3

Statistical significance of clusters is correlated with functional annotation for yeast expression data. The diagrams show the significance $p_{\mathrm{GO}}$ of gene annotation terms vs the cluster score significance, traced over a range of the scoring parameter $\mu$ (shown by the color scale) of three representative clusters involved in translation (ribosomal genes), the sulfur metabolic process, and the carbohydrate metabolic process.