Parallel Biclustering of Genes with Coherent Evolutions: Algorithm and Biological Significance of the Biclusters

Uncovering genetic pathways is equivalent to finding clusters of genes with expression levels that evolve coherently under subsets of conditions. This can be done by applying a biclustering procedure to gene expression data. Given a microarray data set with M genes and N conditions, we define a bicluster with coherent evolution as a subset of genes with expression levels that are non-decreasing as a function of a particular ordered subset of conditions. We propose a new biclustering procedure that identifies all biclusters with a specified number of K conditions in parallel with O(MK) complexity. Unlike almost all prior biclustering techniques, the proposed approach is guaranteed to find all biclusters with a specified minimum numbers of genes and conditions in the data set. All of the biclusters it identifies have no imperfection, i.e., the evolutions of the genes in each bicluster will be coherent across all conditions in the bicluster. Furthermore, the complexity of the proposed approach is lower than that of prior approaches. We also discuss the biological significance of the biclusters computed by the algorithm for a set of yeast gene microarray data