Biclustering is a technique used in analysis of microarray data. It aims at discovering subsets of genes that presents the same tendency under a subsest of experimental conditions. Various techniques have been introduced for discovering significant biclusters. One of the most popular heuristic was introduced by Cheng and Church [6]. In the same work, a measure, called mean squared residue, for estimating the quality of biclusters was proposed. Even if this heuristic is successful in finding interesting biclusters, it presents a number of drawbacks. In this paper we expose these drawbacks and propose some solutions in order to overcome them. Experiments show that the proposed solutions are effective in order to improve the heuristic. © 2008 IEEE.