BMC Genomics 2008, 9(Suppl 2):S20 http://www.biomedcentral.com/1471-2164/9/S2/S20 The label assigned to an unclassified ORF by a bicluster classifier is also weighted based on the functional enrich- ment of the bicluster. Unclassified ORFs may receive labels from more than one bicluster classifier. Where assigned labels agree weights are additively combined. So for example, if unclassified ORF YAAxxx is classified by two annotated biclusters with functional enrichments 0.90 amd 0.75 for the Transcription functional category, YAAxxx is assigned the label Transcription with a weight of 1.65. In step 4 this weighted frequency, F, is used to rank unclassified ORFs within lists for each functional cate- gory. Unclassified ORFs that have many supporting biclusters with high functional enrichments for functional category A should top the weighted the list for category. In step 5, to reduce the potential for returning false positives, the best supported labels at the top of each list are then selected. We define a selection threshold, F ≥ βFmax, where Fmax is the highest weighted frequency in the list. Like the bicluster filtering parameter (a) the frequency threshold parameter, β, is user defined. In the extreme case, where α and β are set to 1.00, only unclassified ORFs labelled by the most enriched biclusters (Emax) for each functional cat- egory and labelled most frequently (Fmax) will be assigned labels. Since three yeast datasets are available in this study, a final cross-referencing step (step 6), where unclassified ORF labels are only assigned if they are consistent across mul- tiple expression datasets, may also be performed. As BALBOA involves separate 'training' and 'labelling' stages we may evaluate it via standard cross validation. Furthermore, although the set of unannotated ORFs are all officially designated as 'unclassified' by MIPS, for many there does exist some 'wet lab' experimental and/or pro- tein sequence information. Although, evidently, this information is not sufficient to allow an official func- tional annotation it may still support the putative func- tional labels assigned by BALBOA. Evaluation Datasets We use three yeast expression datasets in our evaluation. The 'Eisen' dataset contains 6,221 genes and 80 samples related to yeast cell-cycle, sporulation, and diauxic shift [1]. The 'Hughes' dataset contains 6,316 genes and 300 samples from an extensive functional analysis expression study [25]. The 'Gasch' dataset contains 6,129 genes and 150 samples from a yeast cell stress study [26]. Missing entries were randomly imputed from the inter-quartile range of each dataset. To reduce the impact of this impu- tation we removed all rows and columns containing extensive (≥ 25%) missing values. ORF profiles were annotated via the MIPS (Munich Infor- mation Centre for Protein Sequences) database [27]. Approximately 1500 ORFs in yeast are assigned category 99 (Unclassified). These MIPS labels were used to evaluate the functional enrichment after our bicluster generation phase, allowing selection of good bicluster 'classifiers'. Lastly, to avoid classification of non-coding ORFs those specified as 'dubious' (≈ 500) by the Saccharomyces Genome Database (SGD) were removed from each data- set. Datasets and algorithms are available on-line at http:/ /mlg.ucd.ie/balboa.html. Multi-class k-NN implementations Supervised approaches such as k-Nearest Neighbour (kNN) and Support Vector Machines (SVMs) have been used to classify unlabelled ORFs within expression data [6-8]. Recently, the 'local' kNN approach (that looks at the labels of the k most similar data object only) has been shown to out-perform the 'global' SVM approach (that searches for a class separating hyperplane) in the gene expression domain [23]. This is perhaps unsurprising as given the overlapping nature of gene functional classes a good class partition may be difficult to find. In kNN an unlabelled 'query' object is compared with its k nearest labelled objects in feature space. This 'nearness' depends on its feature values and is defined by a suitable similarity metric. In our context the query consists of an unannotated ORF and its feature values are its expression levels. We use Pearson's correlation as the similarity met- ric. We use k = 10, which was previously used in this domain [23], and is also the number of genes present in the initial bicluster seed in BALBOA. Also important in kNN is the voting process. Firstly, we use a majority voting scheme in which we assign the most prevalent label from our k nearest neighbours. We also implement a unanimous voting scheme in which we only assign a label to the query object if all k neighbours 'agree' or contain that label. This will reduce the recall but enable higher precision and reduce the potential for false posi- tives. To cater for the possibility of a gene having multiple functional labels, we must implement these kNN in a multi-class manner. Therefore when two (or more) labels are equally prevalent among the k nearest neighbours we assign all labels to our query. Results Comparative cross validation with kNN Before applying BALBOA to classify the unannotated yeast ORFs we must first determine its prediction accuracy, or precision, by cross validation. To do this we divide the annotated gene set into a training set and test set. We then train BALBOA on the training set and use the resultant Page 7 of 15 (page number not for citation purposes)