Identification of co-regulation patterns by unsupervised cluster analysis of gene expression data

1. A computer implemented method for identifying co-regulation patterns within gene expression data comprising gene expression levels, the method comprising:

(a) inputting the data into a computer system having a memory and a processor for executing a clustering algorithm;

(b) selecting a clustering algorithm based on a dissimilarity measure between pairs of principal components of the gene expression levels;

(c) randomly assigning class labels to the gene expression levels;

(d) defining a plurality of clusters of gene expression levels within each labeled class;

(e) measuring dissimilarity between each cluster of gene expression levels by measuring a residual of a fit of one cluster onto another cluster, wherein the residual fit comprises using a fit that is invariant with respect to affine transformations, wherein the affine transformations comprise a combination of translation, scaling and rotation;

(f) reassigning gene expression levels to the labeled class with the most similar cluster;

(g) repeating steps (d) through (f) until assignment of gene expression levels to the labeled classes remains constant; and

(h) displaying a graph showing the gene expression levels clustered into the labeled classes, wherein the labeled classes correspond to co-regulation activity.

2. The method of claim 1 , wherein the clustering algorithm is a k-means algorithm.

3. The method of claim 1 , further comprising, prior to step (b), ranking the gene expression data according to one or more quality criteria and using a pre-determined fraction of top ranked gene expression data for steps (b) through (g).

4. The method of claim 3 , wherein the one or more quality criteria are selected from saliency, smoothness and reliability.

5. The method of claim 1 , wherein the gene expression levels comprise mRNA expression levels measured on a microarray.

6. The method of claim 1 , wherein the gene expression levels are measured at different time steps.

7. A computer implemented method for identifying co-regulation patterns within a dataset comprising gene expression levels, the method comprising:

inputting the dataset into a computer system having a memory and a processor for executing a clustering algorithm;

selecting a plurality of granularity levels k, and for each granularity level k:

(a) inducing perturbations in the dataset to generate a modified dataset;

(b) applying the clustering algorithm to the at least one modified dataset to produce k clusters under each of the perturbations;

(c) creating a data subset comprising the clusters identified in step (b);

(d) applying the clustering algorithm to the data subset using the same value of k clusters;

(e) determining the stability of the clusterings at each granularity level k by measuring dissimilarity between data in the data subset and the cluster center for the cluster into which the data was assigned;

measuring fit of the data to the cluster centers for all k granularity levels, wherein the fit comprises using a fit that is invariant with respect to affine transformations, wherein the affine transformations comprise a combination of translation, scaling and rotation;

selecting from among the plurality of granularity levels an optimum granularity level k corresponding to the best fit;

generating an output comprising the dataset clustered into a plurality of subsets corresponding to the optimal granularity level k; and

displaying a graph showing the gene expression levels clustered into the plurality of subsets, wherein the subsets correspond to co-regulation activity.

8. The method of claim 7 , wherein the perturbations comprise a combination of one or more of sub-sampling the dataset, changing initialization of the clustering algorithm, and adding noise to the dataset.

9. The method of claim 7 , further comprising, prior to selecting a plurality of granularity levels, ranking the gene expression data according to one or more quality criteria and selecting a pre-determined fraction of top ranked gene expression data.

10. The method of claim 9 , wherein the one or more quality criteria are selected from saliency, smoothness and reliability.

11. The method of claim 7 , wherein the gene expression levels comprise mRNA expression levels measured on a microarray.

12. The method of claim 7 , wherein the gene expression levels are measured at different time steps.

13. A computer implemented method for determining co-regulation patterns within a gene expression dataset comprising gene expression levels, the method comprising:

inputting the dataset into a computer system having a memory and a processor for executing a clustering algorithm;

randomly assigning labels to the gene expression levels in the dataset by partitioning the dataset into k subsets, wherein k has a minimum number and a maximum number;

for each value of k, beginning with the minimum value, for each pair of subsets, computing a correlation score on the intersection between the pair of subsets, wherein the correlation score comprises a similarity measure between the pair of subsets and the greatest similarity has the highest score; and

displaying a histogram comprising a distribution of the correlation scores for each value of k, wherein the distribution comprising the highest value of k that remains concentrated near the highest correlation score corresponds to a clustering of the gene expression levels according to co-regulation activity.

14. The method of claim 13 , wherein the step of computing the correlation score comprises selecting a fraction of the gene expression levels in each subset for comparison with other subsets.

15. The method of claim 14 , wherein the fraction is greater than 0.5.

16. The method of claim 13 , further comprising, prior to randomly assigning labels, ranking the gene expression data according to one or more quality criteria and selecting a pre-determined fraction of top ranked gene expression data.

17. The method of claim 16 , wherein the one or more quality criteria are selected from saliency, smoothness and reliability.

18. The method of claim 13 , wherein the gene expression levels comprise mRNA expression levels measured on a microarray.

19. The method of claim 13 , wherein the gene expression levels are measured at different time steps.

20. A computer implemented method for identifying co-regulation patterns within a gene expression dataset comprising gene expression levels, the method comprising:

inputting the dataset into a computer system having a memory and a processor for executing a clustering algorithm;

randomly assigning labels to the gene expression levels in the dataset by partitioning the dataset into k subsamples, wherein k has a minimum number and a maximum number;

representing each subsample by a matrix;

computing a dot product between pairs of subsamples to generate a correlation score on an intersection between the pair of subsamples, wherein the correlation score comprises a similarity measure between the pair of subsamples and the greatest similarity has the highest score; and

generating a display comprising a distribution of the correlation scores for each value of k, wherein the distribution comprising the highest value of k that remains concentrated near the highest correlation score corresponds to a clustering of the gene expression levels according to co-regulation activity.

21. The method of claim 20 , further comprising, prior to randomly assigning labels, ranking the gene expression data according to one or more quality criteria and using a pre-determined fraction of top ranked gene expression data for subsequent steps.

22. The method of claim 21 , wherein the one or more quality criteria are selected from saliency, smoothness and reliability.

23. The method of claim 20 , wherein the gene expression levels comprise mRNA expression levels measured on a microarray.

24. The method of claim 20 , wherein the gene expression levels are measured at different time steps.