BACKGROUND
gene microarrays are a popular technology for assisting with the prediction and understanding of diseases  <cit> .
cancer is one such disease where this technology has proved to be particularly powerful.
an important challenge in this area is the discovery of gene sets which can be used as predictors of cancer.
for a gene set to be useful as the basis of developing a clinical predictor for cancer, there are a number of desirable properties it should have:
• compactness: there should not be too many genes in the set.
this reduces the cost involved in developing a clinical diagnostic test using these genes.
• accuracy: when the genes are input to a machine learning algorithm as features, it should be possible to achieve a high true positive rate and a low false positive rate.
• classifier independence: it should be possible to achieve high accuracy using a range of different machine learning classifiers with the gene set.
this increases the confidence that biologists have in the stability and generality of the gene set.
• biological relevance: most of the genes in the gene set should have a known relationship to cancer, based on the literature.
• biological coverage: the genes in the gene set should span a number of distinct biological processes and each gene should be independently useful for prediction.
the set of genes should not be confined to a single pathway.
this increases the robustness of prediction and allows more uniform classification power across different subtypes of cancer.
in this paper, we propose a new classifier voting approach to discover a gene set for breast cancer prognosis that satisfies these five properties.
we are able to discover a gene set using the van 't veer et al.
<cit>  dataset that consists of  <dig> genes and delivers highly accurate prediction results for a range of classifiers.
in addition, we were able to discover a  <dig> gene set that delivers high accuracy on the ma et al.
<cit>  dataset, for which we also validated our performance on an additional independent dataset exhibiting the same biological conditions  <cit> .
the majority of these genes have been previously mentioned in the cancer literature, and we have found the genes in these sets to be relatively independent in terms of function, meaning our genes are able to cover a number of different processes involved in cancer.
in comparison with other studies on these datasets, our gene sets are considerably smaller and deliver considerably higher performance across a range of machine learning classifiers.
our proposed technique is based on the use of multiple voting classifiers to identify the final gene set.
its use of multiple classifiers makes it different from previous work for microarray classification, such as wrapper based methods, which only target a single classifier.
an important aspect of our method is that it does not employ any biological domain knowledge  as part of the algorithm for identifying the gene set.
this makes it particularly applicable for deployment in scenarios where the literature is sparse or the state-of-the-art is immature.
nevertheless, for the dataset we use, we are able to confirm that the individual genes in the sets that are discovered are biologically relevant.
methods
our proposed approach comprises two steps.
in the first step, we rank all genes of the training set.
in the second step, we investigate the classification performance of combinations of genes using a voting approach from the ranked genes obtained from the first step, but employing a number of classifiers instead of just one classifier.
the steps are described in detail in the subsequent sections.
the receiver operating characteristic  curve: preliminaries
in machine learning, the receiver operating characteristic  curve is used to evaluate the discriminative performance of binary classifiers.
this is obtained by plotting the curve of the true positive rate  versus the false positive rate  for a binary classifier by varying the discrimination threshold.
all the calculations of true positive rate and false positive rate are attained when using a particular classifier threshold.
by varying the threshold, a set of values for these measurements is obtained.
this set of values is plotted in a two-dimensional cartesian graph to yield the roc curve.
the roc curve takes into account all the possible solutions by varying the discriminative threshold.
the best performance would be produced, if the roc curve matches with the upper left corner of the roc space .
the closer the roc curve is to the upper part of the roc space, the better the performance of the classifier.
an roc curve is a two dimensional illustration of classifier performance.
reducing roc performance to a single scalar value to represent expected performance helps compare classifiers.
a popular method is to calculate the area under the roc curve   <cit> .
the auc, being a part of the area of the unit square, has a value between  <dig> and  <dig>  since random guessing could produce the diagonal line between  and  with an area of  <dig> , a classifier with an auc less than  <dig>  is undesirable  <cit> .
an auc value close to  <dig> indicates better performance for a binary classifier  <cit> .
feature ranking using roc
we rank all genes of the training set using the first step of mamitsuka  <cit> 's roc, which is the equivalent of the mann-whitney u statistic  <cit> , normalized by the number of possible pairings of positive and negative values, also known as the two sample wilcoxon rank sum statistic  <cit> .
the auc actually represents the probability that a randomly chosen positive example is correctly rated  with greater suspicion than a randomly chosen negative example.
let us consider a training dataset d of n examples, where each example comprises m attributes: x <dig>  x <dig>  x <dig> ..., xm.
each of the m attributes has a differing discriminative power reflected by its respective auc.
to calculate the discriminative power that is expressed in terms of auc, we plot the roc curve for each gene paired with the class label,  and calculate the auc of the roc curve.
now, we order the genes based on their respective aucs.
multi-classifier voting approach to select genes
we attempt to classify the validation dataset with the top ranked genes.
at first we pass the top  <dig> genes individually to all classifiers, and note the classification accuracy of each classifier on a validation set.
for the second pass, we select the gene for which the most classifiers achieve their highest accuracy.
then we form a pair of the selected gene from the first pass, along with the remaining nine genes, and input these nine pairs to the selected classifiers.
we then note the classification accuracy.
the pair on which the most classifiers achieve their highest accuracy is selected and given to a third pass.
we continue adding single genes to form 3-gene combinations, and so on.
a diverse set of fifteen classifiers was used for this process.
they are: logistic model tree   <cit> , naïve bayes tree   <cit> , naïve bayes, random forest, c <dig> , k-nearest neighbour , artificial neural network , logistic regression, support vector machine , and bagging  <cit>  and boosting   <cit>  for naïve bayes, random forest and c <dig> .
we stop growing the gene set once more than 50% of the classifiers have their accuracy lowered on the validation set by the addition of an individual gene.
in the case of any tie between two or more genes, we note the total accuracy  for the tied genes and the gene with the largest total accuracy is chosen for the next pass.
this majority voting approach allows us to select a small subset of genes that can boost classification accuracy on a number of classifiers.
one can then tune the performance of an individual classifier by choosing the prefix of the genes  that delivers best accuracy.
for example, for c <dig>  with boosting on the van 't veer data, adding the 5th gene to the first four genes actually degrades the performance of that specific classifier.
so for that individual classifier, rather than using our final selection of  <dig> genes, we can instead use only a subset of  <dig>  genes.
datasets
in each of the three datasets used in our analysis, the prognostic outcome to be predicted is whether distant metastases will occur within  <dig> years  or whether the patient is disease-free after  <dig> years .
van't veer data  <cit> : the dataset comprises  <dig> breast cancer patients treated through modified radical mastectomy or breast-conserving treatment followed by radiotherapy.
the patients were split into a training set of  <dig>  a validation set of  <dig>  and a test set of  <dig> cases.
the training set consists of  <dig> positive  and  <dig> negative  cases, the validation set comprises five positive and five negative cases, and the test set was made up of  <dig> positive and  <dig> negative cases.
further, we created a merged dataset from van 't veer's  <cit>  training  and test sets to apply k-fold cross validation .
in k-fold cv,  <dig> cases out of the training set are randomly selected for the validation set before applying the froc.
ma et al.
data  <cit> : this dataset contains  <dig> breast cancer patients treated through standard breast surgery followed by continued adjuvent tamoxifen therapy.
there were  <dig> positive cases  and  <dig> negative cases .
we separate the first  <dig> positive cases and the last  <dig> negative cases to form the test set and use the remaining cases for training.
loi et al.
data  <cit> : the dataset is made up of  <dig> breast cancer patients obtained from the guyt <dig> test data used in the loi et al.
study, with similar treatments to those performed in the ma et al.
dataset.
there were  <dig> positive cases  and  <dig> negative cases .
this dataset was included in our study as a completely independent test dataset.
all patients were considered as test cases to gauge performance of the classifiers trained on the ma et al.
dataset.
evaluation
for the van 't veer  <cit>  and ma et al.
<cit>  datasets, we used a holdout cross validation procedure, where a training set is used to train the classifiers and a separate test set is used to evaluate.
we have also used the more general k-fold cross validation  scheme to evaluate the performance on van 't veer data.
in k-fold cv, the original sample is partitioned into k subsamples.
of the k subsamples, a single subsample is retained as the validation data for testing the model, and the remaining k -  <dig> subsamples are used as training data.
the cv process is then repeated k times , with each of the k subsamples used exactly once as the validation data.
the k results from the folds, then, can be averaged  to produce a single estimation.
here, we have chosen k to be  <dig>  the results for k-fold cv is presented in the additional file  <dig>
all of our evaluation results are reported in weighted accuracy  <cit> , which is calculated by the formula shown in eq.
.
weighted accuracy=tpp+tnn <dig>
where, p = total number of positive cases,
n = total number of negative cases.
RESULTS
using the van 't veer data  <cit> , our final selected gene set consists of the  <dig> genes  and as we shall show, this compact gene set delivers highly accurate performance across a range of classifiers.
the functions of these genes are summarised in table  <dig>  additionally, we used the ma et al.
<cit>  data to test whether our method was successful on a dataset with different biology to the van 't veer dataset.
we have obtained a different set of  <dig> genes .
we also tested the generalisability of this  <dig> gene set on an additional independent dataset exhibiting the same biological conditions  <cit> .
most of the later discussion will be using the van 't veer data as an example, unless otherwise stated.
biological significance of the compact gene sets
as the treatment procedures applied to the patients in both the van 't veer study  <cit>   and ma et al.
study  <cit>   are vastly different, it is not surprising that there is no overlap between the two gene sets identified as the best predictors of prognosis outcome.
the biology driving the chance to distant metastasis in each dataset is likely to be significantly different and as such it would not make sense to expect the gene lists to overlap.
therefore, we will consider each gene set independently.
gene ontology  and kyoto encyclopedia of genes and genomes  pathway analysis of the two gene sets show that each of the genes are diverse in function and appear to be unrelated in terms of the biological processes in which they are involved.
what is interesting, however, is that the majority of the genes have been previously shown to be related to cancer in the literature .
this suggests that our feature selection procedure yields a compact sampling of the diverse biological processes represented by the microarray, which are highly representative of the prognostic potential of the patient.
in concordance with this, in the  <dig> gene set, tspyl <dig> and ca <dig> have been previously used as prognostic biomarkers in cancer  <cit> .
furthermore, four of the top  <dig> genes selected by our method are in the set of  <dig> genes used in the study by van 't veer  <cit> .
and the most important individual gene in improving a number of the classifier performances in the test set  is present in the  <dig> genes selected by alexe et al.
<cit> .
in the  <dig> gene set, cd <dig> has been used previously as a prognostic biomarker in gastric cancer  <cit> .
links between identified genes and the cancer literature
<dig> gene set
each of the  <dig> genes can be directly linked to potential cancer re-occurrence through their respective biological functions.
tspyl <dig> is involved in nucleosome assembly, a process which, if destabilised, can alter the regulatory mechanisms of a cell  <cit> , which is likely to occur in cancer.
nmu has been shown to be related to metastatic potential and cancer cachexia  <cit> , which would have a significant impact on the potential of reoccurrence of the cancer.
ca <dig> is involved in nitrogen metabolism and is linked to cell proliferation and aspm is involved in mitotic spindle regulation and is expressed in proliferating tissues.
.
lin <dig> is involved in progression through the cell cycle  <cit>  and is a tumor suppressor  <cit>  that inhibits dna synthesis, thus having significant cancerous potential.
regulation of the diaph <dig> gene  <cit>  is important in regulating the transcription factor mitf, which in turn regulates the invasiveness of melanoma.
finally, while no significant link to cancer processes were found for agtpbp <dig>  somatic mutations in the coding sequence have been found in colorectal cancers  <cit> .
<dig> gene set
<dig> out of the  <dig> genes in this set not only have links to cancer through the literature, they have in most cases been shown to be directly linked to prognostic outcome.
a study into antibodies against zic <dig> in small lung cell carcinoma showed that the concentration of antibodies is a good indicator of prognosis  <cit> .
srda <dig> overexpression in hormone-refractory prostate cancers was shown to be crucial for cell viability  <cit>  and is a likely factor in resistance to hormone based therapies in prostate cancers.
ppar has been shown previously to be abberently expressed in colon cancer cells  <cit>  and is an important player in the proliferation and growth of these cells  <cit> .
a protein involved in innate immune response which is critical to the regulation of the complement cascade, cd <dig>  has been shown to be important in prostate growth  <cit> , gastric tumor invasiveness  <cit>  and breast cancer prognosis  <cit> .
finally, rgs <dig> has been implicated in the control of autophagy in colon cancer cell lines  <cit> .
the demonstrated links of these genes with the literature highlights the relevancy of each of the genes with respect to cancer and demonstrates their potential to represent biological processes which are directly related to the prognostic potential  of a patient.
classification performance on test set
<dig> gene set
the best performance for the test dataset obtained was  <dig> % for c <dig>  with boosting.
this performance was achieved using only three genes: tspyl <dig>  diaph <dig>  and agtpbp <dig>  it is worth noting that the gene subset {tspyl <dig>  diaph1} was found to be significant for at least six of the considered  <dig> classifiers .
it was also found that the gene tspyl <dig> is the most influential and has been chosen by all the considered classifiers.
the performance of ann and svm was found to be better for the gene subsets {tspyl <dig>  ca9}, and {tspyl <dig>  lin9}, respectively.
the gene lin <dig> was found to be important only when using svm.
similarly, the gene ca <dig> was found to be suitable for the ann and logistic regression along with other genes.
an analysis of the experimental results reveals that similar types of classifiers tended to choose the same subset of genes  to obtain the best performance.
for instance, random forest, random forest with bagging and random forest with boosting, are essentially similar classifiers with some small variation.
all these classifiers chose the gene subset {tspyl <dig>  diaph <dig>  aspm} for classifying the dataset.
however, random forest with bagging produced the best accuracy of the three different types of random forest considered in this study, adding the gene nmu to the common gene subset {tspyl <dig>  diaph <dig>  aspm}.
thus, a subset of genes used by all classifiers is selected as the important gene subset.
table  <dig> summarises the classification accuracy for both the individual test set of van 't veer  <cit>  and for  <dig> fold cross validation , comparing the use of subsets of the  <dig> genes, versus the scenario where all  <dig>  genes are used.
*our experiments were carried out on a standard intel core  <dig> duo cpu  <dig>  ghz desktop computer running  <dig> gb of ram.
<dig> gene set
discussion
in our multi-classifier voting approach, one selects a subset of genes using an roc based ranking.
this is then followed by a classifier voting phase, to refine this list of genes even further.
our improved performance is achieved due to two factors.
first, roc is a classifier independent method that is not dependent on the standard deviation of the features.
second, the multi-classifier voting gene selection approach produces the best possible combination of genes satisfied by a majority of the classifiers.
these two benefits contribute to obtaining a better classification performance for the complete set of unseen datasets.
furthermore, the significant reduction of genes we obtain is another advantage of our approach.
previous studies that link gene expression profiles to clinical outcomes in breast cancer cases have demonstrated that the potential for distant metastasis and overall survival probability may be attributable to the biological characteristics of the primary tumor at the time of diagnosis  <cit> .
in particular, a 70-gene expression signature by van 't veer  <cit>  has proven to be a strong prognostic factor, outperforming all known clinicopathological parameters.
the accuracy in distinguishing cases of poor and good breast cancer prognosis, provided by the subset of  <dig> genes selected by van 't veer  <cit> , was revalidated and confirmed by van de vijver  <cit>  in a different cohort of patients.
however,  <dig> genes is not a compact set, greatly increasing the expense of developing a clinical predictor.
even the set of  <dig> genes by alexe et al.
<cit>  is twice as large as our  <dig> gene set.
our method yielded better accuracy with  <dig> genes, and that, too, was independent of a specific classifier.
having a compact set of genes is extremely important from a treatment and drug development viewpoint, where clinical and experimental validation is costly and it is vital to restrict the number of hypotheses or targets  to be followed up.
we also show, in the comparison of our  <dig> gene set with the  <dig> gene set of ma et al.
<cit>  in table  <dig> using the loi et al.
<cit>  data, that our approach avoids generating an overly compact geneset that may not generalise well to microarray data from another lab.
this is extremely important when attempting to develop a robust predictor in a clinical setting.
we have also compared our best results for the van 't veer  <cit>  dataset against some well known cancer treatment guidelines .
it clearly shows that machine learning approaches are effective technique in classifying breast cancer prognosis.
*results obtained from gevaert et al.
<cit> , where results were provided as number of true positives and true negatives.
comparison with other studies
a number of efforts have been made in this direction for breast cancer prognosis but without major success.
ritz  <cit>  combined both genetic and clinical information in a neural network for breast cancer prognosis, but found that the combination did not improve the performance.
dettling et al.
<cit>  applied penalized logistic regression analysis to predict cancer prognosis for the van 't veer  <cit>  dataset.
they found that none of the clinical variables entered the model and concluded that the clinical data did not contain any useful independent information for prediction, given the gene expression profile.
to prognosticate on the breast cancer dataset, alexe et al.
<cit>  applied the logical analysis of data  tool to analyze microarray data.
they identified  <dig> genes out of  <dig>  possible genes that could distinguish patients with poor or good prognoses.
amongst the  <dig> genes the lad tool identified three and five genes that were associated with poor and good prognoses, respectively.
two wholly new classes  of patients were discovered.
it was also demonstrated that the training and test sets of van 't veer  <cit>  differ in their characteristics.
however, this study of alexe et al.
was overly specific to the chosen classifier , as we shall shortly see.
we assessed the classification performance of five different subsets of genes on the van 't veer  <cit>  dataset.
the  <dig> and  <dig> genes selected by van 't veer  <cit> , the set of  <dig> genes selected by the lad technique  <cit> , a set of  <dig> genes selected by roc  with markov blanket  <cit>  and the set of  <dig> genes selected by our voting approach.
for roc  with markov blanket we have used the same parameter for the number of genes to select as given in that paper, namely  <dig> genes and then using an area between two roc curves  value >  <dig> for the second step, chosen to yield the most competitive performance for the technique.
we applied five classification methods used by alexe et al.
<cit>  and our top performing classifier c <dig>  with boosting on the gene set of size  <dig>  these classification methods include ann, svm, logistic regression, k-nn, c <dig>  decision tree and c <dig>  with boosting .
following this, predictive models were constructed for the training set and were tested using the supplied test set of  <dig> samples.
*results adopted from alexe et al.
<cit> .
it is clear that the weighted accuracy in distinguishing patients with good and poor breast cancer prognoses is the highest across all classifiers using the  <dig> genes selected by our voting approach and is much higher than the models using  <dig> ,  <dig> and  <dig> genes.
our approach produced much better performance for most classifiers, except for ann, where using the  <dig> selected genes of alexe et al.
<cit>  or by using roc with markov blanket  <cit>  was better.
however, the methodology of alexe et al.
incorporated a "selection bias"  <cit>  for finding their subset of  <dig> genes, since the test set was used.
in contrast, our voting approach did not have access to the test set for gene selection.
when selecting genes using our voting approach, we used only the training dataset, keeping the test set completely unknown.
the performance of the classifiers using the selected  <dig> and  <dig> genes by van 't veer  <cit>  was found to be insignificant compared with that of our approach.
furthermore,  <dig> or  <dig> is not a compact set of genes and our voting method can obtain a better accuracy using at most four genes .
gevaert et al.
<cit>  proposed a bayesian networ k-based strategy to treat clinical and microarray data along the same lines as above using the same dataset.
a probabilistic model was used because it integrates the data sources in several ways, and explores and documents the model structure and parameters.
the concept of a markov blanket is used to identify all the variables that shield the class variable from being affected by the rest of the network.
however, all the processes are integrated in the classifier, and hence the performance of the system is biased towards the choice of a classifier.
furthermore, the performance of the classifier would depend on the selection of the initial distribution for the model.
comparison with other filter approaches
jeffery et al.
<cit>  have demonstrated that the roc is an accurate way to identify differentially regulated genes in a microarray dataset and that it can produce robust classifiers applying  <dig> feature selection techniques on  <dig> gene expression datasets.
when dealing with datasets that have  <dig> or more samples, the roc was shown to be the most accurate.
other filter approaches like t-test and principle component analysis  produce reasonable results, but roc yields better results  on the van 't veer  <cit>  dataset.
it is particularly useful for gene expression data, as it is not directly dependent on the standard deviation of the expression of each gene like the t-test is, or only on the correlation of each genes like the pca is.
moreover, unlike pca, roc is not sensitive to the scaling of the data.
gene set significance tests
it is interesting to consider the results of gene set enrichment analysis   <cit>  on our set of  <dig> genes obtained by voting, against the other gene sets proposed by van 't veer et al.
<cit>  , alexe et al.
<cit>  , and the one we have obtained using mamitsuka's  <cit>  technique .
three out of the five gene sets are enriched in phenotype  <dig> .
of which, mamitsuka's and our gene sets have an fdr q-value equal to  <dig> and  <dig> , with an enrichment score  of  <dig>  and  <dig> , respectively.
members of the leading edge subset  also indicate that our gene set contains only those genes contributing to the enrichment score, compared to the other gene sets that contain only a fraction of genes contributing to the enrichment score .
CONCLUSIONS
we have proposed and implemented a multi-classifier voting approach for gene selection, to effectively classify the prognosis of breast cancer patients using data from two distinct treatment cases.
the novelty of our approach is that it can identify a very small number of genes that are predictive across a large range of classifiers.
we applied our voting approach to three well-known microarray datasets, related to breast cancer.
experimental analysis demonstrated high prediction accuracies for the gene sets discovered, compared to previous studies.
the gene sets discovered were also biologically relevant and had good biological process coverage.
list of abbreviations used
roc: receiver operating characteristic; auc: area under the roc curve; lmt: logistic model tree; k-nn: k-nearest neighbour; ann: artificial neural network; svm: support vector machine; nbtree: naïve bayes tree; cv: cross validation; pca: principle component analysis; gsea: gene set enrichment analysis; es: enrichment score; go: gene ontology; kegg: kyoto encyclopedia of genes and genomes
competing interests
the authors declare that they have no competing interests.
authors' contributions
mrh, mmh and kr conceived the design of the roc ranking and voting algorithm.
jb and gm contributed to the experimental design, and the experiments were performed by mmh and mrh.
the biological significance was investigated by gm and jwkh and the writing was performed with input from all authors.
supplementary material
additional file 1
this file contains the rank gene list used in each fold of 5-fold cv, and performance of each fold using the selected genes for different classifier.
click here for file
additional file 2
this file contains the result of gene set enrichment analysis .
click here for file
acknowledgements
this work is partially supported by national ict australia.
national ict australia is funded by the australian government's backing australia's ability initiative in part through the australian research council.
mmh is supported by a melbourne research scholarship.
jwkh and gm are supported by an australian postgraduate award and a nicta research project award.
this article has been published as part of bmc bioinformatics volume  <dig> supplement  <dig>  2009: proceedings of the seventh asia pacific bioinformatics conference   <dig>  the full contents of the supplement are available online at

 gene microarrays are a popular technology for assisting with the prediction and understanding of diseases. cancer is one such disease where this technology has proved to be particularly powerful. an important challenge in this area is the discovery of gene sets which can be used as predictors of cancer. for a gene set to be useful as the basis of developing a clinical predictor for cancer, there are a number of desirable properties it should have: • compactness: there should not be too many genes in the set. this reduces the cost involved in developing a clinical diagnostic test using these genes. • accuracy: when the genes are input to a machine learning algorithm as features, it should be possible to achieve a high true positive rate and a low false positive rate. • classifier independence: it should be possible to achieve high accuracy using a range of different machine learning classifiers with the gene set. this increases the confidence that biologists have in the stability and generality of the gene set. • biological relevance: most of the genes in the gene set should have a known relationship to cancer, based on the literature. • biological coverage: the genes in the gene set should span a number of distinct biological processes and each gene should be independently useful for prediction. the set of genes should not be confined to a single pathway. this increases the robustness of prediction and allows more uniform classification power across different subtypes of cancer. in this paper, we propose a new classifier voting approach to discover a gene set for breast cancer prognosis that satisfies these five properties. we are able to discover a gene set using the van't veer et al. dataset that consists of genes and delivers highly accurate prediction results for a range of classifiers. in addition, we were able to discover a gene set that delivers high accuracy on the ma et al. dataset, for which we also validated our performance on an additional independent dataset exhibiting the same biological conditions. the majority of these genes have been previously mentioned in the cancer literature, and we have found the genes in these sets to be relatively independent in terms of function, meaning our genes are able to cover a number of different processes involved in cancer. in comparison with other studies on these datasets, our gene sets are considerably smaller and deliver considerably higher performance across a range of machine learning classifiers. our proposed technique is based on the use of multiple voting classifiers to identify the final gene set. its use of multiple classifiers makes it different from previous work for microarray classification, such as wrapper based methods, which only target a single classifier. an important aspect of our method is that it does not employ any biological domain knowledge as part of the algorithm for identifying the gene set. this makes it particularly applicable for deployment in scenarios where the literature is sparse or the state-of-the-art is immature. nevertheless, for the dataset we use, we are able to confirm that the individual genes in the sets that are discovered are biologically relevant. methods our proposed approach comprises two steps. in the first step, we rank all genes of the training set. in the second step, we investigate the classification performance of combinations of genes using a voting approach from the ranked genes obtained from the first step, but employing a number of classifiers instead of just one classifier. the steps are described in detail in the subsequent sections. the receiver operating characteristic curve: preliminaries in machine learning, the receiver operating characteristic curve is used to evaluate the discriminative performance of binary classifiers. this is obtained by plotting the curve of the true positive rate versus the false positive rate for a binary classifier by varying the discrimination threshold. all the calculations of true positive rate and false positive rate are attained when using a particular classifier threshold. by varying the threshold, a set of values for these measurements is obtained. this set of values is plotted in a two-dimensional cartesian graph to yield the roc curve. the roc curve takes into account all the possible solutions by varying the discriminative threshold. the best performance would be produced, if the roc curve matches with the upper left corner of the roc space. the closer the roc curve is to the upper part of the roc space, the better the performance of the classifier. an roc curve is a two dimensional illustration of classifier performance. reducing roc performance to a single scalar value to represent expected performance helps compare classifiers. a popular method is to calculate the area under the roc curve. the auc, being a part of the area of the unit square, has a value between and since random guessing could produce the diagonal line between and with an area of, a classifier with an auc less than is undesirable. an auc value close to indicates better performance for a binary classifier. feature ranking using roc we rank all genes of the training set using the first step of mamitsuka's roc, which is the equivalent of the mann-whitney u statistic, normalized by the number of possible pairings of positive and negative values, also known as the two sample wilcoxon rank sum statistic. the auc actually represents the probability that a randomly chosen positive example is correctly rated with greater suspicion than a randomly chosen negative example. let us consider a training dataset d of n examples, where each example comprises m attributes: x x x..., xm. each of the m attributes has a differing discriminative power reflected by its respective auc. to calculate the discriminative power that is expressed in terms of auc, we plot the roc curve for each gene paired with the class label, and calculate the auc of the roc curve. now, we order the genes based on their respective aucs. multi-classifier voting approach to select genes we attempt to classify the validation dataset with the top ranked genes. at first we pass the top genes individually to all classifiers, and note the classification accuracy of each classifier on a validation set. for the second pass, we select the gene for which the most classifiers achieve their highest accuracy. then we form a pair of the selected gene from the first pass, along with the remaining nine genes, and input these nine pairs to the selected classifiers. we then note the classification accuracy. the pair on which the most classifiers achieve their highest accuracy is selected and given to a third pass. we continue adding single genes to form 3-gene combinations, and so on. a diverse set of fifteen classifiers was used for this process. they are: logistic model tree, naïve bayes tree, naïve bayes, random forest, c, k-nearest neighbour, artificial neural network, logistic regression, support vector machine, and bagging and boosting for naïve bayes, random forest and c. we stop growing the gene set once more than 50% of the classifiers have their accuracy lowered on the validation set by the addition of an individual gene. in the case of any tie between two or more genes, we note the total accuracy for the tied genes and the gene with the largest total accuracy is chosen for the next pass. this majority voting approach allows us to select a small subset of genes that can boost classification accuracy on a number of classifiers. one can then tune the performance of an individual classifier by choosing the prefix of the genes that delivers best accuracy. for example, for c with boosting on the van't veer data, adding the 5th gene to the first four genes actually degrades the performance of that specific classifier. so for that individual classifier, rather than using our final selection of genes, we can instead use only a subset of genes. datasets in each of the three datasets used in our analysis, the prognostic outcome to be predicted is whether distant metastases will occur within years or whether the patient is disease-free after years. van't veer data: the dataset comprises breast cancer patients treated through modified radical mastectomy or breast-conserving treatment followed by radiotherapy. the patients were split into a training set of a validation set of and a test set of cases. the training set consists of positive and negative cases, the validation set comprises five positive and five negative cases, and the test set was made up of positive and negative cases. further, we created a merged dataset from van't veer's training and test sets to apply k-fold cross validation. in k-fold cv, cases out of the training set are randomly selected for the validation set before applying the froc. ma et al. data: this dataset contains breast cancer patients treated through standard breast surgery followed by continued adjuvent tamoxifen therapy. there were positive cases and negative cases. we separate the first positive cases and the last negative cases to form the test set and use the remaining cases for training. loi et al. data: the dataset is made up of breast cancer patients obtained from the guyt test data used in the loi et al. study, with similar treatments to those performed in the ma et al. dataset. there were positive cases and negative cases. this dataset was included in our study as a completely independent test dataset. all patients were considered as test cases to gauge performance of the classifiers trained on the ma et al. dataset. evaluation for the van't veer and ma et al. datasets, we used a holdout cross validation procedure, where a training set is used to train the classifiers and a separate test set is used to evaluate. we have also used the more general k-fold cross validation scheme to evaluate the performance on van't veer data. in k-fold cv, the original sample is partitioned into k subsamples. of the k subsamples, a single subsample is retained as the validation data for testing the model, and the remaining k - subsamples are used as training data. the cv process is then repeated k times, with each of the k subsamples used exactly once as the validation data. the k results from the folds, then, can be averaged to produce a single estimation. here, we have chosen k to be the results for k-fold cv is presented in the additional file all of our evaluation results are reported in weighted accuracy, which is calculated by the formula shown in eq.. weighted accuracy=tpp+tnn where, p = total number of positive cases, n = total number of negative cases.  using the van't veer data, our final selected gene set consists of the genes and as we shall show, this compact gene set delivers highly accurate performance across a range of classifiers. the functions of these genes are summarised in table additionally, we used the ma et al. data to test whether our method was successful on a dataset with different biology to the van't veer dataset. we have obtained a different set of genes. we also tested the generalisability of this gene set on an additional independent dataset exhibiting the same biological conditions. most of the later discussion will be using the van't veer data as an example, unless otherwise stated. biological significance of the compact gene sets as the treatment procedures applied to the patients in both the van't veer study and ma et al. study are vastly different, it is not surprising that there is no overlap between the two gene sets identified as the best predictors of prognosis outcome. the biology driving the chance to distant metastasis in each dataset is likely to be significantly different and as such it would not make sense to expect the gene lists to overlap. therefore, we will consider each gene set independently. gene ontology and kyoto encyclopedia of genes and genomes pathway analysis of the two gene sets show that each of the genes are diverse in function and appear to be unrelated in terms of the biological processes in which they are involved. what is interesting, however, is that the majority of the genes have been previously shown to be related to cancer in the literature. this suggests that our feature selection procedure yields a compact sampling of the diverse biological processes represented by the microarray, which are highly representative of the prognostic potential of the patient. in concordance with this, in the gene set, tspyl and ca have been previously used as prognostic biomarkers in cancer. furthermore, four of the top genes selected by our method are in the set of genes used in the study by van't veer. and the most important individual gene in improving a number of the classifier performances in the test set is present in the genes selected by alexe et al.. in the gene set, cd has been used previously as a prognostic biomarker in gastric cancer. links between identified genes and the cancer literature gene set each of the genes can be directly linked to potential cancer re-occurrence through their respective biological functions. tspyl is involved in nucleosome assembly, a process which, if destabilised, can alter the regulatory mechanisms of a cell, which is likely to occur in cancer. nmu has been shown to be related to metastatic potential and cancer cachexia, which would have a significant impact on the potential of reoccurrence of the cancer. ca is involved in nitrogen metabolism and is linked to cell proliferation and aspm is involved in mitotic spindle regulation and is expressed in proliferating tissues.. lin is involved in progression through the cell cycle and is a tumor suppressor that inhibits dna synthesis, thus having significant cancerous potential. regulation of the diaph gene is important in regulating the transcription factor mitf, which in turn regulates the invasiveness of melanoma. finally, while no significant link to cancer processes were found for agtpbp somatic mutations in the coding sequence have been found in colorectal cancers. gene set out of the genes in this set not only have links to cancer through the literature, they have in most cases been shown to be directly linked to prognostic outcome. a study into antibodies against zic in small lung cell carcinoma showed that the concentration of antibodies is a good indicator of prognosis. srda overexpression in hormone-refractory prostate cancers was shown to be crucial for cell viability and is a likely factor in resistance to hormone based therapies in prostate cancers. ppar has been shown previously to be abberently expressed in colon cancer cells and is an important player in the proliferation and growth of these cells. a protein involved in innate immune response which is critical to the regulation of the complement cascade, cd has been shown to be important in prostate growth, gastric tumor invasiveness and breast cancer prognosis. finally, rgs has been implicated in the control of autophagy in colon cancer cell lines. the demonstrated links of these genes with the literature highlights the relevancy of each of the genes with respect to cancer and demonstrates their potential to represent biological processes which are directly related to the prognostic potential of a patient. classification performance on test set gene set the best performance for the test dataset obtained was % for c with boosting. this performance was achieved using only three genes: tspyl diaph and agtpbp it is worth noting that the gene subset {tspyl diaph1} was found to be significant for at least six of the considered classifiers. it was also found that the gene tspyl is the most influential and has been chosen by all the considered classifiers. the performance of ann and svm was found to be better for the gene subsets {tspyl ca9}, and {tspyl lin9}, respectively. the gene lin was found to be important only when using svm. similarly, the gene ca was found to be suitable for the ann and logistic regression along with other genes. an analysis of the experimental results reveals that similar types of classifiers tended to choose the same subset of genes to obtain the best performance. for instance, random forest, random forest with bagging and random forest with boosting, are essentially similar classifiers with some small variation. all these classifiers chose the gene subset {tspyl diaph aspm} for classifying the dataset. however, random forest with bagging produced the best accuracy of the three different types of random forest considered in this study, adding the gene nmu to the common gene subset {tspyl diaph aspm}. thus, a subset of genes used by all classifiers is selected as the important gene subset. table summarises the classification accuracy for both the individual test set of van't veer and for fold cross validation, comparing the use of subsets of the genes, versus the scenario where all genes are used. *our experiments were carried out on a standard intel core duo cpu ghz desktop computer running gb of ram. gene set discussion in our multi-classifier voting approach, one selects a subset of genes using an roc based ranking. this is then followed by a classifier voting phase, to refine this list of genes even further. our improved performance is achieved due to two factors. first, roc is a classifier independent method that is not dependent on the standard deviation of the features. second, the multi-classifier voting gene selection approach produces the best possible combination of genes satisfied by a majority of the classifiers. these two benefits contribute to obtaining a better classification performance for the complete set of unseen datasets. furthermore, the significant reduction of genes we obtain is another advantage of our approach. previous studies that link gene expression profiles to clinical outcomes in breast cancer cases have demonstrated that the potential for distant metastasis and overall survival probability may be attributable to the biological characteristics of the primary tumor at the time of diagnosis. in particular, a 70-gene expression signature by van't veer has proven to be a strong prognostic factor, outperforming all known clinicopathological parameters. the accuracy in distinguishing cases of poor and good breast cancer prognosis, provided by the subset of genes selected by van't veer, was revalidated and confirmed by van de vijver in a different cohort of patients. however, genes is not a compact set, greatly increasing the expense of developing a clinical predictor. even the set of genes by alexe et al. is twice as large as our gene set. our method yielded better accuracy with genes, and that, too, was independent of a specific classifier. having a compact set of genes is extremely important from a treatment and drug development viewpoint, where clinical and experimental validation is costly and it is vital to restrict the number of hypotheses or targets to be followed up. we also show, in the comparison of our gene set with the gene set of ma et al. in table using the loi et al. data, that our approach avoids generating an overly compact geneset that may not generalise well to microarray data from another lab. this is extremely important when attempting to develop a robust predictor in a clinical setting. we have also compared our best results for the van't veer dataset against some well known cancer treatment guidelines. it clearly shows that machine learning approaches are effective technique in classifying breast cancer prognosis. *results obtained from gevaert et al., where results were provided as number of true positives and true negatives. comparison with other studies a number of efforts have been made in this direction for breast cancer prognosis but without major success. ritz combined both genetic and clinical information in a neural network for breast cancer prognosis, but found that the combination did not improve the performance. dettling et al. applied penalized logistic regression analysis to predict cancer prognosis for the van't veer dataset. they found that none of the clinical variables entered the model and concluded that the clinical data did not contain any useful independent information for prediction, given the gene expression profile. to prognosticate on the breast cancer dataset, alexe et al. applied the logical analysis of data tool to analyze microarray data. they identified genes out of possible genes that could distinguish patients with poor or good prognoses. amongst the genes the lad tool identified three and five genes that were associated with poor and good prognoses, respectively. two wholly new classes of patients were discovered. it was also demonstrated that the training and test sets of van't veer differ in their characteristics. however, this study of alexe et al. was overly specific to the chosen classifier, as we shall shortly see. we assessed the classification performance of five different subsets of genes on the van't veer dataset. the and genes selected by van't veer, the set of genes selected by the lad technique, a set of genes selected by roc with markov blanket and the set of genes selected by our voting approach. for roc with markov blanket we have used the same parameter for the number of genes to select as given in that paper, namely genes and then using an area between two roc curves value > for the second step, chosen to yield the most competitive performance for the technique. we applied five classification methods used by alexe et al. and our top performing classifier c with boosting on the gene set of size these classification methods include ann, svm, logistic regression, k-nn, c decision tree and c with boosting. following this, predictive models were constructed for the training set and were tested using the supplied test set of samples. *results adopted from alexe et al.. it is clear that the weighted accuracy in distinguishing patients with good and poor breast cancer prognoses is the highest across all classifiers using the genes selected by our voting approach and is much higher than the models using, and genes. our approach produced much better performance for most classifiers, except for ann, where using the selected genes of alexe et al. or by using roc with markov blanket was better. however, the methodology of alexe et al. incorporated a "selection bias" for finding their subset of genes, since the test set was used. in contrast, our voting approach did not have access to the test set for gene selection. when selecting genes using our voting approach, we used only the training dataset, keeping the test set completely unknown. the performance of the classifiers using the selected and genes by van't veer was found to be insignificant compared with that of our approach. furthermore, or is not a compact set of genes and our voting method can obtain a better accuracy using at most four genes. gevaert et al. proposed a bayesian networ k-based strategy to treat clinical and microarray data along the same lines as above using the same dataset. a probabilistic model was used because it integrates the data sources in several ways, and explores and documents the model structure and parameters. the concept of a markov blanket is used to identify all the variables that shield the class variable from being affected by the rest of the network. however, all the processes are integrated in the classifier, and hence the performance of the system is biased towards the choice of a classifier. furthermore, the performance of the classifier would depend on the selection of the initial distribution for the model. comparison with other filter approaches jeffery et al. have demonstrated that the roc is an accurate way to identify differentially regulated genes in a microarray dataset and that it can produce robust classifiers applying feature selection techniques on gene expression datasets. when dealing with datasets that have or more samples, the roc was shown to be the most accurate. other filter approaches like t-test and principle component analysis produce reasonable results, but roc yields better results on the van't veer dataset. it is particularly useful for gene expression data, as it is not directly dependent on the standard deviation of the expression of each gene like the t-test is, or only on the correlation of each genes like the pca is. moreover, unlike pca, roc is not sensitive to the scaling of the data. gene set significance tests it is interesting to consider the results of gene set enrichment analysis on our set of genes obtained by voting, against the other gene sets proposed by van't veer et al., alexe et al., and the one we have obtained using mamitsuka's technique. three out of the five gene sets are enriched in phenotype. of which, mamitsuka's and our gene sets have an fdr q-value equal to and, with an enrichment score of and, respectively. members of the leading edge subset also indicate that our gene set contains only those genes contributing to the enrichment score, compared to the other gene sets that contain only a fraction of genes contributing to the enrichment score.  we have proposed and implemented a multi-classifier voting approach for gene selection, to effectively classify the prognosis of breast cancer patients using data from two distinct treatment cases. the novelty of our approach is that it can identify a very small number of genes that are predictive across a large range of classifiers. we applied our voting approach to three well-known microarray datasets, related to breast cancer. experimental analysis demonstrated high prediction accuracies for the gene sets discovered, compared to previous studies. the gene sets discovered were also biologically relevant and had good biological process coverage. list of abbreviations used roc: receiver operating characteristic; auc: area under the roc curve; lmt: logistic model tree; k-nn: k-nearest neighbour; ann: artificial neural network; svm: support vector machine; nbtree: naïve bayes tree; cv: cross validation; pca: principle component analysis; gsea: gene set enrichment analysis; es: enrichment score; go: gene ontology; kegg: kyoto encyclopedia of genes and genomes competing interests the authors declare that they have no competing interests. authors' contributions mrh, mmh and kr conceived the design of the roc ranking and voting algorithm. jb and gm contributed to the experimental design, and the experiments were performed by mmh and mrh. the biological significance was investigated by gm and jwkh and the writing was performed with input from all authors. supplementary material additional file 1 this file contains the rank gene list used in each fold of 5-fold cv, and performance of each fold using the selected genes for different classifier. click here for file additional file 2 this file contains the result of gene set enrichment analysis. click here for file acknowledgements this work is partially supported by national ict australia. national ict australia is funded by the australian government's backing australia's ability initiative in part through the australian research council. mmh is supported by a melbourne research scholarship. jwkh and gm are supported by an australian postgraduate award and a nicta research project award. this article has been published as part of bmc bioinformatics volume supplement 2009: proceedings of the seventh asia pacific bioinformatics conference the full contents of the supplement are available online at
