BACKGROUND
an important goal of microarray studies with two classes is to identify genes, for further investigation, that "explain" much of the class differences.
one common approach is to look separately at genes that exhibit high differential expression.
the disadvantage of this approach is that it ignores the role of gene combinations in leading to good classification.
another approach is to investigate classification rules for combinations of genes.
while this approach accounts for gene interactions, too often these rules involve so many genes that it is difficult to determine those genes that are not included simply by chance.
our strategy is to look for classification rules that perform well with few genes, so as to have a stronger "signal" to detect genes that contribute most to good classification.
there are various approaches to developing classification rules for microarrays and identifying genes for further investigation.
almost all approaches involve a split of the data into training and test samples.
in the training sample a classification rule is developed, and in the test sample its performance is determined.
two common measures of performance are cross-validation  <cit>  and multiple random validation  <cit> .
in k-fold cross-validation, the data are divided into k subsets.
on each iteration of the cross-validation a different collection of the k- <dig> subsets serve as the training sample and the remaining subset serves as the test sample.
the performance of the classification rule is the average performance in the k test samples  <cit> .
in multiple random validation, the data are randomly split into training and test samples many times.
unlike cross-validation, the goal is not to average performance over test samples but to investigate the variability of performance over test samples and the frequencies of genes selected on random splits  <cit> .
there are also various approaches for formulating a classification rule in the training sample.
one common approach, called a filter, selects genes with the best individual performances prior to formulation of the classification rule.
another common approach, called a wrapper, splits the training sample into a training-training sample and a training-test sample and uses cross-validation within the training sample to both select genes and formulate a classification rule  <cit> .
unlike a filter, a wrapper can identify genes that perform poorly individually but well together, but the price is likely increased variability in the measure of performance due to a small training-test sample .
importantly, both approaches for gene selection involve a threshold for the number of genes to include in a classification rule.
without a threshold it is possible to obtain excellent classification in the training sample  that would likely do poorly in the test sample because the classification rule has been overly tailored to the training sample.
the threshold is either specified in advance or determined by a performance criterion and typically yields a moderate to large number of genes  <cit>
the identification of a moderate number of genes is theoretically desirable because the genes likely form a network.
however we are concerned that, despite the use of refined approaches, it is more likely that with classification rules involving a moderate number of genes rather than a few genes, that some genes will be detected by chance therefore our goal was to identify classification rules that perform well with the fewest genes, and so may be more "robust" than rules with more genes.
importantly with fewer genes in the classification rule, it is easier to identify genes with relatively high frequencies in multiple random validation.
such genes are most likely to represent a true "signal."
the identification of a few genes that contribute to good classification and are not likely detected by chance allows investigators to better focus further research efforts, perhaps leading to easier clinical application, simpler dissemination of results, and possibly improved scientific insights.
although our general strategy could be applied to any of a variety of microarray classification techniques, we chose a simple approach.
for classification we used a filter and the nearest centroid rule, which is easy to implement and has been previously shown to perform well  <cit> .
to measure performance in a comprehensive manner that captures errors in assignments to both classes, we used receiver operating characteristic  curves and the estimated area under the roc curve , which ranges from 1/ <dig> for chance classification to  <dig> for perfect classification  <cit> .
to characterize chance variability we used the previously mentioned multiple random validation procedure that involves repeated random splits of training and test samples  <cit> .
we analyzed data from four published microarray studies involving colon cancer  <cit> , leukemia  <cit> , medulloblastoma  <cit> , and breast cancer  <cit> .
see table  <dig>  although multiple random validation strategy had been used with the colon cancer, medulloblastoma, and breast cancer data sets, these analyses did not involve a comparison of performances for few  versus many genes.
RESULTS
the classification performance generally improved as the number of genes in the classification rule increased from  <dig> to  <dig> to  <dig> to  <dig> with small decreases in improvement likely due to chance.
see figure  <dig> and table  <dig>  because the classification for the medulloblastoma data was poor with an estimated auc not significantly better than chance , we only report in detail the results for the three other data sets.
for these data sets, the performance of the classification rule was more similar between rules with  <dig>   <dig>  and  <dig> genes than between rules with  <dig> and  <dig> genes, particularly when considering the lower bound of the estimated auc.
results when the training sample split was one half the data are given below.
for the colon cancer data set the estimated auc  was .
<dig> , .
<dig> , .
<dig> , and .
<dig>  with  <dig>   <dig>   <dig>  and  <dig> genes respectively; for leukemia data set it was .
<dig> , .
<dig> , .
<dig> , and .
<dig>  for  <dig>   <dig>   <dig>  and  <dig> genes, respectively; and for the breast cancer data set it was .
<dig> , .
<dig> , .
<dig> , and .
<dig>  for  <dig>   <dig>   <dig>  and  <dig> genes, respectively.
similar results were obtained with a four-fifths split into the training sample .
for the three data sets in which the classification rule for  <dig> genes performed well, we investigated the classification rule for  <dig> genes to determine if any genes had relatively high frequencies of selection.
gene histograms are shown in figure  <dig>  for the breast cancer data set, no gene had a relatively high frequency.
for the colon cancer data set, the human desmin gene had a relatively high frequency .
human desmin is essential for maintaining the structural integrity of skeletal muscle  <cit> .
desmin has also been used in a study of colon cancer as a marker for fat storing cells  <cit> , and, in a study of colon polyps from  <dig> cases, all were negative for desmin  <cit> .
for the leukemia data the zyxin gene had a high relative frequency , 44%, 34%, and 31% when the training sample contained four-fifths the data.)
zyxin plays a pivotal role in mitosis  <cit> .
after completing our analysis, we found that other investigators of the same data set identified zyxin has the most significant feature for classification, discussed some possible biological links, and recommended further investigation of the role of zyxin in leukemia  <cit> .
secretory granule proteoglycan was the other gene with high relative frequency in the leukemia data set when the training sample contained four-fifths of the data.
the peptide core of a secretory granule proteoglycan, serglycin, has been implicated in gene methylation of leukemia cells  <cit> .
methylation is an important process in the regulation of expression in many genes.
serglycin is also involved in the formation of granules in neutrophil granulocytes  <cit> .
granules are important for distinguishing the two classes of leukemias.
interestingly secretory granule proteoglycan was not listed among identified genes in other classifications of these data  <cit> .
discussion
other classification rules for the same data sets performed similarly to ours  <cit> ; however precise comparison of misclassification rates is not meaningful due to differences in the validation procedures, particularly when there was no random splitting of training and test samples.
in terms of methodology for gene selection and classification, there are several related approaches: a filter with multiple random validation of the entire sample  <cit> , a wrapper with multiple random validation of the entire sample  <cit> , and a wrapper with multiple random cross-validation within the training sample and no independent test sample  <cit>  .
see table  <dig>  our approach can be viewed either as  a wrapper with multiple random validation  and a training-test sample instead of a test sample or  a filter with multiple random validation of the entire sample.
these related approaches computed either gene frequencies or a relevancy measure  <cit>  that can be viewed as a frequency when the weights equal  <dig>  our general strategy of finding classification rules with few genes that perform well and then identifying genes with relatively high frequencies under multiple random validation applies to both classification rules with filters and wrappers.
future research using a wrapper would be of great interest because of the potential of the wrapper to identify genes that have good classification when considered together but poor classification when considered separately.
the inclusion of additional genes in the classification rule can affect performance in one of two ways depending on whether or not the additional genes are predictive of outcome or not.
if the additional genes are not predictive , the performance of the rule in the test sample will likely worsen due to additional "noise".
if the additional genes are predictive, then performance in the test sample will improve with more "signals."
improvement in performance is greatest if the additional predictive genes are independent and smaller if the additional predictive genes are correlated.
in our microarray studies, which showed small gains in performance with additional genes, the genes were likely predictive and correlated.
our goal is to identify genes with high relative frequencies of selection in the classification rule with few genes.
it is important to consider only classification rules with few genes because with moderate numbers of genes in the classification rules, many genes invariably appear in nearly all the classification rule and hence there is a concern that many genes are included by chance.
with few genes in the classification rule, one can sometimes find, as in two of our data sets, one or two genes with relatively high frequencies, which seems like a strong "signal" that these genes make a real contribution to classification and are hence worthy of further study.
it is, however, possible that many highly associated genes could have similarly high frequencies of occurrence in classification rules with few genes and one should be aware of this potential scenario.
throughout this study we have been "conservative" in our identification of genes for further study by trying to rule out, as much as possible, the role of chance in explaining good classification.
hence we used multiple random validation and focused on as few genes as possible.
we also wanted our measure of performance to be as informative as possible by using roc curves.
the 95% confidence intervals we report are only approximate because they are based on repeated sampling from a finite population, namely  <dig> to  <dig> specimens.
however for our purposes, approximate confidence intervals are acceptable, because the main focus is not precisely estimating the variability of classification performance but rather the identification of genes that make a strong contribution to good classification performance.
CONCLUSIONS
a relevant quote attributed to the noted mathematician henri poincare is, "science is built up of facts, as a house is with stones.
but a collection of facts is no more a science than a heap of stones is a house."
often investigators report large numbers of genes that are either differentially expressed or constitute a classification rule, but which, due to the influence of chance, may be more of a "heap of stones" than part of a "house."
to confidently identify the basic "building blocks" for classification of cancer outcomes, investigators should use multiple random validation to find classification rules that perform well with few genes and select genes with relatively high frequencies of occurrence in these classification rules.

 an important goal of microarray studies with two classes is to identify genes, for further investigation, that "explain" much of the class differences. one common approach is to look separately at genes that exhibit high differential expression. the disadvantage of this approach is that it ignores the role of gene combinations in leading to good classification. another approach is to investigate classification rules for combinations of genes. while this approach accounts for gene interactions, too often these rules involve so many genes that it is difficult to determine those genes that are not included simply by chance. our strategy is to look for classification rules that perform well with few genes, so as to have a stronger "signal" to detect genes that contribute most to good classification. there are various approaches to developing classification rules for microarrays and identifying genes for further investigation. almost all approaches involve a split of the data into training and test samples. in the training sample a classification rule is developed, and in the test sample its performance is determined. two common measures of performance are cross-validation and multiple random validation. in k-fold cross-validation, the data are divided into k subsets. on each iteration of the cross-validation a different collection of the k- subsets serve as the training sample and the remaining subset serves as the test sample. the performance of the classification rule is the average performance in the k test samples. in multiple random validation, the data are randomly split into training and test samples many times. unlike cross-validation, the goal is not to average performance over test samples but to investigate the variability of performance over test samples and the frequencies of genes selected on random splits. there are also various approaches for formulating a classification rule in the training sample. one common approach, called a filter, selects genes with the best individual performances prior to formulation of the classification rule. another common approach, called a wrapper, splits the training sample into a training-training sample and a training-test sample and uses cross-validation within the training sample to both select genes and formulate a classification rule. unlike a filter, a wrapper can identify genes that perform poorly individually but well together, but the price is likely increased variability in the measure of performance due to a small training-test sample. importantly, both approaches for gene selection involve a threshold for the number of genes to include in a classification rule. without a threshold it is possible to obtain excellent classification in the training sample that would likely do poorly in the test sample because the classification rule has been overly tailored to the training sample. the threshold is either specified in advance or determined by a performance criterion and typically yields a moderate to large number of genes the identification of a moderate number of genes is theoretically desirable because the genes likely form a network. however we are concerned that, despite the use of refined approaches, it is more likely that with classification rules involving a moderate number of genes rather than a few genes, that some genes will be detected by chance therefore our goal was to identify classification rules that perform well with the fewest genes, and so may be more "robust" than rules with more genes. importantly with fewer genes in the classification rule, it is easier to identify genes with relatively high frequencies in multiple random validation. such genes are most likely to represent a true "signal." the identification of a few genes that contribute to good classification and are not likely detected by chance allows investigators to better focus further research efforts, perhaps leading to easier clinical application, simpler dissemination of results, and possibly improved scientific insights. although our general strategy could be applied to any of a variety of microarray classification techniques, we chose a simple approach. for classification we used a filter and the nearest centroid rule, which is easy to implement and has been previously shown to perform well. to measure performance in a comprehensive manner that captures errors in assignments to both classes, we used receiver operating characteristic curves and the estimated area under the roc curve, which ranges from 1/ for chance classification to for perfect classification. to characterize chance variability we used the previously mentioned multiple random validation procedure that involves repeated random splits of training and test samples. we analyzed data from four published microarray studies involving colon cancer, leukemia, medulloblastoma, and breast cancer. see table although multiple random validation strategy had been used with the colon cancer, medulloblastoma, and breast cancer data sets, these analyses did not involve a comparison of performances for few versus many genes.  the classification performance generally improved as the number of genes in the classification rule increased from to to to with small decreases in improvement likely due to chance. see figure and table because the classification for the medulloblastoma data was poor with an estimated auc not significantly better than chance, we only report in detail the results for the three other data sets. for these data sets, the performance of the classification rule was more similar between rules with and genes than between rules with and genes, particularly when considering the lower bound of the estimated auc. results when the training sample split was one half the data are given below. for the colon cancer data set the estimated auc was.,.,., and. with and genes respectively; for leukemia data set it was.,.,., and. for and genes, respectively; and for the breast cancer data set it was.,.,., and. for and genes, respectively. similar results were obtained with a four-fifths split into the training sample. for the three data sets in which the classification rule for genes performed well, we investigated the classification rule for genes to determine if any genes had relatively high frequencies of selection. gene histograms are shown in figure for the breast cancer data set, no gene had a relatively high frequency. for the colon cancer data set, the human desmin gene had a relatively high frequency. human desmin is essential for maintaining the structural integrity of skeletal muscle. desmin has also been used in a study of colon cancer as a marker for fat storing cells, and, in a study of colon polyps from cases, all were negative for desmin. for the leukemia data the zyxin gene had a high relative frequency, 44%, 34%, and 31% when the training sample contained four-fifths the data.) zyxin plays a pivotal role in mitosis. after completing our analysis, we found that other investigators of the same data set identified zyxin has the most significant feature for classification, discussed some possible biological links, and recommended further investigation of the role of zyxin in leukemia. secretory granule proteoglycan was the other gene with high relative frequency in the leukemia data set when the training sample contained four-fifths of the data. the peptide core of a secretory granule proteoglycan, serglycin, has been implicated in gene methylation of leukemia cells. methylation is an important process in the regulation of expression in many genes. serglycin is also involved in the formation of granules in neutrophil granulocytes. granules are important for distinguishing the two classes of leukemias. interestingly secretory granule proteoglycan was not listed among identified genes in other classifications of these data. discussion other classification rules for the same data sets performed similarly to ours; however precise comparison of misclassification rates is not meaningful due to differences in the validation procedures, particularly when there was no random splitting of training and test samples. in terms of methodology for gene selection and classification, there are several related approaches: a filter with multiple random validation of the entire sample, a wrapper with multiple random validation of the entire sample, and a wrapper with multiple random cross-validation within the training sample and no independent test sample. see table our approach can be viewed either as a wrapper with multiple random validation and a training-test sample instead of a test sample or a filter with multiple random validation of the entire sample. these related approaches computed either gene frequencies or a relevancy measure that can be viewed as a frequency when the weights equal our general strategy of finding classification rules with few genes that perform well and then identifying genes with relatively high frequencies under multiple random validation applies to both classification rules with filters and wrappers. future research using a wrapper would be of great interest because of the potential of the wrapper to identify genes that have good classification when considered together but poor classification when considered separately. the inclusion of additional genes in the classification rule can affect performance in one of two ways depending on whether or not the additional genes are predictive of outcome or not. if the additional genes are not predictive, the performance of the rule in the test sample will likely worsen due to additional "noise". if the additional genes are predictive, then performance in the test sample will improve with more "signals." improvement in performance is greatest if the additional predictive genes are independent and smaller if the additional predictive genes are correlated. in our microarray studies, which showed small gains in performance with additional genes, the genes were likely predictive and correlated. our goal is to identify genes with high relative frequencies of selection in the classification rule with few genes. it is important to consider only classification rules with few genes because with moderate numbers of genes in the classification rules, many genes invariably appear in nearly all the classification rule and hence there is a concern that many genes are included by chance. with few genes in the classification rule, one can sometimes find, as in two of our data sets, one or two genes with relatively high frequencies, which seems like a strong "signal" that these genes make a real contribution to classification and are hence worthy of further study. it is, however, possible that many highly associated genes could have similarly high frequencies of occurrence in classification rules with few genes and one should be aware of this potential scenario. throughout this study we have been "conservative" in our identification of genes for further study by trying to rule out, as much as possible, the role of chance in explaining good classification. hence we used multiple random validation and focused on as few genes as possible. we also wanted our measure of performance to be as informative as possible by using roc curves. the 95% confidence intervals we report are only approximate because they are based on repeated sampling from a finite population, namely to specimens. however for our purposes, approximate confidence intervals are acceptable, because the main focus is not precisely estimating the variability of classification performance but rather the identification of genes that make a strong contribution to good classification performance.  a relevant quote attributed to the noted mathematician henri poincare is, "science is built up of facts, as a house is with stones. but a collection of facts is no more a science than a heap of stones is a house." often investigators report large numbers of genes that are either differentially expressed or constitute a classification rule, but which, due to the influence of chance, may be more of a "heap of stones" than part of a "house." to confidently identify the basic "building blocks" for classification of cancer outcomes, investigators should use multiple random validation to find classification rules that perform well with few genes and select genes with relatively high frequencies of occurrence in these classification rules. 
