BMC Genomics 2008, 9(Suppl 2):S20 http://www.biomedcentral.com/1471-2164/9/S2/S20 functional modules) within the expression data. Once this higher level class structure is modelled however, one may employ it to infer added functions for known genes or, more interestingly, assign functional labels to unclassified ORFs. The success of this latter objective clearly depends on the accuracy of the former class modelling approach. The utilization of the class model derived by bicluster analysis to aid functional annotation of unclassified ORFs has been under-explored. One possible method of assign- ing putative functions to unclassified ORFs is by examin- ing biclusters in which these ORFs are present. If these biclusters have a high enrichment of genes from one func- tional category we might surmise that these unannotated ORFs may also belong to this category. This guilt by associ- ation method for ORF classification is discussed in the Methods section. In this paper we extend bicluster analy- sis to shift the focus onto unclassified ORF annotation rather than performing it as a secondary objective to class analysis. Referred to as BALBOA (Bicluster AnaLysis Based Orf Annotation), this approach is a more systematic and directed method of predicting functional labels for unclassified ORFs using expression data. BALBOA's strength lies in the fact that it combines both the informa- tion on class structure, retrieved by bicluster analysis, and the available gene label information. In machine learning such approaches are often referred to as being 'semi-super- vised' in nature. BALBOA begins by partitioning the gene expression data- set into annotated genes and unannotated ORF subsets. Bicluster analysis is then performed on the annotated gene set alone. The resulting fully labelled biclusters are then assessed and used as 'classifiers' to label similarly expressed ORFs in the unannotated set. As BALBOA is based on bicluster analysis we briefly review this topic within this gene expression analysis domain in the Meth- ods section. We then describe the BALBOA ORF classifica- tion strategy. An advantage of the BALBOA approach is that it may be evaluated via cross validation. In the Results section we compare BALBOA to the standard classifica- tion approach of k-nearest neighbour (kNN). The specific multi-class kNN implementations used are also described in this section. In this evaluation we use three independ- ent gene expression datasets derived from Saccharomyces cerevisiae or budding yeast. In the second part of the Results section we then attempt to functionally classify yeast's unclassified ORFs using BALBOA. In the last part of the Results section we also attempt to model novel func- tional modules present within the unclassified ORF set. Importantly, an advantage of using three independently generated gene expression datasets is that they represent different 'views' of the same transcriptome. Therefore any putative predictions concerning the functions of unclassi- fied ORFs may be cross-referenced across datasets. This has the potential to significantly increase the support for both single annotations and predicted functional mod- ules. We also attempt to support our putative annotations via external experimental and protein sequence informa- tion from the Saccharomyces Genome Database (SGD). We first give a brief review of bicluster analysis in the gene expression analysis domain. Methods Bicluster analysis of gene expression data In the context of gene expression data, conventional clus- ter analysis involves computing similarity over all experi- mental samples, i.e. the full set of features. This approach may not be the most suitable for analyzing high dimen- sional gene expression datasets. Gene expression data may contain a significant amount of noise from sample varia- tion and errors within the experimental measurement process itself. Furthermore, even the expressions of func- tionally related genes may not necessarily correlate over the full set of experimental samples. For example, co-reg- ulation within a gene functional module may only be stimulated at certain stages in the cell cycle or environ- mental conditions. Cluster analysis, therefore, has the potential to miss significant subspace similarities within the data that may contribute to the modelling of the nat- ural set of functional classes. To address this problem, the concept of biclustering was introduced to gene expression data analysis by Cheng and Church [11]. In a gene expression data matrix of genes and samples, a bicluster is defined as a subset of genes that show similar expression over a subset of experimental samples. In examining different sample subsets one can also see that different behaviours of the same gene can be captured. This aspect of biclustering enables it to model overlapping gene functional classes i.e. where genes have more than one function. Cheng and Church proposed a bicluster scoring metric called the mean squared residue (H) to evaluate the correla- tion of the rows and columns within selected sub-matrices in the expression data matrix. This is given by: H(I, J) = 1 I J ∑ (aij − aIj − aiJ + aIJ )2 i∈I, j∈J (1) 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 mean of the whole sub-matrix. A sub-matrix with a mean squared residue score below a chosen thresh- old (δ) is termed a δ-bicluster. The number of sub-matri- ces, S, (possible δ-biclusters) in an M × N matrix is: SMN = (2N - 1)(2M - 1) (2) Page 3 of 15 (page number not for citation purposes)