Clustering gene expression patterns

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 O(n(log(n))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 a practical heuristic approach based on the same ideas.We demonstrate the algorithm's performance first on simulated data, and then on actual gene expression data. IntroductionIn any living cell that undergoes a biological process, different subsets of its genes are expressed in different stages of the process.The particular genes expressed at a given stage and their relative abundance are crucial to the cell's proper function.Measuring gene expression levels in different stages, different body tissues, and different organisms is instrumental in understanding biological processes.Such information can help the characterization of gene/function relationships, the determination of effects of experimental treatments, and the understanding of many other molecular biological processes.