An application of zero-suppressed binary decision diagrams to clustering analysis of DNA microarray data

Clustering has been one of the most popular techniques to analyze gene expression data. The biclustering method is two-dimensional clustering of genes and experimental conditions to identify a group of genes that display a coherent behavior in some conditions. Although this method may provide additional insight overlooked by traditional clustering techniques, it is often computationally expensive to perform biclustering on practical gene expression data. In this work, we propose a novel biclustering technique that exploits the zero-suppressed binary decision diagrams (ZBDDs) to cope with such a computational challenge. The ZBDDs are a variant of the reduced ordered binary decision diagrams that have found a widespread use in optimization and verification of VLSI digital circuits. Our experimental results demonstrate that the ZBDDs can indeed extend the scalability of our biclustering algorithm substantially, thus enabling us to apply it to a wider spectrum of gene expression data.