HP Labs Technical Reports
Click here for full text:
Clustering Gene Expression Patterns
Ben-Dor, Amir; Yakhini, Zohar
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.
Back to Index