by using a new type of multiple classifier voting approach, we have identified gene sets that can predict breast cancer prognosis accurately, for a range of classification algorithms. we show that it is possible to obtain superior classification accuracy with our approach and obtain a compact gene set that is also biologically relevant and has good coverage of different biological processes. experimental analysis demonstrates higher prediction accuracies for our sets of genes compared to previous work in the area. an important challenge for this type of data is the discovery of gene sets which can be used as the basis of developing a clinical predictor for cancer. it is desirable that such gene sets be compact, give accurate predictions across many classifiers, be biologically relevant and have good biological process coverage.
 microarray gene expression profiling has provided extensive datasets that can describe characteristics of cancer patients. an important challenge for this type of data is the discovery of gene sets which can be used as the basis of developing a clinical predictor for cancer. it is desirable that such gene sets be compact, give accurate predictions across many classifiers, be biologically relevant and have good biological process coverage.  by using a new type of multiple classifier voting approach, we have identified gene sets that can predict breast cancer prognosis accurately, for a range of classification algorithms. unlike a wrapper approach, our method is not specialised towards a single classification technique. experimental analysis demonstrates higher prediction accuracies for our sets of genes compared to previous work in the area. moreover, our sets of genes are generally more compact than those previously proposed. taking a biological viewpoint, from the literature, most of the genes in our sets are known to be strongly related to cancer.  we show that it is possible to obtain superior classification accuracy with our approach and obtain a compact gene set that is also biologically relevant and has good coverage of different biological processes. 13– january the seventh asia pacific bioinformatics conference beijing, china 