the structure types consist of the overall and the local models . as an effective tool to analyze gene expression data ,
the clustering analysis is comprehensively applied to many fields , such as gene expression spectrum analysis ( 1 ) , genome study , biological regulatory networks ( 2 ) , medicine filtering , new medicine development , clinical disease diagnosis 3 . , 4 . , and so on .
the basic hypothesis included in the clustering analysis is that , the genes that have the same expression mode may have similar functions ( 5 ) .
however , traditional clustering methods have a series of problems in reducing noise , mining local information , and synthesizing the heterogeneous data , etc .
the data dimension is becoming higher and higher due to the use of new biological microarray chips .
different objects of the same cluster in the data of a high dimensional space could show the similarity only in a certain subspace . when this principle is applied to gene expression data
, mutual - controlling genes could show similar expression patterns in some conditions for test samples .
in fact , in the whole input space , the gene expression pattern is different .
therefore , difficulties appear when we use traditional clustering methods to determine the object similarity by using the value approximation in high dimensional data .
the biclustering algorithm presented by cheng and church ( 6 ) is different from traditional clustering algorithms , in which the similarity is not treated as a function of pairs of genes or pairs of conditions .
instead , it is a measure of the coherence of the genes and conditions in the biclustering .
this measure can be a symmetric function of genes and conditions involved and thus the finding of biclusters is a process that groups genes and conditions simultaneously .
the most important innovation of cheng and church algorithm is that they put forward a definition called residue score 
 6 .
, 7 .. the algorithm divides an expression model into three parts : attribute residue , object residue , and -cluster residue ( or background residue ) .
the mathematical definitions are as follows:(1)eij=iieij|i|eij=jjeij|j|eij=ii , jjeij|i||j| where i and j are the row and column vector sets of the submatrix , respectively ; |i| and |j| are the number of rows and columns , respectively ; eij is the element of the submatrix ; eij , eij , and eij are the attribute residue , object residue , and -cluster residue , respectively .
the definition of the residue score is as follows:(2)rsij(i , j)=eijeijeij+eij let x be the set of genes and y the set of conditions .
let eij be the element of the gene - condition expression matrix representing the logarithm of the relative abundance of the mrna of the i gene under the j condition .
let i  x and j  y be the subsets of genes and conditions .
the pair ( i , j ) specifies a submatrix aij with the following mean squared residue score:(3)h(i , j)=ii , jjrsij2|i||j| the lowest score h(i , j ) = 0 indicates that the gene expression levels fluctuate in unison .
these trivial biclusters may not be very interesting but need to be discovered and masked so that more interesting ones can be found .
the row variance may be an accompanying score to reject trivial biclusters:(4)v(i , j)=1|j|jj(eijeij)2 the higher the value of h is , the more disordered the data is . in cheng and church algorithm , a greedy method is used to select submatrix with a low h score .
firstly , the method is to remove the row or column to achieve the largest decrease of the score .
for the current submatrix , they calculate the average residue score of each row using d(i)=1|j|jjrsij(i , j ) and the average residue score of each column using e(j)=1|i|iirsij(i , j ) , then choose the row or column with the maximal score and delete it from the current submatrix , until h(i , j ) < . also they use a parameter  , so that they can delete a set of nodes each time before the score is recalculated . without updating the score after the removal of each node , the matrix may shrink too much and one may miss some large -clusters .
one may also choose an adaptive  based on the score and the size during the iteration .
secondly , they add rows and columns so that the matrix with the maximal size can be obtained .
the most important innovation of cheng and church algorithm is that they put forward a definition called residue score 
 6 .
