DeBi: Discovering Differentially Expressed Biclusters using a Frequent Itemset Approach

Here we present a fast biclustering algorithm called DeBi (Differentially Expressed BIclusters). The algorithm is based on a well known data mining approach called frequent itemset. It discovers maximum size homogeneous biclusters in which each gene is strongly associated with a subset of samples. We evaluate the performance of DeBi on a yeast dataset, on synthetic datasets and on human datasets.We demonstrate that the DeBi algorithm provides functionally more coherent gene sets compared to standard clustering or biclustering algorithms using biological validation measures such as Gene Ontology term and Transcription Factor Binding Site enrichment. We show that DeBi is a computationally efficient and powerful tool in analyzing large datasets. The method is also applicable on multiple gene expression datasets coming from different labs or platforms.In recent years, various high throughput technologies such as cDNA microarrays, oligo-microarrays and sequence-based approaches (RNA-Seq) for transcriptome profiling have been developed. The most common approach for detecting functionally related gene sets from such high throughput data is clustering [1]. Traditional clustering methods like hierarchical clustering [2] and k-means [3], have several limitations. Firstly, they are based on the assumption that a cluster of genes behaves similarly in all samples. However, a cellular process may affect a subset of genes, only under certain conditions. Secondly, clustering assigns each gene or sample to a single cluster. However, some genes may not be active in any of the samples and some genes may participate in multiple processes.Biclustering is a two-way clustering method for detecting local patterns in data. It finds subsets of genes that behave similarly in subsets of samples. Biclustering was initially introduced by Hartigan [4]. However, it was first applied by Cheng and Church [5] on gene expression data. Cheng and Church tried to identify submatrices of low mean residue