microarray data may provide much useful information for disease gene identification and medical diagnosis because microarray has the ability to measure the expression levels of thousands of genes simultaneously . among the huge number of genes , only a small fraction of them show strong correlation with a certain phenotype . many statistical and supervised methods such as t - test , neural network are utilized to mine genes that are differentially expressed under different conditions [ 2 , 3 ] . however , these gene selection techniques are often based on individual gene prioritization by measuring the correlation of each gene with particular disease types so these traditional techniques might ignore the differentially coexpressed ( dce ) gene subsets which are defined to be highly correlated under one experimental condition but uncorrelated under another condition . disease - related differentially coexpressed genes are those which exhibit similar expression patterns in normal samples but share no similarity in disease samples . figure 1 depicts the simulated differentially coexpressed disease genes between normal samples ( samples120 ) and disease samples ( samples 2140 ) . identification of disease specific dec gene subsets is very helpful for disease diagnosis and clinical treatment . clustering algorithms are often used to find gene groups which display similar expression profiles [ 5 , 6 ] . however , the dec genes only show highly correlated expression patterns in one biological state , not across the entire dataset . biclustering is a method to identify gene subsets exhibiting consistent patterns over a subset of experimental conditions , but this method is still not proper for identification of dec gene groups because the experimental conditions may not be in the same biological state [ 7 , 8 ] . kostka and spang proposed the first method to investigate dec gene subsets by using an additive model and a stochastic search algorithm . alteredexpression was an improved algorithm based on additive model to detect optimal dec gene subsets with best rrv ( ratio of residual variance between two different samples ) and minimal f - score . varadan and anastassiou proposed an approach called entropy minimization and boolean parsimony ( embp ) to identify gene subsets whose joint expression state predicts the presence or absence of a particular disease with minimum uncertainty . the coxpress was developed to identify groups of gene that are differentially coexpressed in different biological states by using a resampling method to calculate t - value for each clustered group . these methods took into account all possible gene subsets by searching the whole dataset ; it was a huge computational burden as the number of genes increases . in this paper , the miclique algorithm is proposed to explore dec gene subsets in an intuitive way based on mutual information ( mi ) and clique analysis . mutual information is used to measure the coexpression relationship between each pair of genes in two different kinds of samples , and then the symmetric mutual information matrices are binarized by selecting two threshold values . the adjacency matrix of graph is obtained by logical operation with vertices corresponding to genes and edges corresponding to relationships between genes . gene cliques detected by miclique represent dec gene subsets , which are highly correlated under one experimental condition but uncorrelated under another condition . compared with linear similarity measures such as euclidean distance and pearson correlation [ 12 , 13 ] , the mutual information is a general measure of statistical dependence between variables and capable of detecting any type of functional relationship , which is widely used in gene expression analysis . for the application of mi on gene expression data , the physical meaning of mi(x ; y ) is the reduction of the uncertainty of x due to knowledge of y ( or vice versa ) . note that h(x ) = i(x ; x ) , and so entropy is the self - information . the nonnegative mi(x ; y ) equals zero if and only if x and y are statistically independent , meaning that the variables x and ydo not follow any kind of dependence . graph theoretical concepts are useful for the description and analysis of relationships in biological systems clique analysis is a core component of graph in many biological applications such as gene expression networks analysis , cis regulatory motif finding , and matching three - dimensional molecular structures . generally clique represents biological module of similar function and biological annotations . for a simple undirected graph g with the set of vertices and edges , the degree of a vertex is the number of connected edges ; thus the degree of an isolated vertex is zero . weight of each edge is a value between the pair connection , which might represent costs , lengths , or correlation , and so forth . a complete graph is a graph with every pair of nodes joined by an edge . the adjacency matrix of an undirected graph is a symmetric matrix b = ( bij ) in which the entry bij = 1 if the node i and node j are connected by an edge and 0 otherwise . if the graph is a clique , then b is a matrix with 1 off the diagonal and 0 on the diagonal . if the graph contains a clique , the adjacency matrix of that clique is a submatrix of b. identification of all maximal cliques in a graph is a problem of clique enumeration . bioconductor , the open project for the analysis and comprehension of genomic data , provides a large collection of software for working with graphs and cliques . some social network analysis tools are also efficient in clique analysis . but for imperfect systems or experimental data , the requirement of complete connectivity for maximal cliques is stringent ; so more general notions of cohesive subgroups should be considered including n - cliques , k - plexes , and k - core . for undirected and unweighted graph , a commonly used measure of network cohesion is density , which simply refers to the ratio of the number of edges that is actually present in the graph to maximum possible number of edges . = ( eij)nxs involving n genes from s samples ,   eij is the expression value of the ith gene in jth sample . the sample set is divided into two subsets : s1 ( normal samples ) and s2 ( disease samples ) ; so enxs is also divided into ( e1)nxs1 and ( e2)nxs2 . differentially coexpressed disease genes are those of high mutual information values in normal samples but of low mi values in disease samples . step 1calculating the mutual information of each pair of genes in e1 and e2 , then two square symmetric mutual information matrices ( mi1)nxn and ( mi2)nxn are obtained . a big value of mutual information mi1(i , j ) means that the gene i and gene j are strongly coexpressed in normal samples , while a low value represents weak coexpression . 
  calculating the mutual information of each pair of genes in e1 and e2 , then two square symmetric mutual information matrices ( mi1)nxn and ( mi2)nxn are obtained . a big value of mutual information mi1(i , j ) means that the gene i and gene j are strongly coexpressed in normal samples , while a low value represents weak coexpression . step 2binarizing the mutual information matrices by selecting two threshold values t1 and t2 ( t1 > t2 ) , respectively , for mi1 and mi2 , one has the following . if mi1(i , j )  t1 , then m1(i , j ) = 1 , else m1(i , j ) = 0 . if mi2(i , j )  t2 , then m2(i , j ) = 1 , else m2(i , j ) = 0.m(i , j ) = m1(i , j )  &  m2(i , j ) . if i = j then m(i , j ) = 0.the matrices m1and m2 are binarized mutual information matrices for mi1 and mi2 . m is a logical symmetric matrix obtained by  and  operation on m1 and m2 . if m(i , j ) is 1 , it means that gene i and gene j are coexpressed in normal samples while suffer an alteration in disease groups . 
  binarizing the mutual information matrices by selecting two threshold values t1 and t2 ( t1 > t2 ) , respectively , for mi1 and mi2 , one has the following . if mi1(i , j )  t1 , then m1(i , j ) = 1 , else m1(i , j ) = 0 . if mi2(i , j )  t2 , then m2(i , j ) = 1 , else m2(i , j ) = 0.m(i , j ) = m1(i , j )  &  m2(i , j ) . if mi1(i , j )  t1 , then m1(i , j ) = 1 , else m1(i , j ) = 0 .   if mi2(i , j )  t2 , then m2(i , j ) = 1 , else m2(i , j ) = 0 . m(i , j ) = m1(i , j )  &  m2(i , j ) . if i = j then m(i , j ) = 0 . the matrices m1and m2 are binarized mutual information matrices for mi1 and mi2 . m is a logical symmetric matrix obtained by  and  operation on m1 and m2 . if m(i , j ) is 1 , it means that gene i and gene j are coexpressed in normal samples while suffer an alteration in disease groups . 
 step 3the m matrix can be transformed to the adjacency matrix of a graph g with vertices corresponding to genes and edges corresponding to biological interactions . there is an edge between vertices i and j in g if m(i , j ) = 1 . the dec disease genes , which present a similar expression pattern in normal samples but suffer a distinct alteration in disease samples , are represented as a completely connected subgraph . so the problem of identifying dec disease gene subsets is converted into clique detection based on adjacency matrix . the m matrix can be transformed to the adjacency matrix of a graph g with vertices corresponding to genes and edges corresponding to biological interactions . there is an edge between vertices i and j in g if m(i , j ) = 1 . the dec disease genes , which present a similar expression pattern in normal samples but suffer a distinct alteration in disease samples , are represented as a completely connected subgraph . so the problem of identifying dec disease gene subsets is converted into clique detection based on adjacency matrix . how to select the threshold values of t1 and t2 is very important for biological experimental interpretation . different threshold values lead to different results . if the t1 is high and t2 is low , the graph has few edges and many isolated vertices . as t1 decreases and t2 increases , more edges are added to the graph , until it is completely connected . a graph with a large number of isolated vertices generally will fail to fall into a clique , but too many edges will cause a lot of overlapped cliques , which also are not very informative for data analysis . proper thresholds will lead to a proper percentage of isolated vertices and reasonable experimental results . the threshold values are related with data sources and data types , and so forth , and they can be selected by graph density and percentage of isolated vertex . the percentage of isolated vertices decreases and the number of edges increases as t1 decreases and t2 increases . real gene expression data including colon dataset and leukemia dataset are selected to illustrate the application of the proposed miclique algorithm [ 22 , 23 ] . the colon dataset contains expression levels of 2000 genes with the highest minimal intensity selected from 6500 genes across 62 samples , 40 tumor samples , and 22 normal samples . the leukemia dataset contains gene expression profiles of acute leukemias measured using affymetrix high - density oligonucleotide arrays : acute lymphoblastic leukemia ( all ) and acute myeloid leukemia ( aml ) . the dataset contains 7129 human genes , 47 cases of all ( 38 b - cell all and 9 t - cell all ) , and 25 cases of aml . figure 3 gives the percentage of isolated vertices and the density of the graph ( number of edges present in graph divided by maximum possible number of edges , which is c2000 ) . the final thresholds for colon data are selected as t1 =   2.2 and t2 =   1.0 . the maximal cliques are detected from this gene network , with the minimum size of clique as four . table 2 lists the gene accession numbers in each clique and figure 4 displays the overlapped clique group graphically . there are eight vertices and 19 edges in the cohesive subgroups with the density of 0.68 ( the maximum possible number of edges is c8 ) . figure 5 shows mi values of the eight genes , where each plot is a representation of the mi matrix in either the normal samples or disease samples . each mi value in the matrix is represented as a square , with the color of the square representing the amount of value . the color scale used is black to white , with black representing the smallest value of mi and white representing largest value of mi . the mi values range from 2.072 to 2.477 in normal samples and from 0.508 to 1.095 in disease samples . these eight genes form a differentially coexpressed gene subset , which is disease - related gene module identified by miclique algorithm . table 3 lists the genbank accession number , the gene symbols , accession number in uniprotkb ( uniprot knowledgebase ) , and gene descriptions given by colon data . the uniprotkb is the central hub for the collection of information on proteins such as amino acid sequence , protein name or description , taxonomic data , and biological ontology . figure 6 depicts gene expression profiles of the eight genes in normal and disease samples . as shown in figure 6 , the profiles of these genes are highly coexpressed in normal samples ( samples 122 ) while the coexpression pattern disappears in disease samples ( samples 2362 ) . table 4 lists gene annotations of the eight genes from gene ontology ( go ) obtained by amigo searching tool . go is a database to support biologically meaningful annotation for the description of the molecular function , biological process , and cellular component of gene products . as observed in table 4 , some of the genes are of the common biological functions and involved in the same biological processes such as muscle development , calcium ion binding , and regulation of striated muscle contraction . the results of aigner et al . showed that zeb1 is associated with human colorectal cancer , and zeb1 is a key player in pathologic epithelial to mesenchymal transition ( emt ) associated with tumour progression . have proved that hevin is downregulated in many cancers and hevin may be a potential target for cancer diagnosis and therapy . for example , all these eight genes are included in the differentially expressed genes for colon dataset selected by unified framework ; some of these genes are consistent with the results of other researchers [ 2931 ] . the definition of the similarity measures is very important for identification of the relationships among genes . euclidean distance and correlation coefficient are traditional similarity measures commonly used in gene expression analysis . but both of them are unsuitable for nonlinear relationships that might exist between the patterns . euclidean distance fails to detect the simultaneous upregulated or downregulated expression levels with large amplitude absolute changes . compared with euclidean distance and pearson correlation coefficient , the usage of the mi measure yields a more significant performance . figures 7 and 8 show euclidean distance values matrices and pearson correlation coefficient values matrices of the eight genes identified by miclique from colon dataset respectively . the euclidean distance values range from 2.025 to 7.073 in normal samples and range from 1.676 to 5.497 in disease samples . the pearson correlation coefficient values range from 0.151 to 0.946 in normal samples and range from 0.242 to 0.891 in disease samples . both of the figures display no indication of differentially coexpression patterns among the eight genes . the samples of leukemia dataset are divided into two subclasses of disease samples : acute lymphoblastic leukemia ( all ) and acute myeloid leukemia ( aml ) . the miclique algorithm is applied to the preprocessed and normalized leukemia dataset with t1 = 2.2 and t2 = 0.9 . a group of dec genes is identified , which are coexpressed in all samples but not in aml samples . the mi values of these eight genes in dec group range from 1.944 to 3.348 in all samples and range from 0.764 to 1.225 in aml samples with the average mi values 2.550 in all samples and 0.934 in aml samples , respectively . table 5 lists the genbank accession numbers , gene symbols , and gene descriptions given by leukemia dataset . besides the miclique can identify dec genes correlated in aml but not in all . all these dec genes are helpful for understanding disease pathogenesis of leukemia and biological function of gene modules . the difference between the miclique and supervised gene selection methods is that miclique algorithm evaluates the contributions of genes to phenotype by gene subets , rather than individual genes . although the aim of miclique is not to select discriminative genes between normal and disease tissues , or between different types of disease samples , the identified genes are still very informative for samples classification . for example , most of the genes identified by miclique from colon dataset are also differentially expressed genes , which are consistent with the results of other researches . the dec genes focus on the interaction among gene pairs and disease - related gene network , which is very important for understanding disease pathogenesis and biological function of gene modules . the miclique algorithm has provided a new and intuitive way to biological and clinical cancer research .
computational analysis of microarray data has provided an effective way to identify disease - related genes . 
 traditional disease gene selection methods from microarray data such as statistical test always focus on differentially expressed genes in different samples by individual gene prioritization . 
 these traditional methods might miss differentially coexpressed ( dce ) gene subsets because they ignore the interaction between genes . in this paper , 
 miclique algorithm is proposed to identify dec gene subsets based on mutual information and clique analysis . 
 mutual information is used to measure the coexpression relationship between each pair of genes in two different kinds of samples . 
 clique analysis is a commonly used method in biological network , which generally represents biological module of similar function . by applying the miclique algorithm to real gene expression data , 
 some dec gene subsets which correlated under one experimental condition but uncorrelated under another condition are detected from the graph of colon dataset and leukemia dataset .