A new GRASP-like algorithm for biclustering: a case-study on gene expression analysis

Biclustering or simultaneous clustering of both genes and conditions has generated considerable interest over the past few decades, due to the increasing need of efficiently analyzing high-dimensional gene expression data in several different and heterogenous contexts, such as for example in information retrieval, knowledge discovery, and data mining. In a gene expression data matrix, a bicluster is a submatrix of genes and conditions that exhibits a high correlation of expression activity across both rows and columns. Unfortunately, the problem of locating the most significant bicluster has been shown to be NP-complete. Therefore, given the inner intractability of the problem from a computational point of view, we have designed and implemented a GRASPlike heuristic algorithm to efficiently find good solutions in reasonable running times. Experimental results on Yeast gene expression dataset are promising indicating that the methods are able to find significant biclusters, especially from a biological point of view.