, 7 .. the algorithm divides an expression model into three parts : attribute residue , object residue , and -cluster residue ( or background residue ) .
the mathematical definitions are as follows:(1)eij=iieij|i|eij=jjeij|j|eij=ii , jjeij|i||j| where i and j are the row and column vector sets of the submatrix , respectively ; |i| and |j| are the number of rows and columns , respectively ; eij is the element of the submatrix ; eij , eij , and eij are the attribute residue , object residue , and -cluster residue , respectively .
the definition of the residue score is as follows:(2)rsij(i , j)=eijeijeij+eij let x be the set of genes and y the set of conditions .
let eij be the element of the gene - condition expression matrix representing the logarithm of the relative abundance of the mrna of the i gene under the j condition .
let i  x and j  y be the subsets of genes and conditions .
the pair ( i , j ) specifies a submatrix aij with the following mean squared residue score:(3)h(i , j)=ii , jjrsij2|i||j| the lowest score h(i , j ) = 0 indicates that the gene expression levels fluctuate in unison .
these trivial biclusters may not be very interesting but need to be discovered and masked so that more interesting ones can be found .
the row variance may be an accompanying score to reject trivial biclusters:(4)v(i , j)=1|j|jj(eijeij)2 the higher the value of h is , the more disordered the data is . in cheng and church algorithm ,
firstly , the method is to remove the row or column to achieve the largest decrease of the score . for the current submatrix
, they calculate the average residue score of each row using d(i)=1|j|jjrsij(i , j ) and the average residue score of each column using e(j)=1|i|iirsij(i , j ) , then choose the row or column with the maximal score and delete it from the current submatrix , until h(i , j ) < . also they use a parameter  , so that they can delete a set of nodes each time before the score is recalculated . without updating the score after the removal of each node ,
one may also choose an adaptive  based on the score and the size during the iteration .
secondly , they add rows and columns so that the matrix with the maximal size can be obtained .
because the greedy method may not always lead to correct results , we use an additional course to avoid deleting 
the steps for the node addition in the original algorithm are as follows:1.compute eij ( for all i ) , eij ( for all j ) , eij , and h(i , j).2.add the columns j  j with1|i|ii(eijeijeij+eij)2<h(i , j).3.recompute eij , eij , and h(i , j).4.add the rows i  i with1|j|jj(eijeijeij+eij)2<h(i , j).5.for the i row that is still not in i , add its inverse if1|j|jj(eijeijeij+eij)2<h(i , j).6.if no node needs to add in the current iteration , return the final i and j. compute eij ( for all i ) , eij ( for all j ) , eij , and h(i , j ) .
recompute eij , eij , and h(i , j ) . add the rows i  i with 1|j|jj(eijeijeij+eij)2<h(i , j ) .
for the i row that is still not in i , add its inverse if 1|j|jj(eijeijeij+eij)2<h(i , j ) .
if no node needs to add in the current iteration , return the final i and j. considering that the search space of cheng and church algorithm is only a subspace of the result set , we make some improvements as follows . in order to maximize the size of the result submatrix , we amend the decision condition in the original algorithm by changing the original constraint(5)1|i|ii(eijeijeij+eij)2<h(i , j)into the following form(6)1|i|ii(eijeijeij+eij)2<kh(i , j ) and when it is added into the former matrix , the value of h in the new matrix is less than the original value .
the improved algorithm extends the searching scope and increases the number of the nodes that can be added into the cluster .
our improved algorithm introduces a parameter k in equation ( 6 ) to ensure that the blind search is reduced .
cross validation shows that the improved algorithm performs better when k is taken as 3.2 . to speed up the improved algorithm
, we first express the matrix by using the idea of chromosome used in evolutionary computation , and then change the chromosomes in the matrix into two - dimensional link lists , in which we calculate the value of h and save the values of the chromosomes in the field h. to examine the efficiency of the improved algorithm , we tested it using the yeast gene expression spectrum from the gene expression data set ( 2 ) .
for the ten clusters obtained in the simulation , we calculated the average computational time of the results and found that the original algorithm cost 65  s , while the improved algorithm cost 94  s. the comparison results are shown in table 1 .
the quality of result sets of the improved algorithm is enhanced obviously , on the tolerable condition that the time cost is increased by less than 0.5 times .
the comparison of the submatrix rows and columns from the improved algorithm and the result sets of the original algorithm are also shown in table 1 .
it is obvious that from the results in the same condition , the improved algorithm can obtain better result sets and more information . in cheng and church algorithm ,
there are two important parameters  and  that need to be set before the algorithm running , where  is a threshold of score function h and measures the extent of data consistency .
the parameter  influences the quality of matrix clustering and in general it is better if the value is smaller .
but if  is too small , the scale of the submatrix will be over small and easy to lose information .
hence , a balance point should be found for this parameter before running the algorithm .
the parameter  is used in the deletion course of the first phase in the original algorithm , which is also an important threshold .
we determined the value ranges through experiments to provide referable information for realizing adaptive setting for the parameters .
firstly , we chose real data sets for testing . through a series of numerical experiments
, we obtained the relation between the values of parameter  and submatrix size , as shown in figure 1 .
the arithmetic average of space size is used to estimate the quality of the clustering . in the experiments
, it was found that the size of the submatrix decreases monotonously with the descent of the value of . when  is taken as around 120 , the trend of the descent is gentle .
even the value of  goes down again , this trend does not change essentially .
therefore , we suggest that for these data sets , it is better to take the value of  in the range of [ 120 , 180 ] . for the same data sets , we took the difference of the two systems clocks before and after the experiment as the time consumption of clustering , and only calculated the consuming time during the course of deletion . in this way we obtained the relation between the value of  and the time consumption ( figure 2 ) .
the value of  was taken in the range of [ 2.8 , 3.2 ] .
we also need to make practical clustering test at  = 2.8 to avoid any misvalue .
if the clustering results are satisfied , we could keep the range , otherwise we have to increase the lower limit . for different data sets
, we can obtain a series of results . through linear regression and suitable adjustment to these calculation results
let [ a , b ] be the value range of data sets , m the number of genes , and n the number of conditions .
the simulating experiments showed that it is better to take the value of  in the range of [ 3j , 4j ] .
the results of simulations showed that it is better to take the value of  in the range of [ 7l , 8l ] .
the open human lymphoma b cell data set ( 8) was used to examine the proposed improved algorithm .
compared with the original algorithm , the quality of clustering results using the improved algorithm is enhanced obviously , the mining expression models are better , and the data possess stronger consistency with fluctuation on the condition that the time cost is increased a bit .
in addition , in spite that the noise level of data sets is very high of having the loss rate of 12.3% , simulation results showed that the improved algorithm could still keep a good clustering effect even if the noise interference is very strong .
because the greedy method may not always lead to correct results , we use an additional course to avoid deleting 
the steps for the node addition in the original algorithm are as follows:1.compute eij ( for all i ) , eij ( for all j ) , eij , and h(i , j).2.add the columns j  j with1|i|ii(eijeijeij+eij)2<h(i , j).3.recompute eij , eij , and h(i , j).4.add the rows i  i with1|j|jj(eijeijeij+eij)2<h(i , j).5.for the i row that is still not in i , add its inverse if1|j|jj(eijeijeij+eij)2<h(i , j).6.if no node needs to add in the current iteration , return the final i and j. compute eij ( for all i ) , eij ( for all j ) , eij , and h(i , j ) .
recompute eij , eij , and h(i , j ) . add the rows i  i with 1|j|jj(eijeijeij+eij)2<h(i , j ) .
for the i row that is still not in i , add its inverse if 1|j|jj(eijeijeij+eij)2<h(i , j ) .
if no node needs to add in the current iteration , return the final i and j. considering that the search space of cheng and church algorithm is only a subspace of the result set , we make some improvements as follows . in order to maximize the size of the result submatrix , we amend the decision condition in the original algorithm by changing the original constraint(5)1|i|ii(eijeijeij+eij)2<h(i , j)into the following form(6)1|i|ii(eijeijeij+eij)2<kh(i , j ) and when it is added into the former matrix , the value of h in the new matrix is less than the original value .
the improved algorithm extends the searching scope and increases the number of the nodes that can be added into the cluster .
our improved algorithm introduces a parameter k in equation ( 6 ) to ensure that the blind search is reduced .
cross validation shows that the improved algorithm performs better when k is taken as 3.2 . to speed up the improved algorithm
, we first express the matrix by using the idea of chromosome used in evolutionary computation , and then change the chromosomes in the matrix into two - dimensional link lists , in which we calculate the value of h and save the values of the chromosomes in the field h. to examine the efficiency of the improved algorithm , we tested it using the yeast gene expression spectrum from the gene expression data set ( 2 ) .
for the ten clusters obtained in the simulation , we calculated the average computational time of the results and found that the original algorithm cost 65  s , while the improved algorithm cost 94  s. the comparison results are shown in table 1 .
the quality of result sets of the improved algorithm is enhanced obviously , on the tolerable condition that the time cost is increased by less than 0.5 times .
the comparison of the submatrix rows and columns from the improved algorithm and the result sets of the original algorithm are also shown in table 1 .
it is obvious that from the results in the same condition , the improved algorithm can obtain better result sets and more information .
in cheng and church algorithm , there are two important parameters  and  that need to be set before the algorithm running , where  is a threshold of score function h and measures the extent of data consistency .
the parameter  influences the quality of matrix clustering and in general it is better if the value is smaller .
but if  is too small , the scale of the submatrix will be over small and easy to lose information .
hence , a balance point should be found for this parameter before running the algorithm .
the parameter  is used in the deletion course of the first phase in the original algorithm , which is also an important threshold .
we determined the value ranges through experiments to provide referable information for realizing adaptive setting for the parameters .
firstly , we chose real data sets for testing . through a series of numerical experiments , we obtained the relation between the values of parameter  and submatrix size , as shown in figure 1 .
the arithmetic average of space size is used to estimate the quality of the clustering . in the experiments
, it was found that the size of the submatrix decreases monotonously with the descent of the value of . when  is taken as around 120 , the trend of the descent is gentle .
even the value of  goes down again , this trend does not change essentially .
therefore , we suggest that for these data sets , it is better to take the value of  in the range of [ 120 , 180 ] . for the same data sets , we took the difference of the two systems clocks before and after the experiment as the time consumption of clustering , and only calculated the consuming time during the course of deletion . in this way we obtained the relation between the value of  and the time consumption ( figure 2 ) .
the value of  was taken in the range of [ 2.8 , 3.2 ] .
we also need to make practical clustering test at  = 2.8 to avoid any misvalue .
if the clustering results are satisfied , we could keep the range , otherwise we have to increase the lower limit . for different data sets
, we can obtain a series of results . through linear regression and suitable adjustment to these calculation results
let [ a , b ] be the value range of data sets , m the number of genes , and n the number of conditions .
the simulating experiments showed that it is better to take the value of  in the range of [ 3j , 4j ] .
the results of simulations showed that it is better to take the value of  in the range of [ 7l , 8l ] .
the open human lymphoma b cell data set ( 8) was used to examine the proposed improved algorithm .
compared with the original algorithm , the quality of clustering results using the improved algorithm is enhanced obviously , the mining expression models are better , and the data possess stronger consistency with fluctuation on the condition that the time cost is increased a bit .
in addition , in spite that the noise level of data sets is very high of having the loss rate of 12.3% , simulation results showed that the improved algorithm could still keep a good clustering effect even if the noise interference is very strong .
the process of the extended space in the second stage of cheng and church algorithm is improved .
the numbers of rows and columns are increased about 20% by using the improved algorithm .
the effects of the two important parameters on the speed of the algorithm and the clustering quality are discussed . on the basis of simulated experiments , the experienced values for selecting parameter ranges
 cheng and church algorithm is an important approach in biclustering algorithms . in this paper , 
 the process of the extended space in the second stage of cheng and church algorithm is improved and the selections of two important parameters are discussed . 
 the results of the improved algorithm used in the gene expression spectrum analysis show that , compared with cheng and church algorithm , the quality of clustering results is enhanced obviously , the mining expression models are better , and the data possess a strong consistency with fluctuation on the condition while the computational time does not increase significantly . 
Introduction
Cheng and Church algorithm
Results and Discussion
Improvements for Cheng and Church algorithm
Parameter selection
Application
Conclusion