our strategy is to search for classification rules that perform well with few genes and, if they are found, identify genes that occur relatively frequently under multiple random validation. using multiple random validation, investigators should look for classification rules that perform well with few genes and select, for further study, genes with relatively high frequencies of occurrence in these classification rules. in the three data sets with good classification performance, the classification rules for genes were only slightly worse than for or genes and somewhat better than for gene. in two of these data sets, one or two genes had relatively high frequencies not noticeable with rules involving or genes: desmin for classifying colon cancer versus normal tissue; and zyxin and secretory granule proteoglycan genes for classifying two types of leukemia. the goal of most microarray studies is either the identification of genes that are most differentially expressed or the creation of a good classification rule. the disadvantage of the former is that it ignores the importance of gene interactions; the disadvantage of the latter is that it often does not provide a sufficient focus for further investigation because many genes may be included by chance. to comprehensively measure classification performance we used receiver operating characteristic curves. for classification we used a filter with a nearest centroid rule that is easy to implement and has been previously shown to perform well.
 the goal of most microarray studies is either the identification of genes that are most differentially expressed or the creation of a good classification rule. the disadvantage of the former is that it ignores the importance of gene interactions; the disadvantage of the latter is that it often does not provide a sufficient focus for further investigation because many genes may be included by chance. our strategy is to search for classification rules that perform well with few genes and, if they are found, identify genes that occur relatively frequently under multiple random validation.  we analyzed data from four published studies related to cancer. for classification we used a filter with a nearest centroid rule that is easy to implement and has been previously shown to perform well. to comprehensively measure classification performance we used receiver operating characteristic curves. in the three data sets with good classification performance, the classification rules for genes were only slightly worse than for or genes and somewhat better than for gene. in two of these data sets, one or two genes had relatively high frequencies not noticeable with rules involving or genes: desmin for classifying colon cancer versus normal tissue; and zyxin and secretory granule proteoglycan genes for classifying two types of leukemia.  using multiple random validation, investigators should look for classification rules that perform well with few genes and select, for further study, genes with relatively high frequencies of occurrence in these classification rules. 