MJ: TRICLUSTER: an effective algorithm for mining coherent clusters in 3Dmicroarray data

In this paper we introduce a novel algorithm called tri-Cluster, for mining coherent clusters in three-dimensional (3D) gene expression datasets. triCluster can mine arbi-trarily positioned and overlapping clusters, and depending on di®erent parameter values, it can mine di®erent types of clusters, including those with constant or similar values along each dimension, as well as scaling and shifting ex-pression patterns. triCluster relies on graph-based ap-proach to mine all valid clusters. For each time slice, i.e., a gene£sample matrix, it constructs the range multigraph, a compact representation of all similar value ranges between any two sample columns. It then searches for constrained maximal cliques in this multigraph to yield the set of bi-clusters for this time slice. Then triCluster constructs another graph using the biclusters (as vertices) from each time slice; mining cliques from this graph yields the ¯nal set of triclusters. Optionally, triCluster merges/deletes some clusters having large overlaps. We present a useful set of metrics to evaluate the clustering quality, and we show that triCluster can ¯nd signi¯cant triclusters in the real microarray datasets. 1