BMC Genomics 2008, 9(Suppl 2):S20 http://www.biomedcentral.com/1471-2164/9/S2/S20 ter. The 'stopping' criterion for this expansion is based on the largest disimprovement in the Hv-Score of the growing bicluster. BALBOA's bicluster analysis step is based upon the BUB- BLE algorithm with some important extensions, discussed in the next section, designed to improve the subsequent ORF functional classification process. In the next section we shall examine the 'co-occurrence' method of ORF func- tional classification that has been thus far employed with both cluster and bicluster analysis of gene expression data. Unclassified ORF annotation via unsupervised class modelling ORF annotation by co-occurrence analysis: 'guilt by association' It is evident from previous cluster and bicluster analysis studies of gene expression data that functionally related genes tend to group together [1,22]. Extending this logic would suggest that similar functions be attributed to any unclassified ORFs also present. The support for this func- tional inference increases with the ratio of annotated to unclassified ORFs within the grouping and the functional enrichment of the annotated genes present. This co-occur- rence analysis has also been referred to as the guilt by asso- ciation approach [23]. Wu et al. applied several gene clustering techniques to expression data [15]. Using the above premise, they inferred putative functions for unannotated ORFs and labelled the clusters using the MIPS functional database (see Results section). To assess the precision of this strat- egy they iteratively re-labelled each annotated gene in turn as 'unclassified' and re-assessed all the cluster enrichments (and resultant ORF classifications). They achieved an accuracy of up to 80% with a recall of 40% in the case of the Protein Synthesis functional category. Although Wu et al. did some filtering on the basis of p-values they did not take into account the functional enrichment of the clus- ters, only whether the gene was present or not. Also, a sig- nificant number of the clusters contained many unannotated genes and therefore added limited informa- tion to the model. Lastly, as this annotation approach is built upon conventional clustering only, it does not uti- lize input from the gene relationships that only occur over significant subsets of experimental samples. In another study, biclusters generated by the SAMBA biclustering algorithm were subsequently analyzed to pro- duce a so called 'naive functional annotations' of unclas- sified ORFs [19]. Again p-value filtering was carried out but in this case the evaluation involved hiding 30% of the known annotations and then assessing the precision. Here the authors used the 10 Gene Ontology (GO) categories (rather than the more specific 17 MIPS categories). It was also noted that genes could be assigned more than one annotation as a result of this process. However, as p-values were used to select significant biclusters (p > 10-4) and no weight was given to functional enrichment of the biclus- ters, we can see that many annotations, some poorly sup- ported, may be assigned to an ORF. It is also difficult to gauge the success of this approach as the authors only pro- vide the specificity (percentage of true negatives correct) and the selectivity (recall) of their annotations. Both of the above classification approaches use a 'co-occurrence' strat- egy to putatively label unannotated ORFs. An alternative strategy might be to borrow from the 'labelled training set' approach used in supervised learning. The BALBOA strategy for unclassified ORF annotation In the BALBOA strategy for annotation of unclassified ORFs the gene expression dataset is first partitioned into labelled and unlabelled subsets, i.e. annotated genes and unannotated ORFs respectively. Gene labels are provided by the MIPS database, see Results section. Bicluster analy- sis is then applied to model the classes in the annotated subset. This produces fully labelled biclusters that can be used as 'classifiers' to direct labelling of the unclassified ORFs in the unannotated subset. This type of approach, in which both knowledge of labels and object similarities are combined to drive classification, may be referred to as 'semi-supervised' as the classification is partially directed by the labels that are available. This approach has several advantages over the 'co-occurrence' ORF annotation method described in the last section. Firstly, the biclusters are fully labelled, containing no unclassified ORFs, and therefore all will be more informative. The biclusters gen- erated in this manner also tend to have higher functional enrichments than those generated over the total expres- sion dataset. Furthermore, during evaluation the dataset may be partitioned into 'training' and 'testing' subsets enabling cross validation in accordance with standard practice (where training and testing sets remain separated) to be applied. In BALBOA, the bicluster analysis step employs several extensions to the previous BUBBLE approach. Firstly, the diversity within the final bicluster population is increased by masking bicluster seeds as they are discovered. This masking involves replacing the entries of the dataset that represent the bicluster seed with random values from the inter-quartile range of the dataset. Selection from this range plus the fact that masking is limited to the bicluster seed minimizes the random interference referred to in [12]. Secondly, the number of bicluster solutions generated by BALBOA is also increased. As in ensemble clustering it is advantageous to increase the size and diversity of the set of biclusters as this will enable better determination of the most 'stable' relationships [24]. In this case however this stability adds increased support to our subsequent ORF classification step. Page 5 of 15 (page number not for citation purposes)