Search tips
Search criteria 


Logo of jbbJournal's HomeManuscript SubmissionAims and ScopeAuthor GuidelinesEditorial BoardHome
J Biomed Biotechnol. 2010; 2010: 726413.
Published online 2010 June 23. doi:  10.1155/2010/726413
PMCID: PMC2896865

Neighborhood Rough Set Reduction-Based Gene Selection and Prioritization for Gene Expression Profile Analysis and Molecular Cancer Classification


Selection of reliable cancer biomarkers is crucial for gene expression profile-based precise diagnosis of cancer type and successful treatment. However, current studies are confronted with overfitting and dimensionality curse in tumor classification and false positives in the identification of cancer biomarkers. Here, we developed a novel gene-ranking method based on neighborhood rough set reduction for molecular cancer classification based on gene expression profile. Comparison with other methods such as PAM, ClaNC, Kruskal-Wallis rank sum test, and Relief-F, our method shows that only few top-ranked genes could achieve higher tumor classification accuracy. Moreover, although the selected genes are not typical of known oncogenes, they are found to play a crucial role in the occurrence of tumor through searching the scientific literature and analyzing protein interaction partners, which may be used as candidate cancer biomarkers.

1. Introduction

DNA microarray technology, a powerful tool in functional genome studies, has yet to be widely accepted for extracting disease-relevant genes, diagnosis, and classification of human tumor [13]. Generally, genes are ranked according to their differential expression by analysis of combination of normal and tumor samples, and genes above a predefined threshold are considered as candidate genes for the cancer being studied [4]. However, this method may produce a vast number of false, positives. In addition to the false-positive problem, the imbalance between the number of samples and genes may potentially degrade the classification accuracy and it can lead to possible overfitting and dimensional curse or even to be a complete failure in the analysis of microarray data [2]. An efficient way to solve these problems is gene selection. In fact, a good gene-selection method that can identify key tumor-related genes is of vital importance for tumor classification and identification of diagnostic and prognostic signatures for predicting therapeutic responses [5, 6].

Identifying minimum gene subsets means discarding most noise and redundancy in dataset to the utmost extent, resulting in not only classification accuracy improvement but also tumor diagnosis cost decrease in clinical application, which is still a key challenge in gene expression profile- (GEP-) based tumor classification. Rough set theory has been successfully used in feature selection [7, 8]. However, it is difficult to directly and effectively deal with real-valued attributes of microarray dataset [9]. Dataset discretization is usually adopted to tackle the problem, but the pretreatment may lose some useful information. To combat this problem, Hu et al. [10] first presented the basic concepts on neighborhood rough set (NRS) model and designed a novel feature selection method called forward attribute reduction based on neighborhood model (FARNeM) to select a minimal reduct, which avoided the preprocess of data discretization and hence decreased the information lost in pretreatment. But the reduct which satisfies criterions of higher classification performance and fewer gene numbers is not unique and full of chance. Obviously, it is not appropriate to use only a gene subset (a reduct) to train classifier, which necessitates it to select numerous minimal gene subsets with the highest or near highest dependence on training set to avoid the selection bias problem. Breadth-First Search (BFS) [11], a basic graph search algorithm that begins at the root node and explores all the neighboring nodes, were adopted to implement our goals for selecting any number of optimal and minimum gene subsets. However, for n nodes, there are 2n combinations of gene subsets in total. It is not practical to search all of the gene subsets in 2n combinations. The computational complexity is too high. To circumvent these problems, we proposed a breadth-first heuristic search algorithm based on neighborhood rough set (HBFSNRS) to select numerous gene subsets. The dependence function of NRS was selected as the heuristic information.

To prioritize the numerous selected genes, a parameter sig was introduced. Previous studies showed that significant class predictor genes whose expression profile vector show remarkable discrimination capability among different class samples of specific cancer maybe play a crucial role in the development of cancer [4]. We hypothesized that the occurrence probability of genes in the final selected gene subsets may reflect the power of tumor classification and the significance of them to some extent. To probe our hypothesis, several publicly available microarray datasets were applied. HBFSNRS method was also compared with four related methods: PAM, ClaNC, Kruskal-Wallis rank sum test (KWRST), and Relief-F to demonstrate its good performance, efficiency, and effectiveness in gene selection, prioritization and cancer classification.

2. Materials and Methods

2.1. The Framework of Our Analysis Method

Our proposed method is different from the traditional gene selection strategies: Filters and Wrappers. The Filter methods are based mostly on selecting genes using between-class separability criterion [12], and they do not use feedback information from predictor performance in the process of gene selection, such as relative entropy, information gain, KWRST, and t-test. The wrapper methods select genes by using a predictor performance as a criterion of gene subset selection such as GA/SVM [13] and GA/KNN [14]. Our method is a combination of Filter and Wrapper methods. A novel HBFSNRS-based cancer classification framework is illustrated as Figure 1. Four major steps of the designed method are described as follows.

Figure 1
The framework of our analysis method. (a) An ensemble classifier was constructed on the basis of the selected genes subsets by HBFSNRS with a specific threshold value δ. (b) Another ensemble classifier was constructed based on classification results ...

2.2. Gene Pre-Selection Based on KWRST

All of the microarray datasets, without respect to training and test dataset, were normalized per gene by subtracting the minimum expression measurements and dividing by the difference between the maximal and minimum values of that gene. The expression levels for each gene were scaled on [0,  1].

