Clustering gene expression patterns

Recent advances in biotechnology allow researchers to measure expression le vels for thousands of genes simultaneously, across different conditions and over time. Analysis of data produced by such experiments offers potential insight into gene function and regulatory mechanisms. A key step in the ana lysis of gene expression data is the detection of groups of genes that mani fest similar expression patterns. The corresponding algorithmic problem is to cluster multicondition gene expression patterns, In this paper we descri be a novel clustering algorithm that was developed for analysis of gene exp ression data. We define an appropriate stochastic error model on the input, and prove that under the conditions of the model, the algorithm recovers t he duster structure with high probability, The running time of the algorith m on an n-gene dataset is O{n(2)[log(n)](c)}. We also present a practical h euristic based on the same algorithmic ideas. The heuristic was implemented and its performance is demonstrated on simulated data and on real gene exp ression data, with very promising results.