in the past decade , microarray - based gene expression profiling has become a widely studied field of research . additionally , with the introduction of commercial gene expression - based diagnostic tests , microarrays are finally coming into practical use . to construct a reliable set of genes or gene expression signature the initially used methods for gene selection were based on simple statistical tests and could evaluate only a single gene at a time . examples of such univariate gene selection methods include gene selection based on t - test   ( with multiple variants ) , signal - to - noise ( sn ) ratio , correlation tests , information gain , and so forth . nowadays , novel and more complex multivariate gene selection methods , which can evaluate groups of genes and detect interactions among multiple genes simultaneously , are introduced on a frequent basis . one of the most serious problems in the detection and evaluation of reliable gene expression signatures is the lack of studies that use large number of samples . a recent study by xu et al .   suggests the integration of multiple microarray studies to increase the sample size , and demonstrates a novel method of microarray integration on breast - cancer gene expression signatures . however , such gene expression signatures are very unstable owing to different protocols and sources of data used in different laboratories . on the other hand , there are much more data sets with relatively high number of samples available today than a few years ago . our study exploits the advantage of one of the largest publicly available repositories of gene expression measurements that were collected by the international genomics consortium . this paper presents an empirical study on different supervised gene selection techniques from the perspective of the stability of the ranked gene lists . the usual way of estimating the  goodness  of the ranked gene lists is by using them for the classification of samples and measuring different accuracy metrics like percentage of correctly classified samples or area under roc curve , shortly auc . in this study , three different metrics for ranked gene lists similarity were used to estimate the stability of the gene selection method . another important factor is the stability of the stability metrics or metastability that can be of significant importance when comparing the performance of the feature selection on data sets with different number of samples . meta - stability in this study was measured as the standard deviation of the stability metric . stability and meta - stability of the gene selection methods was observed on data sets with 50 and up to 600 samples . our study demonstrated that one should be careful in selecting a particular feature selection method when more and more gene expression data sets with up to 500 or even 1000 patients are available . a paper by ma   was one of the first papers in gene expression analysis comparing different supervised gene selection methods by bootstrapping the samples of initial data set . ma measured the concordance and reproducibility of the supervised gene screening based on eight different gene selection methods . the measurements of concordance were done by overlapping the selected genes with different settings for n top genes . among other conclusions , this empirical study once again explained that genes passed through different gene selection methods may be considerably different . unfortunately , experimentation using different number of samples was not possible owing to small number of samples present in the three data sets that were used in study by ma . in which the stability of differentially expressed genes was evaluated using the measurement of frequency , by which a given gene is selected across the subsamples . they showed that resampling can be an appropriate technique to determine a set of genes with sufficiently high frequency . furthermore , they recommended using resampling techniques to assess the variability of different performance indicators . in contrast to our research , their approach was based on measuring the stability of single genes and not the ranked lists of genes produced by the gene selection methods . once again , their method was not tested on data sets with large number of samples . their experiments were carried out on simulated data consisting of 30 ( small data set ) and 86 ( large data set ) samples , which is much lesser than the number of samples used in this study . however , ein - dor et al .   determined that the gene lists obtained for the same clinical types of patients by different laboratories often differ significantly and have very few common genes . they evaluated the robustness of gene lists by employing the probably approximately correct ( pac ) sorting , and pointed out that an achievement of a typical overlap of 50% between two lists of genes would require expression profiles of over thousand patients with early detection of breast cancer . using microarray data sets that are available today , our study tried to confirm the conclusions of the study by ein - dor et al . although most of the above - mentioned studies used only a simple overlap metric , there are many other metrics available , which had been used in similar earlier researches . one of the fields in which such metrics were initially used in empirical studies is the information retrieval ( ir ) , where the metrics used to compare the stability of the results returned by different web search engines . a study by bar - ilan et al .   used the metrics for the stability of ranked lists to monitor the consistency of the web search results for the most popular search engines through time . the metrics that they used were principally proposed much earlier by fagin et al .   who also theoretically defined them . in our study , we initially evaluated three ranked lists stability metrics , that is , simple overlap , weighted overlap , and extended spearman stability metric . the latter two metrics were proposed by fagin et al . to define the metrics that would award the subjects ( genes ) similarly ranked at the top of the list in comparison with those that were ranked lower . the original data were obtained from the expression project for oncology ( expo ) data set from the international genomics consortium ( http://www.intgen.org/ ) that was deposited at gene expression omnibus ( geo ) repository , accession number gse2109 . samples from this collection represent an integral part of the gene expression machine learning repository ( gemler ) , available at http://gemler.fzv.uni - mb.si/. all the samples were based on affymetrix genechip u133 plus 2.0 arrays and were normalized using mas5 . the empirical tests for this study were conducted using four data sets from gemler that were chosen by the highest number of available samples . therefore , a collection of four data sets with more than 500 samples ( table 1 ) was selected for the experimental work . one can observe the lower than normal number of probes for u133 plus 2.0 arrays which is due to prefiltering using maximal variance of signal where 20% of probes with the highest variance were retained . gene selection methods are used to identify the gene subsets of microarray data that can be further used to effectively discriminate the different clinical conditions . all the gene selection and classification methods , except signal - to - noise method , are a part of weka environment   that was used to conduct this study . signal - to - noise ( sn ) gene selection was introduced by golub et al .   and represents a typical univariate gene selection method , that is , genes are scored individually one at a time and later ranked by their score defining their ability to separate samples based on a single gene . the sn gene ranking method is a variant of the widely used t - score - based statistical gene selection methods . it has a simple definition 
								 ( 1)sni=|12|1+2 , 
							 where difference of mean gene expression values for classes 1 and 2 is divided by sum of 1 and 2 that represent standard deviations of gene expression values for samples belonging to class 1 and class two , respectively . subsequently , the genes are sorted according to their sni scores and the n top genes are selected as members of the ranked gene list . direct interpretation of this score suggests that it measures the degree of overlap for the ith gene distribution in both the classes . however , it can only be used in binary problems where there are only two different classes . information gain ( ig ) is another method from the family of univariate gene selection methods . information theory - based   gene selection that was initially used in the decision - tree - building algorithms   has also been used as one of the gene selection procedures . the ig is a measure - based method , where each gene obtains an ig score . in our study an infogainattributeeval implementation from weka environment , as defined in , was used for evaluation of genes by measuring their information gain with respect to the class . discretization of numeric values was done using the minimum description length ( mdl)-based discretization method by . usually , n top genes are selected for the inclusion in the gene expression signature . in our study , 100 top genes were used in all the experiments . relieff gene selection method is a representative of the multivariate gene selection techniques , where a group of genes is evaluated synchronously . relieff algorithm is based on the original relief algorithm   that could only be used for the classification problems with two class values and nominal values of variables . the basic idea of relief algorithm is ranking of features based on their ability to distinguish between instances that are near to each other . the original algorithm was extended by kononenko , so that it can deal with multiclass problems and missing values . later , it was further improved by robnik - sikonja and kononenko   to suit the noisy data and for its usage in regression problems . support vector machines recursive feature elimination ( svm - rfe ) represents another multivariate gene selection method . the svm in combination with rfe were introduced for gene selection in bioinformatics by guyon et al . . the svm - rfe feature selection method is based on linear svm used as the learning algorithm . in the final step of each cycle , all the genes are ranked and a preselected number of the lowest - ranked genes are eliminated . by default , however , it is also possible to remove more than one feature per round . to measure the stability of gene lists produced by specific gene selection methods , one should employ appropriate metrics that are able to statistically measure the differences between the two lists of ranked genes . this study uses three different stability measures , that is , overlap , weighted overlap , and spearman ranked - list similarity metric . overlap is one of the simplest measures of similarity , where the similarity of the two lists ( 1 , 2 ) is not based on the ranking of the genes . the degree of similarity is calculated by simple counting of the genes that are present in both the lists and dividing them by the number of genes in each list . the top - k genes overlap can be defined as 
								 ( 2)(k,1,2)=i=1k(1(i),2)k , 
							 where 
								 ( 3)(1(i),2)={0,if  1(i)2=,1,otherwise.weighted overlap represents an improved version of the overlap metric , where the higher - ranked genes present in both the lists contribute to higher degree of similarity than the lower - ranked genes present in both the lists . weighted overlap gradually builds overlap score by starting with only the top ranked gene from both compared lists and continues to add top ranked genes one by one . it can be defined as 
								 ( 4 )  (w)(k,1,2)=i=1k(i,1,2)k.spearman 's ranked - lists similarity measure , also called spearman 's footrule , requires all the genes present in both the lists for the actual implementation of this measure . in case of gene selection that would mean that both compared selection methods must select the same set of genes , that can be ranked differently . to define spearman 's footrule , it is necessary to introduce 1(i ) and 2(i ) that represent ranks of gene i in lists 1 and 2 , respectively . by introducing normalization to [ 0 , 1 ] interval , the value 1 is obtained when both the lists completely agree , and 0 is obtained for the genes from both the lists in the opposite order 
								 ( 5 )  (sp)(k,1,2)=1i=1k|1(i)2(i)|max  ( (sp)(k,1,2 ) ) . the original method was applied to the nonequal lists of the same size by fagin et al . , and is therefore much more suitable for comparison of ranked gene lists 
 ( 6)(f)(k,1,2)=2(kz)(k+1)+iz|1(i)2(i)|is1(i )  it1(i ) , 
							 where z stands for number of genes present in both lists , z represents a set of genes that are present in both lists , s represents set of genes that are present only in the first list of genes and vice - versa for t. after normalization and transformation to ,   we get 
								 ( 7 )  (fn)(k,1,2)=1(f)(k,1,2)max  ( (f)(k,1,2 ) ) . two classification models were used to evaluate the classification performance , after the initial set of genes was reduced to 100 highest - ranked genes . k - nearest neighbors ( k - nn ) is one of the simplest classification algorithms , and is based on the distance metric that measures the distance to the nearest neighbors of a sample that is to be classified . the k - nn classifier is widely used in machine learning and has been applied to bioinformatics problems . with the given test sample of unknown class , this model finds the k nearest neighbors in the training set using euclidean distance ( d ) ,   and assigns the label of the test sample according to the labels of those neighbors . a setting with 5 nearest neighbors was used for the estimation of classification performance in our study . to ensure a majority in the voting process , we used the weighting technique where each vote is weighted by its distance to the test sample . support vector machines ( svms ) can handle very large - scale classification with respect to both the number of samples as well as the number of variables . the first step includes mapping of data vectors to a high - dimensional space , while the second step attempts to find a hyperplane in the newly mapped space with maximum margin separating the classes of data . the simplest example of svm is a hyperplane that separates two classes of examples with maximum margin . the margin is defined by the distance from the hyperplane to the nearest of the data points . our study employed an optimized version of svm called the sequential minimized optimization , proposed by platt , which is implemented in the weka environment . the first group of experiments is based on sampling using different number of samples from the original data . random sampling with replacement leaves the number of samples in a new sampled data set unchanged as it was in the original , owing to some samples being picked more than once . this method of resampling is often called bootstrapping and is used for estimating the properties of an estimator ( such as its stability ) by measuring those properties when sampling from an approximating distribution . similarity measurement for each of the four gene selection methods consisted of the following steps . randomly select n samples from original dataset , with n ranging from 50 to m in steps of 25 until m exceeds number of all patients . each of four gene selection methods is used on each subset to construct k ranked lists of genes ( each of them containing 100 top ranked genes ) . stability s is then measured by averaging over all pairwise comparisons of k ranked gene lists for each gene selection method separately 
										 ( 8)s=2i=1kj = i+1ksim(gi , gj)k(k1 ) , 
									 where gi represents ranked list of genes from subsample k  ( 1 i  k ) ,   and sim(gi , gj ) represents one of three similarity measures (  ,  or  ) used to estimate the stability of two ranked gene lists by calculating similarity between them . figure 1 shows the stability results on the largest data set , comparing 344 breast cancer tissues against 286 colon cancer tissues . similar results were obtained for the three remaining data sets ( see supplemental files in the supplementary material available online on doi:616358 ) . simultaneous comparison of sn and ig as well as relieff and svm - rfe also represents the comparison of two families of gene selection methods , that is , univariate versus multivariate . univariate methods show steady growth of stability , in contrast to the multivariate methods , where stability measures rarely ( relieff ) or never ( svm - rfe ) show any growth when the number of samples gets higher . on comparing the univariate gene selection methods , it is evident that ig produces by far the most stable lists of ranked genes . by directly interpreting the overlap metric , it can be stated that when the number of samples reaches 400 , ig gives more than 80 out of 100 genes in both the lists from the two bootstrapped data sets . on the other hand , svm - rfe is capable of producing only around 20 common genes on an average . it can be observed that all the three similarity metrics that were used in the stability measurements for all of the four gene selection methods showed very similar behavior . weighted overlap metric produced the most optimistic results , followed by classical overlap and spearman metric . the higher values of weighted overlap metric can be explained by the fact that this metric prefers overlap of higher - ranked genes . standard deviation measurements for all the three similarity metrics , as a function of the number of samples , can be obtained in the supplemental materials . from the standard deviation results , it can be observed that relieff is the only method where larger number of samples does not stabilize the similarity measurements . furthermore , the ig again proved to be the most optimal method with the lowest standard deviation values , especially for large number of samples . stability of produced gene lists becomes even more important when ranked gene lists from two different studies are compared . a lot of recent studies include a comparison of breast cancer gene signatures where different lists of genes are usually compared to referential study by van't veer et al . . a paper by ein - dor et al shows that thousands of genes would be needed to achieve an overlap of 50% for breast cancer dataset . to confirm this pessimistic statement , another experimental setup was prepared , where partitioning of initial data set in two independent subsets was employed . the samples were randomly shuffled and equally partitioned into two groups with equal number of samples . again , two univariate gene selection techniques were compared with two multivariate methods , to measure the similarity of the two ranked gene lists produced from each partition of data . the whole procedure was repeated 10 times and the measurements were averaged for each point , shown in figure 2 , representing the number of samples in each group . this experiment demonstrated similar results to the former one , with an even bigger gap between the most- and the least - stable gene selection technique . the relieff showed good performance when compared with sampling experiment , but was still unable to grow steadily and was therefore considered very unstable . the svm - rfe demonstrated very low stability again , while ig managed to cross 50% overlap at somewhere between 50 and 75 samples in each group . by observing the results for sn gene selection , it is evident that more than 300 samples in each group would be needed to reach an overlap of 50% . the final experiment compared the accuracy of the classification rates for ig and svm - rfe - based gene selection methods to test the possible significance of svm - rfe - based gene selection in providing better results than the classification using ig gene selection . each feature selection method was used in combination with two classification models , that is , svm and k - nn . the two measures of accuracy were used to evaluate the classification performance of the four classification combinations . in addition to the classical accuracy estimation ( denoted as acc ) , calculated as the number of correctly classified samples divided by the total number of samples , the area under roc curve , or in short , the area under curve ( auc ) was used . classification performance estimation was carried out using 10-fold cross - validation cycle that was repeated 10 times to ensure higher reliability of the results , especially in cases where a small number of samples were used . to avoid the so - called selection bias that was exposed in earlier studies by ambroise and mclachlan   and simon et al . , gene selection along with classification was carried out exclusively on the training set within the cross - validation procedure . figure 3 presents the results of acc and auc , while figure 4 shows the standard deviation values for different number of samples used in the comparison of breast and colon cancers . it can be observed that acc levels do not vary as much as auc levels when evaluating different combinations of gene selection and classification methods . friedman 's nonparametric test was used for all the four data sets , comparing the performance of the four gene selection and classification combinations to confirm the significance of differences in acc and auc levels . after friedman 's test , which confirmed significant differences between the compared gene selection and classification - model combinations , wilcoxon signed ranks test was carried out . statistical evaluation of pairwise comparisons using wilcoxon signed ranks test showed that in most cases , no significant difference was observed with respect to acc , when compared with k - nn using ig or svm - rfe as the gene selection method . the only significant difference in acc was found in colon - kidney cancer data set , where svm - rfe - supported k - nn classifier significantly outperformed the ig - supported k - nn classifier . there was only one additional significant difference with respect to acc , which was confirmed using wilcoxon test on breast - kidney data set , where ig - supported svm significantly outperformed svm - rfe - supported svm classifier . however , in terms of auc and comparison between ig- and svm - rfe - supported classifiers , no significant differences were observed . on the whole , there were only two cases of significantly different results in 16 pairwise comparisons of acc and auc . the detailed statistical results of the tests described earlier as well as the additional results are available in the supplemental file ( including significant difference in the performance between svm and k - nn , shown in figure 3 ) . all experiments described earlier used a fixed number of 100-top ranked genes to calculate stability metrics . however , changing the number of selected genes can have a significant impact on characteristics of stability performance . in case of 100 selected top genes it may happen that half or even more of them do not have any informative value on some datasets . therefore , another experiment was designed where we observed simple overlap score at different number of selected genes for breast versus colon cancer dataset . partitioning of dataset in two parts of equal number of samples was repeated 500 times that is more than in previous experiments to get even more reliable results . one of the reasons to introduce this kind of experiment was to clarify a very strange behavior of overlap scores for svm - rfe selection method where stability monotonically dropped when the number of samples was getting higher . figure 5 presents the results for two most interesting gene selection techniques  that is , information gain and svm - rfe . in case of information gain one can observe that overlap values rise with the higher number of samples in all cases . on the other hand , svm - rfe demonstrates very interesting pattern where only very small number of selected genes guarantees that stability will improve with higher number of samples , while in cases of larger number of selected genes , the stability drops significantly when the number of available samples increases . this fact hints at very low number of true informative genes in this dataset . based on our results , it can be concluded that the choice of the gene selection method with respect to the aim of the study is very important . in cases that require a reproducible set of genes or single new genes for a specific disease , which still allow good classification performance , one should use  good old  univariate methods . univariate methods can offer much more reproducible and stable gene expression signatures , while multivariate methods present a possibility to discover multiple new gene expression signatures that include interactions of multiple coexpressed genes . however , it is evident that even univariate gene selection methods can perform very differently . in the case of partitioning experiment using ig , it can be observed that 50% overlap is reached with less than 75 samples , while sn ranking fails to reach that level of similarity . in addition to the observation by ein - dor et al . , who stated that thousands of samples are needed to achieve 50% overlap between two ranked lists of genes , it should be noted that the choice of the gene ranking method used is very important . similarity of the ranked gene lists based on svm - rfe gene selection method demonstrates that a target of 50% overlap will hardly ever be reached , even if thousands of samples are employed in a study . an important question to answer at this point is what makes svm - rfe , which has been regarded as one of the most promising gene selection methods in recent years , so unstable . a part of this question was already answered by hardin et al . , who claimed that a linear svm may assign zero weights to strongly relevant variables , with weakly relevant variables getting higher weights . they compared the theoretical foundations of svm - based feature selection with the markov  blanket - based gene selection techniques . in conclusion , they pointed out that gene selection algorithms that routinely miss the strongly relevant features ( like svm - rfe ) do not necessarily affect the classification performance when such algorithms are used in combination with the classification models . efficiency of unstable methods is further supported by simon , who stated that one can find many correlated genes in each microarray study , and hence , it can be assumed that genes selected for inclusion in a classifier will not be stable among different studies . based on the assumptions of earlier studies , it is evident that svm - rfe gene selection method works well on various different subsets of genes from the initial pool of genes . from the results presented in this study , it can be inferred that though a list of approximately 1% of genes used for classification can be very inconsistent , the svm classifier would still be able to obtain very good classification performance using various subsets . this is very useful when we use svm - rfe - supported classifiers exclusively for classification , but can present a serious threat to reproducibility when the classifier is used for biomarker identification . however , our last experiment hints at low number of informative genes , especially in case of svm - rfe gene selection . it could also be said that svm - rfe can be very helpful when searching for a number of true informative genes is our target , but one should be aware that in general svm - rfe still lags behind in terms of stability when compared to univariate selection methods used in this study . as already mentioned in the introductory section of this paper this opens a new question whether gene set stability represents the most appropriate way of measuring the reproducibility of microarray analysis results . there are other ways to estimate the stability of gene sets through functional enrichment of selected gene sets where it is also possible to compare overlap of enriched sets of genes . but on the other hand , we do not really know how many of gene sets used in gene set enrichment methods are true informative genes ( e.g. , in msigdb ) . therefore , it would be interesting to assess the stability of produced gene sets by comparing the overlap of enriched groups of genes from random subsets of the original dataset . this study compared the empirical results of four gene selection methods to calculate the stability of the gene selection lists . three different metrics were used to compare the stability of gene selection methods to show that they mostly produced very similar results . it was observed that in most cases , simple overlap metric can be used for the estimation of gene selection stability . the results presented also show that there is no significant difference in the accuracy between svm - rfe - based gene selection classification and the ig - based gene selection classification . on the other hand , it was demonstrated that in terms of ranked gene lists similarity ig gene selection clearly outperforms svm - rfe that shows the worst performance among compared gene selection methods . our study represents an attempt to empirically estimate the number of needed samples to achieve the desired level of stability . however , only a setting using 100 selected genes has been observed . in the future , with more computational power available , it may be possible to compare the relationships in three dimensions , consisting of the number of genes selected , number of available samples , and stability of the gene lists .
this paper presents an empirical study that aims to explain the relationship between the number of samples and stability of different gene selection techniques for microarray datasets . unlike other similar studies where number of genes in a ranked gene list is variable 
 , this study uses an alternative approach where stability is observed at different number of samples that are used for gene selection . 
 three different metrics of stability , including a novel metric in bioinformatics , were used to estimate the stability of the ranked gene lists . 
 results of this study demonstrate that the univariate selection methods produce significantly more stable ranked gene lists than the multivariate selection methods used in this study . 
 more specifically , thousands of samples are needed for these multivariate selection methods to achieve the same level of stability any given univariate selection method can achieve with only hundreds .