adjacent normal - tumor matched lung cancer samples were analysed by the affymetrix genechip human genome u133 array set hg - u133a . a total of 66 samples were used for microarray analysis , including pair - wise samples from 27 patients.10 the accession number in the gene expression omnibus ( geo ) is gse7670 . the protein - protein interaction data was downloaded from the human protein reference database ( hprd ) ( 09/01/2007 release ) . the joint association of gene pair expression states with phenotype was evaluated by calculation of the entropy . here we adapted a simple formulation called entropy minimization and boolean parsimony ( embp).11 firstly , the logarithmic transformed expression value of each gene was binarized into two states : 1 as  high - expression  and 0 as  low - expression  using the corresponding average value across samples as the threshold . then there are four possible states for each gene pair ( table 1 ) . for each state ( s ) we counted the number of times , n0 , that the state s appeared in normal samples and the number of times , n1 , that it appeared in cancerous samples . then we defined q = n1/(n0 + n1 ) as our estimation of the probability that state s is encountered in the cancer phenotype . the uncertainty of determining whether or not the state is encountered in a cancer phenotype was estimated from the entropy h(q ) : 
 h(q)=qlog2(q)(1q)log2(1q ) h(q ) approaches 0 for values of q that are close to either 0 or 1 , and takes a maximum value of 1 for q = 0.5 . if n1 or n0 is equal to 0 , then q equal 0 or 1 , thus h(q ) can not be defined according to above formula . to find the most informative predictive gene pairs associated with a phenotype , we therefore selected those with an h(q ) below a particular threshold value ( < 0.3 ) for further analysis . we then performed a label - randomizing permutation test 10 times , to assess whether any selected predictive gene pairs differed significantly from those selected at random . the permutation p value were calculated by comparing the h with the randomly permutated h. to evaluate the prediction performance of gene pairs as biomarkers , we use a support vector machine ( svm ) as a classifier to test the classification power . for each gene pair the kernel was polynomial ( degree 1 ) , and the prediction accuracy on leave - one - out cross - validation was evaluated by the gems tool with default setting12 ( http://www.gems-system.org/ ) . adjacent normal - tumor matched lung cancer samples were analysed by the affymetrix genechip human genome u133 array set hg - u133a . a total of 66 samples were used for microarray analysis , including pair - wise samples from 27 patients.10 the accession number in the gene expression omnibus ( geo ) is gse7670 . the protein - protein interaction data was downloaded from the human protein reference database ( hprd ) ( 09/01/2007 release ) . the joint association of gene pair expression states with phenotype was evaluated by calculation of the entropy . here we adapted a simple formulation called entropy minimization and boolean parsimony ( embp).11 firstly , the logarithmic transformed expression value of each gene was binarized into two states : 1 as  high - expression  and 0 as  low - expression  using the corresponding average value across samples as the threshold . then there are four possible states for each gene pair ( table 1 ) . for each state ( s ) we counted the number of times , n0 , that the state s appeared in normal samples and the number of times , n1 , that it appeared in cancerous samples . then we defined q = n1/(n0 + n1 ) as our estimation of the probability that state s is encountered in the cancer phenotype . the uncertainty of determining whether or not the state is encountered in a cancer phenotype was estimated from the entropy h(q ) : 
 h(q)=qlog2(q)(1q)log2(1q ) h(q ) approaches 0 for values of q that are close to either 0 or 1 , and takes a maximum value of 1 for q = 0.5 . if n1 or n0 is equal to 0 , then q equal 0 or 1 , thus h(q ) can not be defined according to above formula . to find the most informative predictive gene pairs associated with a phenotype , we therefore selected those with an h(q ) below a particular threshold value ( < 0.3 ) for further analysis . we then performed a label - randomizing permutation test 10 times , to assess whether any selected predictive gene pairs differed significantly from those selected at random . to evaluate the prediction performance of gene pairs as biomarkers , we use a support vector machine ( svm ) as a classifier to test the classification power . for each gene pair , we used the expression values of the two genes as the inputs . the kernel was polynomial ( degree 1 ) , and the prediction accuracy on leave - one - out cross - validation was evaluated by the gems tool with default setting12 ( http://www.gems-system.org/ ) . the gene pairs most strongly associated with the phenotype for human lung cancer are listed in table 2 . almost all of the 16 gene pairs listed showed a prediction accuracy > 90% and all modules had a p - value < 10 in the permutation test . three gene pairs , pafah1b1-ndel1 , cav1-src and nos3-cav1 , showed a clear distribution skewness in cancer samples ( n1 = 26 vs n0 = 1 ) . to determine whether these identified gene pairs played a role in the mechanism of tumorigenesis , we further investigated the enriched gene functional categories and pathways , and the genetic association of these informative gene pairs with cancer using the national cancer institute ( nci ) david tool ( http://david.abcc.ncifcrf.gov ) . a total of 354 genes involved in gene pairs which entropy < 0.3 were selected for further analysis . high - expression  status in cancer samples as the  cancer - specific signatures  . of the 354 genes with ensemble signatures , there were 24 ( 7.1% ) that had a genetic association with human cancer , and of the 187 genes with cancer - specific signatures , there were 18 ( 9.6% ) with a similar genetic association ( table 3 , gene - disease association is based on the genetic association database , http://geneticassociationdb.nih.gov/ ) . the most enriched gene function according to gene ontology function association in all signatures was  signal transduction ( 39.6% , p - value 5.1e-11 ) and  cell cycle  ( 15.5% , p - value 4.9e-9 , table 4 ) . in general , the enriched ratio of cancer - specific signatures was higher than ensemble signatures . the most enriched signaling pathway was the mapk pathway ( 9.1% , p - value 1.1e-4 , table 5 ) . an important advantage of our method is that it might reveal cancer - associated expression pattern of gene pairs involved in particular protein - protein interactions . for example , it is widely accepted that cav-1 might play an important role in oncogenic transformation and metastasis.13 cav-1 normally functions as a tumor suppressor gene candidate and could act as a negative regulator of the rasp42/44 map kinase cascade.14,15 here we show that cav-1 is involved in five gene pairs which is  high - expression  in normal samples ( i d = 2 , 5 , 9 , table 2 ) and  low - expression  in cancer samples ( i d = 15 , 16 , table 2 ) . more significantly , the combination of its status with src or nos3 ( enos ) could discriminate between cancer and normal phenotypes ( table 6 ) . src is an oncogene which can down - regulate cav-1 expression through transcriptional mechanisms.16,17 our results clearly demonstrated this pattern :  if src high - expression , and cav-1 low - expression , then leads to cancer  , and  if src high - expression , and cav-1 ( still ) high - expression , then leads to normal  ( table 6 ) . it suggests that different outcomes of the down - regulation action of src on cav-1 might determine the phenotype discrimination . this is summarized concisely in table 6 and suggests that the discovery of novel relationships between cav-1 and a variety of signaling pathways will offer novel opportunities to develop anti - cancer therapies that target cav-1.13 the idea of extracting synergistic gene pairs for biomarker identification is not new , but our method has several advantages : ( 1 ) interpretability . compared to methods which search all possible synergistic gene pairs without biological evidence,18 the cancer signatures identified in the present study are based on protein - protein interactions , which is recognized as the molecular basis of signaling pathways . furthermore , phenotype discrimination based on protein - protein interactions could contribute to elucidation of the tumorigenesis mechanism . compared to other global search methods , the use of protein - protein interaction data optimizes exploration of the protein - protein interaction space by focusing on regions which are more likely to yield synergistic gene pairs . our approach for describing synergistic phenotype discrimination suggests that our method might play a useful role in the identification of combinatory drug targets .
cancer is a disease associated with the deregulation of multiple gene networks . 
 microarray data has permitted researchers to identify gene panel markers for diagnosis or prognosis of cancer but these are not sufficient to make specific mechanistic assertions about phenotype switches . 
 we propose a strategy to identify putative mechanisms of cancer phenotypes by protein - protein interactions ( ppi ) . 
 we first extracted the logic status of a ppi via the relative expression of the corresponding gene pair . 
 the joint association of a gene pair on a cancer phenotype was calculated by entropy minimization and assessed using a support vector machine . 
 a typical predictor is  if src high - expression , and cav-1 low - expression , then cancer . 
 we achieved 90% accuracy on test data with a majority of predictions associated with the mapk pathway , focal adhesion , apoptosis and cell cycle . 
 our results can aid in the development of phenotype discrimination biomarkers and identification of putative therapeutic interference targets for drug development .