Gene preselection can improve the classification performances since it may reduce the noise, which is also the common procedure for most classification application [15]. We applied gene preselection on training dataset to reduce the noise. All of the genes on the arrays of training data were sorted according to KWRST which is suitable for multiclass problem. In this study, the p top ranking genes (the initial informative gene set G*) were used for finding minimum gene subsets for constructing ensemble tumor classifier with HBFSNRS. Generally speaking, more than 1% of genes in the human genome are involved in oncogenesis [16], so we set the number of the selected top-ranked gene p = 300.

2.3. Neighborhood Rough Set Reduction

The basic concepts of neighborhood rough set (NRS) have been introduced by Hu et al. [10]. In our proposed algorithm, the dependence function of NRS was introduced to evaluate the goodness of selected gene subsets. Here, we presented only the basic notation from NRS approach used in the paper.

Assume there are c subclasses of cancers, let D = {d1, d2,…, dm} denotes the class labels of m samples, where di = k indicates the sample i being cancer k, where k = 1, 2,…, c. Let S = {s1, s2,…sm} be a set of samples and G* = {g1, g2,…, gn} be a set of genes, the corresponding gene expression matrix can be represented as X = (xij)m×n, where xij is the expression level of gene gi in sample sj, i = 1, 2,…, n, j = 1, 2,…, m, and usually n [dbl greater-than sign] m.

Given an information system for classification learning

NDT = left angle bracketS, G* [union or logical sum] D, V, fright angle bracket, where S is a nonempty sample set called sample space, G* is a nonempty set of genes also called condition attributes to characterize the samples, D is a set of output variable called decision attribute (class labels of tumor samples), Va is a value domain of attribute a [set membership] G* [union or logical sum] D, f is an information function f : S × (G* [union or logical sum] D) → V, V = [union or logical sum]a[set membership]G*[union or logical sum]D  Va, a reduction is a minimal set of attributes B[subset, dbl equals]G*.

Given for all si [set membership] S and B[subset, dbl equals]G*, the neighborhood δB(si) of si in the subspace B is defined as


where δ is the threshold and ΔB(si, sj) is the metric function in subspace B. There are three common metric functions that are widely used. Let s1 and s2 be two samples in n-dimensional space G* = {g1, g2,…, gn}. f(s, gi) denotes the value xis of gi in the sample s. Then Minkowsky distance is defined as


where (1) if p = 1, it is called Manhattan distance Δ1; (2) if p = 2, it is called Euclidean distance Δ2; (3) if p = , it is called Chebychev distance. Here, we use the Manhattan distance.

Given a neighborhood decision table NDT, X1, X2,…, Xc are the sample subsets with decisions 1 to c, δB(xi) is the neighborhood information granules including xi, and is generated by gene subset B [subset or is implied by] G*, then the lower and upper approximations of the decision D with respect to gene subset B are, respectively, defined as


where LowerB(X) = {xi | δB(xi)[subset, dbl equals]X, xi [set membership] S} is the lower approximations of the sample subset X with respect to gene subset B, and is also called positive region denoted by PosB(D) which is the sample set that can be classified into one of the classes without uncertainty with the gene subset B. UpperB(X) = {xi | δB(xi)∩Xϕ, xi [set membership] S} denotes the upper approximations, obviously UpperB(X) = S. The decision boundary region of D to B is defined as


The neighborhood model divides the samples into two groups: positive region and boundary region. The decision boundary is the sample set with neighborhoods from more than one class. Through these neighborhood information, we cannot completely be sure that these samples can be classified into the class. The samples in different gene subset subspaces will have different boundary regions and positive regions. The size of the boundary region reflects the discriminability of the classification problem in the corresponding subspaces. It also reflects the recognition power or characterizing power of the condition attributes. The greater the positive region is, the smaller the boundary region will be, and the stronger the characterizing power of the condition attributes will be. So we use the dependency degree of D to B to characterize the power of the selected gene subsets, which is defined as the ratio of consistent objects


where Card(S) and Card(PosB(D)) denotes the cardinal number of sample set S and PosB(D), respectively. If γB(D) = 1 we say that D depends totally on B, and if γB(D) < 1, we say that D depends partially. Here we define γ[empty](D) = 0, and our goal is to find the gene subset B which γB(D) is equal to the set value.

2.4. Gene Reduction Based on HBFSNRS

Informative gene selection involves evaluating the quality of the selected gene subsets and searching for good gene subsets quickly. Here, the dependence function of NRS is used to measure the goodness of the selected gene subset. Here, the computational cost problem is addressed as below.

