triCluster: An Effective Algorithm for Mining Coherent Clusters in 3D Microarray Data

In this paper we introduce a novel algorithm called triCluster, for mining coherent clusters in three-dimensional (3D) gene expression datasets. triCluster can mine arbitrarily 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 expression patterns. triCluster relies on graph-based approach to mine all valid clusters. For each time slice, i.e., a genesample 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 biclusters 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 final 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 find significant triclusters in the real microarray datasets