CLICK and EXPANDER: a system for clustering and visualizing gene expression data

Motivation: Microarrays have become a central tool in bio-logical research. Their applications range from functional annotation to tissue classification and genetic network infer-ence. A key step in the analysis of gene expression data is the identification of groups of genes that manifest similar expres-sion patterns. This translates to the algorithmic problem of clustering genes based on their expression patterns. Results: We present a novel clustering algorithm, called CLICK, and its applications to gene expression analysis. The algorithm utilizes graph-theoretic and statistical techniques to identify tight groups (kernels) of highly similar elements, which are likely to belong to the same true cluster. Several heur-istic procedures are then used to expand the kernels into the full clusters. We report on the application of CLICK to a vari-ety of gene expression data sets. In all those applications it outperformed extant algorithms according to several common figures of merit. We also point out that CLICK can be success-fully used for the identification of common regulatory motifs in the upstream regions of co-regulated genes. Furthermore, we demonstrate how CLICK can be used to accurately classify tissue samples into disease types, based on their expression profiles. Finally, we present a new java-based graphical tool, called EXPANDER, for gene expression analysis and visuali-zation, which incorporates CLICK and several other popular clustering algorithms