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

• US 8,489,531 B2
• Filed: 02/02/2011
• Issued: 07/16/2013
• Est. Priority Date: 05/18/2001
• Status: Expired due to Fees

• Current Assignee: Curtis Anderson, Health Discovery Corporation, James Roberts, Joe Mckenzie, Jules B. Paderewski, Julian N. Stern, Memorial Health Systems Incorporated, Timothy P. O'Hayer
• Original Assignee: Health Discovery Corporation
• Inventors: Ben Hur, Asa, Elisseeff, Andre, Guyon, Isabelle
• Primary Examiner(s): Chaki, Kakali
• Assistant Examiner(s): Bharadwaj, Kalpana
• Application Number:
  US13/019,585
• Publication Number:
  US 20110125683A1
• Time in Patent Office: 895 Days
• Field of Search: 800/294, 435/193
• US Class Current: 706/45
• CPC Class Codes: G06F 16/35 Clustering; Classification
• CPC Class Codes: G06F 18/23 Clustering techniques
• CPC Class Codes: G16B 25/00 ICT specially adapted for hybridisation; ICT specially adapted for gene or protein expression
• CPC Class Codes: G16B 25/10 Gene or protein expression profiling; Expression-ratio estimation or normalisation
• CPC Class Codes: G16B 40/00 ICT specially adapted for biostatistics; ICT specially adapted for bioinformatics-related machine learning or data mining, e.g. knowledge discovery or pattern finding
• CPC Class Codes: G16B 40/20 Supervised data analysis
• CPC Class Codes: G16B 40/30 Unsupervised data analysis

Abstract

A method is provided for unsupervised clustering of gene expression data to identify co-regulation patterns. A clustering algorithm randomly divides the data into k different subsets and measures the similarity between pairs of datapoints within the subsets, assigning a score to the pairs based on similarity, with the greatest similarity giving the highest correlation score. A distribution of the scores is plotted for each k. The highest value of k that has a distribution that remains concentrated near the highest correlation score corresponds to the number of co-regulation patterns.

Claims

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.