HP Labs Technical Reports

Clustering Gene Expression Patterns

Ben-Dor, Amir; Yakhini, Zohar

HPL-98-190

Keyword(s): gene expression patterns; clustering; random graphs

Abstract: With the advance of hybridization array technology researchers can measure expression levels of sets of genes across different conditions and over time. Analysis of data produced by such experiments offers potential insight into gene function and regulatory mechanisms. We describe the problem of clustering multi-condition gene expression patterns. We define an appropriate stochastic model of the input, and use this model for performance evaluations. We present a 0 (n(log(n))super c)-time algorithm that recovers cluster structures with high probability, in this model, where n is the number of genes. In addition to the theoretical treatment, we suggest practical heuristic improvements to the algorithm. We demonstrate the algorithm's performance first on simulated data, and then on actual gene expression data.

12 Pages

Back to Index