Initially, let RED = {{g1}, {g2},…, {gp}} be a set of gene subsets where each subset only has an informative gene. Then, for ∀  redi [set membership] RED, redi = {gi} is expanded to (p − 1) subsets by adding a different genes {gl | gl [set membership] G*, gl [negated set membership] redi} into each redi, where we set temporyi = {{gig1},…, {gigi−1}, {gigi+1},…, {gigp}}, we will get p*(p − 1) subsets in total. Among these subsets, we select the ω top-ranked gene subsets by the dependence function that need to be expanded in the next iteration to reconstruct the set RED, and now each element of RED has 2 genes. Similarly, in the next search layer, for ∀  redx [set membership] RED, redx = {gigj} is extended to (p − 2) subsets excluding the genes have listed in the redx, where we set temporyx = {{gigjg1},…, {gigjgi−1}, {gigjgi+1},…, {gigjgj−1}, {gigjgj+1},…, {gigj    gp}}, i < j, and we will get w*(p − 2) subsets. Among these subsets, ω top-ranked gene subsets were selected to be expanded in next layer as the above method. Now, the element of RED has 3 genes. The search process continues following the above method until meeting the stop criteria. In each layer, we expend to w*(p − card(red)) subsets and only ω top-ranked gene subsets were selected to reconstruct the set RED from the total subsets, so that the search time will not increase exponentially with the increase of search depth. Here, card(red) denotes the cardinal gene number of the gene subset. In the virtue of the minimum construction idea, one of the techniques for the best feature selection could be based on choosing minimal gene subsets that fully describe classes of tumor classification in a given data set. Therefore, when the maximal dependence of the elements of RED (e.g., r_Max = 0.9999) is obtained, the increment between the maximal dependence of two adjacent search levels is less than θ (e.g., θ = 0.0001) or the number of iterative steps is equal to the set value Depth (e.g., Depth = 20), the searching process ends at that level. Otherwise, we continue to search genes in this way until meeting the stopping criterions. The pseudocode of HBFSNRS is shown in Algorithm 1.

Algorithm 1
A heuristic breadth-first search algorithm based on neighborhood rough set (HBFSNRS).

The dependence function of NRS is chosen as the objective function for evaluating the goodness of the selected gene subset mainly because it is computationally fast in that it does not use the feedback information of test data in the training process. To optimize the parameter δ in NRS that control the size of the neighborhood, different values for δ from 0 to 1 with step 0.01 were tested by running forward attribute reduction based on neighborhood model (FARNeM). δ values were sorted according to the classification accuracy by 3-KNN classifier using the corresponding gene subset selected by FARNeM. The 5 top-ranked δ values were used in the next step. But for ALL (a multiclass dataset), the gene number of the selected minimal and optimal reduct set reach 20 or even more for some of the top five δ values. Considering that a large gene subset with an excessive number of genes may contain much noise and redundancy, which may bias and negatively influence the tumor classification and gene prioritization, we discarded such top-ranked δ values and reselected five top-ranked δ values that produced reduct set with less than 20 genes.

2.5. Evaluation Criterion for the Selected Gene Subsets

We adopted 3-KNN classifier to evaluate the classification performance of the selected gene subsets. To improve prediction accuracy and stability, an ensemble classifier was constructed on the basis of the selected gene subset. For each δ, a simple majority voting strategy was applied to integrate the w individual classifier that is constructed from the selected gene subsets obtained by HBFSNRS only on training set. Then, another ensemble classifier was built based on the above classification results with each δ value in the similar way.

Here, we hypothesized that genes with higher occurrence frequency are more likely to be important and cancer-related genes. Therefore, we count the occurrence frequency of each gene in all the selected gene subsets to measure its significance. But for a specific cancer, different δ value may select different sizes of the minimum gene subset. In this case, only counting the occurrence frequency is not appropriate for measuring the significance of genes. To avoid the selection bias, the significance of genes is measured by occurrence of probability, which is defined as


where fij is the occurrence frequency of gene j in all the gene subsets which are selected by HBFSNRS with δi; t is the total number of neighborhood values (we set t = 5 ); ni is the number of genes in a selected gene subset with δi; ω is the number of the final selected gene subsets by HBFSNRS (we set ω = 500).

In order to further investigate the significance of the selected gene, two main methods were used: (1) the selected genes were regarded as predictor set or classification model; (2) literature search and protein-protein interaction (PPI) network analysis.

2.6. Dataset

To evaluate the performance of the proposed method, seven gene expression datasets were used in this study: Acute Lymphoblastic Leukemia (ALL) [17], Breast cancer 30 (GSE5764) [18], Breast cancer 22(GSE8977) [18], Colon cancer [19], Prostate cancer 102 [20], and Prostate cancer 34 [21]. The two pairs of cross-platform datasets were used to evaluate the generalization performance for our cross-platform classification model. Datasets of Breast cancer, Colon cancer, and Prostate cancer are two-class classification systems that contain normal and tumor samples. ALL dataset is a multiple-class classification system. The dataset contains six subtypes of ALL: BCR-ABL, E2A-PBX1, Hyperdip>50, MLL, T-ALL, TEL-AML1. For Breast-cancer datasets, there are too many (54675) affymetrix probe identifiers, therefore the raw data were processed following these steps: affymetrix probe identifier was converted to entrez identifier. When multiple probes corresponded to the same entrez ID, we averaged over these probe intensities. The division of training set and test set is shown in Table 1.

Table 1
The division of training set and test set in our experiments.

3. Results

3.1. Redundant and Irrelevant Genes Potentially Degrade the Classification Accuracy

To avoid overfitting problem and improve classification accuracy and stability, an ensemble classifier was constructed on the basis of the selected gene subsets. We observed that the final integrated results (Table 2) were not satisfactory and no higher classification accuracy obtained compared to some individual classifiers. The main reason may be that our methods used all the selected gene subsets as classification model, which contain many redundant and tumor-unrelated genes and may potentially degrade the classification performance. Figure 2 shows the classification accuracy with different numbers of the top-ranked genes sorted according to the significance of genes defined as (6), from which we found that only a few top-ranked genes were enough to obtain higher classification accuracy. Meanwhile, when more genes were used as predictor set, there was only a little increase or even decrease in the classification performance. Therefore, we inferred that too many selected genes involve much more redundancy and irrelevancy, which degrades the classification accuracy.

