Bioinformatics Vol. 17 no. 5 2001
Pages 405-414
© 2001 Oxford University Press
Analysis of temporal gene expression profiles: clustering by simulated annealing and determining the optimal number of clusters
Biogen Inc., 14 Cambridge Center, Cambridge, MA 02142, USA
Received on August 17, 2000
; revised on October 9, 2000
; accepted on October 10, 2000
Motivation: Cluster analysis of genome-wide expression data from DNA microarray hybridization studies has proved to be a useful tool for identifying biologically relevant groupings of genes and samples. In the present paper, we focus on several important issues related to clustering algorithms that have not yet been fully studied.
Results: We describe a simple and robust algorithm for the clustering of temporal gene expression profiles that is based on the simulated annealing procedure. In general, this algorithm guarantees to eventually find the globally optimal distribution of genes over clusters. We introduce an iterative scheme that serves to evaluate quantitatively the optimal number of clusters for each specific data set. The scheme is based on standard approaches used in regular statistical tests. The basic idea is to organize the search of the optimal number of clusters simultaneously with the optimization of the distribution of genes over clusters. The efficiency of the proposed algorithm has been evaluated by means of a reverse engineering experiment, that is, a situation in which the correct distribution of genes over clusters is known a priori. The employment of this statistically rigorous test has shown that our algorithm places greater than 90% genes into correct clusters. Finally, the algorithm has been tested on real gene expression data (expression changes during yeast cell cycle) for which the fundamental patterns of gene expression and the assignment of genes to clusters are well understood from numerous previous studies.
Availability: The source code of the program implementing the algorithm is available upon request from the authors.
Contact: alex_ lukashin{at}biogen.com
* To whom correspondence should be addressed.
CiteULike 
Connotea 
Del.icio.us What's this?
This article has been cited by other articles:
|
|
 |
|
  A. Bhattacharya and R. K. De Divisive Correlation Clustering Algorithm (DCCA) for grouping of genes: detecting varying patterns in expression profiles Bioinformatics, June 1, 2008; 24(11): 1359 - 1366. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
M. J. Nueda, A. Conesa, J. A. Westerhuis, H. C. J. Hoefsloot, A. K. Smilde, M. Talon, and A. Ferrer Discovering gene expression patterns in time course microarray experiments by ANOVA SCA Bioinformatics, July 15, 2007; 23(14): 1792 - 1800. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
D.-W. Kim, K.-Y. Lee, K. H. Lee, and D. Lee Towards clustering of incomplete microarray data without the use of imputation Bioinformatics, January 1, 2007; 23(1): 107 - 113. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
A. Conesa, M. J. Nueda, A. Ferrer, and M. Talon maSigPro: a method to identify significantly differential expression profiles in time-course microarray experiments Bioinformatics, May 1, 2006; 22(9): 1096 - 1102. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 P. Larranaga, B. Calvo, R. Santana, C. Bielza, J. Galdiano, I. Inza, J. A. Lozano, R. Armananzas, G. Santafe, A. Perez, et al. Machine learning in bioinformatics Brief Bioinform, March 1, 2006; 7(1): 86 - 112. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
X. Leng and H.-G. Muller Classification using functional data analysis for temporal gene expression data Bioinformatics, January 1, 2006; 22(1): 68 - 76. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 K. Dolinski and D. Botstein Changing perspectives in yeast research nearly a decade after the genome sequence Genome Res., December 1, 2005; 15(12): 1611 - 1619. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 D. W. Mount and R. Pandey Using bioinformatics and genome analysis for new therapeutic interventions Mol. Cancer Ther., October 1, 2005; 4(10): 1636 - 1643. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
D.-W. Kim, K. H. Lee, and D. Lee Detecting clusters of different geometrical shapes in microarray gene expression data Bioinformatics, May 1, 2005; 21(9): 1927 - 1934. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
F. D. Gibbons and F. P. Roth Judging the Quality of Gene Expression-Based Clustering Methods Using Gene Annotation Genome Res., October 1, 2002; 12(10): 1574 - 1581. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 N. Wicker, D. Dembele, W. Raffelsberger, and O. Poch Density of points clustering, application to transcriptomic data analysis Nucleic Acids Res., September 15, 2002; 30(18): 3992 - 4000. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 X. L. Xu, J. M. Olson, and L. P. Zhao A regression-based method to identify differentially expressed genes in microarray time course studies and its application in an inducible Huntington's disease transgenic model Hum. Mol. Genet., August 15, 2002; 11(17): 1977 - 1985. [Abstract] [Full Text] [PDF]
|
|