Clustering Gene Expression Patterns

Ben-Dor, Amir ; Yakhini, Zohar

HP Development Company

关键词: gene expression patterns;    clustering;    random graphs;   

RP-ID  :  HPL-98-190

学科分类：计算机科学（综合）

美国|英语

来源: HP Labs

【 摘 要 】

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