Figure 2
Comparison of classification accuracy with different numbers of top-ranked genes on the four test datasets by HBFSNRS, Relif-F, and KWRST.
Table 2
Classification accuracy, sensitivity and specificity on all the test datasets by the ensemble classifier.

3.2. Comparison with Other Related Methods

In order to elaborate the effectiveness of HBFSNRS, we compared the accuracy of our approach with other common filter methods including t-test, information gain, KWRST, and Relief-F. The experimental results indicate that our method is significantly superior to t-test and information gain, and slightly outperforms KWRST and Relief-F in the aspect of tumor classification. For simplicity, we only present KWRST and Relief-F results here (Figure 2). We found that only a few top-ranked genes could achieve higher accuracy in the classification of tumor samples of different classes by our proposed search algorithm. For ALL dataset, the prediction accuracy by HBFSNRS is superior to other methods regardless of the much fewer genes used in cancer classification. For breast-cancer dataset, using one active gene could test outcome with the accuracy of 22.73% by Relief-F, 63.64% by KWRST, whereas 100% test accuracy was obtained using one gene by the proposed HBFSNRS method. For colon-cancer dataset, using one, six active genes could get the prediction accuracy of 80% and 85% by our method, 65%, 70% by Relief-F, and 65%, 75% by KWRST, respectively. For prostate-cancer dataset, when using more than ten genes for tumor classification, KWRST significantly outperformed our method and Relief-F, but our method performs as well as the KWRST when only using the few top-ranked genes (both of our method and KWRST could get 97.06% accuracy using one gene). What is more, we compared our method with other statistical methods PAM and ClaNC. PAM, a statistical technique for class prediction from gene expression data that uses nearest shrunken centroids, was used to identify class predictor genes [22]. ClaNC ranks genes by standard t-statistics, which does not shrink centroids and uses a class-specific gene selection procedure [23]. In our context, ClaNC slightly outperformed PAM, so we only present the comparison with ClaNC here (Table 3). In comparison with ClaNC, our method could obtain higher classification accuracy when using a few top-ranked genes. The one-gene model by our method provides the classification accuracy of 100%, 80%, and 97.06% for Breast-cancer, Colon-cancer, and Prostate-cancer dataset, respectively, whereas ClaNC requires more genes to get the same accuracy. In ALL dataset, the test accuracies on independent test dataset are 87% with six genes, 94% with 12 genes, and 97% with 18 genes by our method. Using the same six, 12, 18 active genes could test outcome with the accuracy of 86%, 95%, and 97% by ClaNC, respectively, which indicates our method was comparable for ALL dataset. As a comparison, the minimum genes with the highest accuracy can be obtained in the classification process by HBFSNRS. In addition, results show that our method is obviously better than ClaNC in colon-cancer and breast-cancer cross-platform datasets. It is likely that ClaNC is not suitable for cross-platform datasets. We proposed that these few genes whose expression profile vector showed remarkable discrimination capability may closely correlated to cancer and could be seen as possible disease signatures.

Table 3
The comparison with the ClaNC method in classification accuracy.

3.3. Analysis of the Top-Ranked Genes (Case Studies)

Mining genes that give rise to ontogenesis is one of key challenges in the area of cancer research. Biologically the experimental results proved that the selected genes with high classification accuracy are functionally related to carcinogenesis or tumor histogenesis, so we could infer that the few top-ranked genes may be very important for tumor diagnosis. The 10 top-ranked genes according to the sig score for each tumor that were regarded as the candidate cancer genes listed in Table 4. To demonstrate our method's ability in uncovering known cancer genes and predicting novel cancer biomarkers, the breast-cancer dataset was employed to this study as the method of [24].

Table 4
The 10 top-ranked genes selected for the four datasets.

First, we checked whether our method can uncover known famous cancer genes. We downloaded a list of 25 breast cancer biomarkers that have been annotated in the OMIM database [25]. Unfortunately, our used dataset (the 300 top-ranked genes selected by KWRST) does not include the 25 known breast cancer genes. Therefore our method cannot be evaluated with it in terms of uncovering known cancer genes. From another point of view, it is verified that higher differential expression of a gene does not necessarily reflect a greater likelihood of the gene being related to cancer. In other words, important genes might not be necessarily differentially expressed. But it is undeniable that higher differential expressions of genes are inevitably important in the cancer diagnosis and development.

