A Condition-Enumeration Tree method for mining biclusters from DNA microarray data sets.

Biclustering, which performs simultaneous clustering of rows (e.g., genes) and columns (e.g., conditions), has proved of great value for finding interesting patterns from microarray data. To find biclusters, a model called pCluster was proposed. A pCluster consists of a set of genes and a set of conditions, where the expression levels of these genes have a similar variation under these conditions. Based on this model, most of the previous methods need to compute MDSs (maximum dimension sets) for every two genes in the microarray data. Since the number of genes is far larger than the number of conditions, this step is inefficient. Another method called MicroCluster was proposed. This method does not compute MDSs for every two genes, and transforms the problem into a graph problem. However, it needs to solve the Maximal Clique problem, which is NP-Complete. To avoid the above disadvantages, in this paper, we propose a new method, CE-Tree (Condition-Enumeration Tree), for finding pClusters. Instead of generating MDSs for every two genes, we generate only MDSs for every two conditions. Then, based only on these MDSs, we expand the CE-Tree in a special local breadth-first within global depth-first manner to efficiently find all pClusters. We also utilize the idea of the traditional hash join approach to efficiently support the CE-Tree. From the simulation results, we show that the CE-Tree method could find pClusters more efficiently than those previous methods.