BMC Genomics 2008, 9(Suppl 2):S20 http://www.biomedcentral.com/1471-2164/9/S2/S20 In such an exponential search space an exhaustive search through all possible sub-matrix solutions is NP-hard [16] and therefore impracticable in large gene expression data matrices. To tackle this issue Cheng and Church formulated the bicluster analysis problem as a 'greedy' search heuristic. The central iteration of this approach is a node deletion step that utilizes the means squared residue as the objective function. This seminal study spawned numerous directly related biclustering approaches [12,14,17] as well as con- ceptually similar strategies that incorporated alternative methods and metrics [18,19]. However, the mean squared residue was subsequently shown to contain some biases that directed searches towards less interesting biclusters containing genes with low expression variance [20], see Figure 1. Recently, we proposed BUBBLE (Bottom-Up Biclustering By Locality Expansion) bicluster analysis strategy [21]. BUBBLE demonstrated improved results over the competitive graph theoretic approach, SAMBA, proposed by Tanay et al. (2002) over several gene expres- sion datasets. BUBBLE begins by locating small, highly correlated regions within the gene expression data matrix via a simulated annealing based search method. These are referred to as bicluster seeds. Interestingly BUBBLE does not aim to find the global optimum only 'regional optima'. Furthermore, this method does not require selection on an arbitrary δ threshold. Importantly, BUBBLE utilizes a new metric, the Hv-score, which is unencumbered by the bias affecting the mean squared residue. This is defined by: ∑ Hv(I, J) = i∈I, j∈J (aij −aIj −aiJ +aIJ )2 ∑ i∈I, j∈J (aij −aiJ )2 (3) where aij is the entry at position ij in the sub-matrix (I, J), aiJ is the mean of the ith row, aIj is the mean of the jth col- umn and aIJ is the mean of the sub-matrix. The Hv-score includes the row variance of the bicluster in the denomi- nator which compensates for the bias inherent in the mean squared residue (equation 1). In BUBBLE, once the bicluster seeds have been located they are then expanded in a deterministic manner by add- ing the most similar gene profiles to produce a full biclus- FCihgaunrgee 1in H-score and Hv-score with increasing bicluster scale Change in H-score and Hv-score with increasing bicluster scale. Figure 1 illustrates how the H-score and improved Hv-score change as the scale of the bicluster being measured changes. Biclusters of different scales, but with the same relative row correlation, receive very different H-scores but approximately the same Hv-score. Biclusters were generated as in [28]. Page 4 of 15 (page number not for citation purposes)