Next, literature search method was used to check whether our method can predict novel cancer biomarkers. In the top 10 genes ranked by (6) for breast cancer, we found that these genes play an important role in the occurrence of breast cancer. The collagen triple helix repeat containing 1 (CTHRC1), ranked the first, whose aberrant expression is widely presented in human solid cancers including breast cancer and seems to be associated with cancer tissue invasion and metastasis [26]. The PDZ and LIM domain protein 4 (PDLIM4), ranked the second, was frequently methylated in breast cancers but not in normal breast tissues [27]. The keratin, type I cytoskeletal 17 (KRT17), ranked the third, was specifically overexpressed in basal-like subtypes of breast cancer [28]. The secreted frizzled-related protein 1 (SFRP1), ranked the fourth, was recently found to be associated with progression and poor prognosis in early stage of breast cancer [29]. The collagen alpha-1 (III) chain (COL3A1), ranked the fifth, was up-regulated in both invasive ductal and lobular carcinomas cells when compared with normal ductal and lobular cells [30]. The peptidase inhibitor 15 (PI15), ranked the sixth, was also differentially expressed but it was down regulated in lobular and ductal invasive breast carcinomas [30]. The actin gamma-enteric smooth muscle (ACTG2), ranked the seventh, is involved in the architecture and remodeling of cytoskeleton in basal medullary breast cancer [31]. The tissue factor pathway inhibitor 2 (TFPI2), ranked the eighth, whose aberrant hypermethylation with gene promoter was associated with metastasis in breast cancer [32]. The serpin B5 (SERPINB5), ranked the ninth, an epithelial-specific serine protease inhibitor, was a biomarker in disseminated breast-cancer cells [33].The fibronectin 1 (FN1), ranked the tenth, was recently suggested to be associated with the prognosis of patients with breast cancers [34].

Finally, we examined gene pathway that involved by the 10 top-ranked genes. The study is carried out using the software which can help the researchers to better understand the biological phenomenon understudied by pointing out significant cellular functions of the selected genes from the webpage “” [35]. Results indicate that the pathways that the 10 top-ranked genes are involved in are ECM-receptor interaction (COL3A1, FN1), focal adhesion (COL3A1, FN1), vibrio cholerae infection (ACTG2), p53 signaling pathway (SERPINB5), Small cell lung cancer (FN1), wnt signaling pathway (SFRP1), regulation of actin cytoskeleton (FN1), pathways in cancer (FN1), which agree well with current knowledge on breast cancer [36]. Thus it can be seen that the selected genes that closely related to adhesion, motility, and metastasis may provide new insights in the underlying molecular mechanisms related to disease development, in designing therapy and in prognostication for patients with breast carcinoma. Thus, the analysis of existing biological experiment results of breast-cancer dataset well illustrates that our method has great power of identifying tumor-related genes.

Furthermore, another case study for prostate-cancer dataset was presented here. In the 10 top-ranked genes, six of them (HPN, MAF, GSTP1, WWC1, JUNB, and RND3) have been reported to be associated with prostate cancer. The hepsin (HPN), ranked the first, a cell surface serine protease that is markedly up-regulated in human prostate cancer, which is overexpression in prostate epithelium in vivo causes disorganization of the basement membrane and promotes primary prostate cancer progression and metastasis to liver, lung, and bone [37]. The transcription factor (MAF), ranked the second, was down-regulated in the tumors relative to normal prostate tissue and may be regarded as the candidate tumor suppressor gene [38]. The glutathione s-transferase P (GSTP1), ranked the fourth, whose CpG island hypermethylation is the most common somatic genome alteration described for human prostate cancer [39]. The gene WWC1, ranked the sixth, was found to interact with histone H3 via its glutamic acid-rich region and that such interaction might play a mechanistic role in conferring an optimal ER transactivation function as well as the proliferation of ligand-stimulated breast-cancer cells [40]. The transcription factor jun-B (JUNB), ranked the seventh, is an essential upstream regulator of p16 and contributes to maintain cell senescence that blocks malignant transformation of TAC. JUNB thus apparently plays an important role in controlling prostate carcinogenesis and may be a new target for cancer prevention and therapy [41]. The Rho-related GTP-binding protein RhoE (RND3), ranked the ninth, a recently described novel member of the Rho GTPases family, was regarded as a possible antagonist of the RhoA protein that stimulates cell cycle progression and is overexpressed in prostate cancer [42]. The remaining genes were not identified to correlate to prostate cancer previously. These genes need further analysis.

Genes related to a specific or similar disease phenotype tend to be located in a specific neighborhood in the protein-protein interaction network, and a protein is likely to be coexpressed with its interaction partners and those proteins that have similar function. Here, we applied a protein-network-based method to analyze the effect of neighborhood partners on the selected genes using all interactions in the Human Protein Reference Database [43]. Figure 3 indicates the protein-interaction network for each top-ranked gene of prostate cancer (KIAA0430 has no interaction partners in HPRD). The red-ellipse nodes represent the 10 top-ranked genes that were ranked by the sig score in (6), among which, those with an asteroid sign means known cancer genes. The diamond nodes indicate the direct interaction partners of the selected genes that were not cancer genes, and blue-octagon nodes show those partners that are identified as known cancer genes which were collected by querying the Memorial Sloan Kettering computational biology website, “Oncogene”, “tumor suppressor”, and “stability” are shown as [4, 44]. Among the 10 top-ranked genes for prostate-cancer dataset (Figure 3), 6 genes (ABL1, JUNB, MAP, P4HB, GSTP1, and RND3) that listed with an asteroid sign have been identified to be known cancer genes. Here, we mainly illustrate the three genes P4HB, PEX3, and ABL1 that we did not find reports on their association with prostate cancer. In the three genes, P4HB and ABL1 have been known as cancer genes. PEX3 is also a famous disease gene which was the cause of peroxisome biogenesis disorder, complementation group 12, and zellweger syndrome. It can be seen that mutation in these genes can lead to many diseases and may have a close relationship with prostate cancer. In this sense, our method is effective on cancer-related gene selection. Recently, Aragues et al. [4] suggest that cancer linker degree (CLD) of a protein which was defined as the number of cancer genes to which a gene is connected is a good indicator of the probability of being a cancer gene. We analyzed the cancer linker degree (CLD) of 10 top-ranked genes on each of the four datasets. For prostate cancer, as is shown in Figure 4, most of the top-ranked genes have a direct interaction with known cancer genes excluding the gene PEX3, and the CLD of ABL1, JUNB, WWC1, MAF, P4HB, GSTP1, HPN, and RND3 is 46, 13, 2, 6, 7, 1, 1, and 1, respectively. In the 10 top-ranked genes of ALL (TCFL5 and LRMP have no interaction partners in HPRD), SMARCA4, DNTT, and NONO are known cancer genes, and the CLD of SMARCA4, DNTT, NONO, CD72, MPP1, and CD99 is 19, 3, 6, 1, 2, and 2, respectively. For breast cancer, CTHRC1, PI15, and SERPINB5 have no interaction partners in HPRD. In the remaining 7 genes of 10 top-ranked genes, SFRP1 and TFPI2 are known cancer genes, and SFRP1, TFPI2, FN1, COL3A1, and KRT17 have a direct interaction with known cancer genes, the CLD of which is 2, 1, 17, 2, and 1 respectively. For colon cancer, FUCA1 has no interaction partners in HPRD. In the remaining 9 genes, MYH9 is a known cancer gene, the CLD of DES, MYH9, C3, and 2-Sep is 4, 3, 1, and 1, respectively. These results show that besides a few selected genes that typically correspond to known specific cancer mutations, a considerable portion of the top-ranked genes have many direct interactions with cancer genes, which suggests that these genes should be very likely to be involved in cancer and may play a central role in the protein network by interconnecting many known cancer genes, and thus the top ranked genes can be regarded as reliable disease biomarkers.

Figure 3
The protein-interaction network associated with the ten top-ranked genes for prostate cancer.

4. Discussions and Conclusions

4.1. Better Performance on Tumor Classification and Gene Selection and Prioritization

An ongoing challenge is to identify new prognostic markers that are directly related to disease and that can more accurately predict the likelihood of gaining cancer in unknown samples. Results indicate that our proposed method of gene selection by HBFSNRS has the following advantages in trying to tack this challenge. (1) Our method could obtain the highest or near highest prediction accuracy of tumor classification with the minimum gene subset. (2) Lists of ranked potential candidate cancer biomarkers with a specific cancer are presented by our approach. (3) Our proposed method can obtain many optimal gene subsets in a short period of time, which is essential to the whole search process. (4) Compared to other gene ranking methods KWRST and Relief-F, our method is relatively stable and contains little chance factors. The success of our methods, gene selection by HBFSNRS, can be attributed to a combination of several aspects. First, we adopted the dependence function of NRS to evaluate the goodness of selected gene subsets. There are two main advantages for this point: time saving and tumor classification without the feedback and leaked information of the test dataset. Second and more importantly, the designed process of gene search by our method can select any number of optimal gene subsets in a comparatively short time, which is an optimization of best-first search. Finally, considering the selection of δ value in the evaluation of gene subsets has the problem that the genes with different δ value will have different ranked positions or relevance to cancer. To avoid this problem of selection bias, we defined a sig score to describe the significance of genes by combining five groups of results that obtained by each δ value. We presented two case studies on breast cancer and prostate cancer to illustrate the power of our method to identify tumor-related genes. Our method illustrates well its high power of tumor classification and gene prioritization.

4.2. Limitation and Extension

One limitation of our approach is in data quality: current high-throughput technologies remain error prone and may be far from complete. In a recent paper, Zhang et al. [45] held that the integration of microarray data gives us more analytical power and reduces the false discovery rate. Given a specific cancer, efficient ways to integrate multiple independent microarray data may be a good way to solve the issue of data quality. The other limitation is the optimization of the threshold value of neighborhood rough set. On one hand, we tried the neighborhood rough set reduction method to evaluate the goodness of the selected gene subsets to save time in tumor classification without using the feedback information of the test dataset. On the other hand, the threshold selection is obtained through the feedback information of the test set. In addition, different δ values may select different gene subsets, hence the genes with different δ value will have different positions in gene prioritization, so the selection of δ has become more critical for gene prioritization. Fortunately, the choice of δ is not so important for gene ranking because the change of gene position in different δ values is not significant. In our study, Spearman's rank correlation coefficient was used to determine whether there is a consistency between the results of gene prioritization with different δ values. Results indicate that there is high consistency among these results.

4.3. Future Work

Our proposed HBFSNRS method has improved the performance of tumor classification based on microarray and identified and prioritized lists of potential tumor-related genes from GEP, our future work will benefit further from integrating other sources. Recent high-throughput technologies have produced vast amounts of protein-protein interactions, which represent valuable resources for candidate-gene prioritization and give us new insights into the mechanism of disease. A great number of studies have shown that integration of multiple sources of data is more reliable for predicting cancer genes than the use of a single criterion [4, 4648]. Thus, it is an efficient method to integrate GEP and protein interaction network for gene prioritization. Although gene expression data and protein interaction data have been integrated for gene prioritization [49, 50], the results are not satisfactory. Therefore, it is still a challenging problem in the area of cancer research.


This work was supported by the grants of the National Science Foundation of China, Nos. 60905023, 30900321, 60973153, 60873012 & 60805021, the grant from the National Basic Research Program of China (973 Program), No. 2007CB311002, the grant of the Guide Project of Innovative Base of Chinese Academy of Sciences (CAS), No. KSCX1-YW-R-30, the Knowledge Innovation Program of the Chinese Academy of Sciences (0823A16121), and the China Postdoctoral Science Foundation (Grant no. 20090450825).


1. Zheng C-H, Huang D-S, Kong X-Z, Zhao X-M. Gene expression data classification using consensus independent component analysis. Genomics, Proteomics and Bioinformatics. 2008;6(2):74–82. [PubMed]
2. Shen Q, Shi W-M, Kong W. New gene selection method for multiclass tumor classification by class centroid. Journal of Biomedical Informatics. 2009;42(1):3–9. [PubMed]
3. Wang H-Q, Wong H-S, Huang D-S, Shu J. Extracting gene regulation information for cancer classification. Pattern Recognition. 2007;40(12):3379–3392.
4. Aragues R, Sander C, Oliva B. Predicting cancer involvement of genes from heterogeneous data. BMC Bioinformatics. 2008;9:p. 172. [PMC free article] [PubMed]
5. Wang H-Q, Huang D-S. Regulation probability method for gene selection. Pattern Recognition Letters. 2006;27(2):116–122.
6. Zheng C-H, Huang D-S, Shang L. Feature selection in independent component subspace for microarray data classification. Neurocomputing. 2006;69(16–18):2407–2410.
7. Pawlak Z. Rough set approach to knowledge-based decision support. European Journal of Operational Research. 1997;99(1):48–57.
8. Wang S-L, Li X, Zhang S, Gui J, Huang D-S. Tumor classification by combining PNN classifier ensemble with neighborhood rough set based gene reduction. Computers in Biology and Medicine. 2010;40(2):179–189. [PubMed]
9. Jensen R, Shen Q. Fuzzy-rough data reduction with ant colony optimization. Fuzzy Sets and Systems. 2005;149(1):5–20.
10. Hu Q, Yu D, Xie Z. Neighborhood classifiers. Expert Systems with Applications. 2008;34(2):866–876.
11. Mehlhorn K, Meyer U. External-memory breadth-first search with sublinear I/O. In: Proceedings of the 10th Annual European Symposium on Algorithms, vol. 2461; 2002; pp. 723–735. Lecture Notes in Computer Science.
12. Duda RO, Hart PE. Pattern Recognition and Scene Analysis. New York, NY, USA: Wiley; 1973.
13. Liu JJ, Cutler G, Li W, et al. Multiclass cancer classification and biomarker discovery using GA-based algorithms. Bioinformatics. 2005;21(11):2691–2697. [PubMed]
14. Li L, Darden TA, Weinberg CR, Levine AJ, Pedersen LG. Gene assessment and sample classification for gene expression data using a genetic algorithm/k-nearest neighbor method. Combinatorial Chemistry and High Throughput Screening. 2001;4(8):727–739. [PubMed]
15. Huang D-S, Zheng C-H. Independent component analysis-based penalized discriminant method for tumor classification using gene expression data. Bioinformatics. 2006;22(15):1855–1862. [PubMed]
16. Futreal PA, Coin L, Marshall M, et al. A census of human cancer genes. Nature Reviews Cancer. 2004;4(3):177–183. [PMC free article] [PubMed]
17. Yeoh E-J, Ross ME, Shurtleff SA, et al. Classification, subtype discovery, and prediction of outcome in pediatric acute lymphoblastic leukemia by gene expression profiling. Cancer Cell. 2002;1(2):133–143. [PubMed]
18. Edgar R, Domrachev M, Lash AE. Gene Expression Omnibus: NCBI gene expression and hybridization array data repository. Nucleic Acids Research. 2002;30(1):207–210. [PMC free article] [PubMed]
19. Alon U, Barka N, Notterman DA, et al. Broad patterns of gene expression revealed by clustering analysis of tumor and normal colon tissues probed by oligonucleotide arrays. Proceedings of the National Academy of Sciences of the United States of America. 1999;96(12):6745–6750. [PubMed]
20. Furusato B, Gao C-L, Ravindranath L, et al. Mapping of TMPRSS2-ERG fusions in the context of multi-focal prostate cancer. Modern Pathology. 2008;21(2):65–75. [PubMed]
21. Welsh JB, Sapinoso LM, Su AI, et al. Analysis of gene expression identifies candidate markers and pharmacological targets in prostate cancer. Cancer Research. 2001;61(16):5974–5978. [PubMed]
22. Tibshirani R, Hastie T, Narasimhan B, Chu G. Diagnosis of multiple cancer types by shrunken centroids of gene expression. Proceedings of the National Academy of Sciences of the United States of America. 2002;99(10):6567–6572. [PubMed]
23. Dabney AR. Classification of microarrays to nearest centroids. Bioinformatics. 2005;21(22):4148–4154. [PubMed]
24. Wu X, Jiang R, Zhang MQ, Li S. Network-based global inference of human disease genes. Molecular Systems Biology. 2008;4(189) [PMC free article] [PubMed]
25. McKusick VA. Mendelian inheritance in man and its online version, OMIM. American Journal of Human Genetics. 2007;80(4):588–604. [PubMed]
26. Tang L, Dai DL, Su M, Martinka M, Li G, Zhou Y. Aberrant expression of collagen triple helix repeat containing 1 in human solid cancers. Clinical Cancer Research. 2006;12(12):3716–3722. [PubMed]
27. Feng W, Shen L, Wen S, et al. Correlation between CpG methylation profiles and hormone receptor status in breast cancers. Breast Cancer Research. 2007;9(4):R57–R69. [PMC free article] [PubMed]
28. Sørlie T, Wang Y, Xiao C, et al. Distinct molecular mechanisms underlying clinically relevant subtypes of breast cancer: gene expression analyses across three different platforms. BMC Genomics. 2006;7, article 127 [PMC free article] [PubMed]
29. Klopocki E, Kristiansen G, Wild PJ, et al. Loss of SFRP1 is associated with breast cancer progression and poor prognosis in early stage tumors. International Journal of Oncology. 2004;25(3):641–649. [PubMed]
30. Turashvili G, Bouchal J, Baumforth K, et al. Novel markers for differentiation of lobular and ductal invasive breast carcinomas by laser microdissection and microarray analysis. BMC Cancer. 2007;7, article 55 [PMC free article] [PubMed]
31. Bertucci F, Finetti P, Cervera N, et al. Gene expression profiling shows medullary breast cancer is a subgroup of basal breast cancers. Cancer Research. 2006;66(9):4636–4644. [PubMed]
32. Rodenhiser DI. Epigenetic contributions to cancer metastasis. Clinical and Experimental Metastasis. 2009;26(1):5–18. [PubMed]
33. Lacroix M. Significance, detection and markers of disseminated breast cancer cells. Endocrine-Related Cancer. 2006;13(4):1033–1067. [PubMed]
34. Helleman J, Jansen MPHM, Ruigrok-Ritstier K, et al. Association of an extracellular matrix gene cluster with breast cancer prognosis and endocrine therapy response. Clinical Cancer Research. 2008;14(17):5555–5564. [PubMed]
35. Khatri P, Sellamuthu S, Malhotra P, Amin K, Done A, Draghici S. Recent additions and improvements to the Onto-Tools. Nucleic Acids Research. 2005;33(2):W762–W765. [PMC free article] [PubMed]
36. Konstantinovsky S, Smith Y, Zilber S, et al. Breast carcinoma cells in primary tumors and effusions have different gene array profiles. Journal of Oncology. 2010;2010 [PMC free article] [PubMed]
37. Klezovitch O, Chevillet J, Mirosevich J, Roberts RL, Matusik RJ, Vasioukhin V. Hepsin promotes prostate cancer progression and metastasis. Cancer Cell. 2004;6(2):185–195. [PubMed]
38. Vivienne Watson JE, Doggett NA, Albertson DG, et al. Integration of high-resolution array comparative genomic hybridization analysis of chromosome 16q with expression array data refines common regions of loss at 16q23-qter and identifies underlying candidate tumor suppressor genes in prostate cancer. Oncogene. 2004;23(19):3487–3494. [PubMed]
39. Lin X, Tascilar M, Lee W-H, et al. GSTP1 CpG island hypermethylation is responsible for the absence of GSTP1 expression in human prostate cancer cells. American Journal of Pathology. 2001;159(5):1815–1826. [PubMed]
40. Rayala SK, Den Hollander P, Manavathi B, et al. Essential role of KIBRA in co-activator function of dynein light chain 1 in mammalian cells. Journal of Biological Chemistry. 2006;281(28):19092–19099. [PubMed]
41. Konishi N, Shimada K, Nakamura M, et al. Function of JunB in transient amplifying cell senescence and progression of human prostate cancer. Clinical Cancer Research. 2008;14(14):4408–4416. [PubMed]
42. Bektic J, Pfeil K, Berger AP, et al. Small G-protein RhoE is underexpressed in prostate cancer and induces cell cycle arrest and apoptosis. Prostate. 2005;64(4):332–340. [PubMed]
43. Peri S, Navarro JD, Kristiansen TZ, et al. Human protein reference database as a discovery resource for proteomics. Nucleic Acids Research. 2004;32:D497–D501. [PMC free article] [PubMed]
45. Zhang Z, Chen D, Fenstermacher DA. Integrated analysis of independent gene expression microarray datasets improves the predictability of breast cancer outcome. BMC Genomics. 2007;8, article 331 [PMC free article] [PubMed]
46. Ortutay C, Vihinen M. Identification of candidate disease genes by integrating gene ontologies and protein-interaction networks: case study of primary immunodeficiencies. Nucleic Acids Research. 2009;37(2):622–628. [PMC free article] [PubMed]
47. Radivojac P, Peng K, Clark WT, et al. An integrated approach to inferring gene-disease associations in humans. Proteins. 2005;72(3):1030–1037. [PMC free article] [PubMed]
48. Aerts S, Lambrechts D, Maity S, et al. Gene prioritization through genomic data fusion. Nature Biotechnology. 2006;24(5):537–544. [PubMed]
49. Ma X, Lee H, Wang L, Sun F. CGI: a new approach for prioritizing genes by combining gene expression and protein-protein interaction data. Bioinformatics. 2007;23(2):215–221. [PubMed]
50. Morrison JL, Breitling R, Higham DJ, Gilbert DR. GeneRank: using search engine technology for the analysis of microarray experiments. BMC Bioinformatics. 2005;6, article 233 [PMC free article] [PubMed]

Articles from Journal of Biomedicine and Biotechnology are provided here courtesy of Hindawi Publishing Corporation