reconstructing and modeling gene - expression networks is one of the most challenging problems of functional genomics .
large - scale monitoring of gene expression is considered to be one of the most promising techniques for reconstructing gene regulatory circuits .
there are different approaches to describing gene networks , for example , boolean models , models based on differential equations , and bayesian networks , among others , but most share a common element - the expression of each gene in the network depends on the expression of some other genes .
to reconstruct such a network we have to answer two questions for each gene in the network : which genes affect it , and how they affect it , for example , positively , negatively or in a more complex way .
most gene - network models can be described as graphs in which each node represents a gene and the presence of an edge between two nodes indicates the existence of an interaction between the connected genes .
edges can have different interpretations ; they can mean either direct interactions or simply observations in the data , which in turn may be the result of either direct or indirect interactions .
a control or influence function associated with each node is needed if we want to describe how input signals are affecting the particular gene .
for example , conditional probability distributions play such a role in bayesian networks , while boolean functions do so in boolean nets . here
we describe a different approach for reconstructing elements of gene networks based on predicting the expression ( or changes in the expression ) of a given gene from the expression ( or changes in the expression ) of other genes .
we present our prediction results in the form of so - called classifiers - decision trees and decision rules .
first , it allows one to identify genes affecting the target gene directly from the classifier ; second , we do not have to assume any arbitrary discretization thresholds ; third , each data sample is treated as an example , and classification algorithms are constructed in a way to learn from these examples ( normally , the more examples the higher the accuracy , usually ) and finally , classifiers given in the form of decision trees or decision rules are easy to interpret . in our model
we assume that the transcription machinery of a gene can be in a finite number of different states depending on the abundance of the other genes ' products , and that the expression of the gene is determined by its state . for simplicity , we consider the classifiers constructed to discriminate only between two states , ' expressed more than average ' and ' expressed less than average ' , although the model can be generalized to any number of states in a straightforward manner . at the same time , there is no single threshold for absence / presence of gene products - the same gene product may affect the state of different genes at different thresholds .
for instance , a particular level of a given gene product may be sufficient to switch on the expression of one gene , but may have to be raised to switch on the expression of a different gene .
our results show that this is indeed the case in real gene networks . in this way ,
our approach is rather different from the boolean networks and , in fact , from any approach that depends on a priori discretization of expression data . despite rather different formulations
, there is a minor similarity between the supervised classification and gene - expression data clustering , which helps to illustrate our approach .
if we know that a gene g belongs to a cluster of genes that share similar expression profiles , then , given a new sample , the behavior of the gene g can be predicted on the basis of the behavior of other genes in the cluster .
such a clustering approach can produce only ' symmetric ' rules : for example , gene g correlates ( or anticorrelates ) with gene h. the classification rules that we derive are often more complex and can involve more than two genes , for example , gene g is expressed only if gene h1 is expressed and h2 is not expressed .
it is important that our classifiers are not black boxes - they consist of sets of simple rules that can be used as elements for building and explaining gene networks , and be examined for their biological meaning . for each gene in the network
we know which genes affect it , as well as a precise description of how they affect the state of the predicted gene .
we applied our methodology to the microarray datasets of spellman and cho for the budding yeast ( saccharomyces cerevisiae ) cell cycle .
as an example , we considered a set of well - described genes , which encode proteins important for cell - cycle regulation .
all extracted relations were examined with respect to the known roles of the selected genes in the cell cycle and in most cases the rules confirmed the a priori knowledge , which indicates the validity of our approach .
our starting point is a gene - expression data matrix , x , where each row represents a gene and each column represents a sample .
each element , xij , of x indicates the expression level of a gene i in a sample j and is called a gene - expression value .
the exact meaning of expression values may be different for different matrices , representing absolute or comparative measurements .
here we use gene - expression log ratios obtained from comparisons of gene expression in a sample versus control , although , in fact , any consistent way of measuring gene expression can be used .
as already mentioned , we assume that the transcription machinery of a gene can be in a finite number of different states .
for example , one can use states ' expressed'/'not expressed '   or ' upregulated'/'downregulated ' .
here we distinguish between two different states ' expressed more than average'/'expressed less than average ' .
more precisely , we define the state , sij , of a gene i under condition j as follows given a gene g , we predict its state from expression measurements of other genes .
the gene g is called the predicted gene , while the genes on which we make the prediction are called the explaining genes .
note that the concept of state is used here only for predicted genes , while the expression values are used for explaining genes . having selected time - series datasets
given a gene - expression matrix x and a gene i , we are going to predict : one , the state of the gene i in sample j from the expression values of other genes in the same sample ; two , the state of the gene i in sample j from the expression values of genes from the previous sample / samples ; and three , the change in the state of the gene i from the changes in states of other genes .
our ultimate goal is to build classifiers that can be used as elements of putative gene networks .
we will use the notation ' simultaneous ' for the events covered by the first problem and ' time delay ' for the second .
the third problem describes events , which may or may not be separated in time and we use the notation ' changes ' for them .
the functions determining states of predicted genes from data are called classifiers , while algorithms building such classifiers on the basis of data with known states are called inducers or induction algorithms . each expression profile ( the column of the expression matrix x ) with a known state of a predicted gene is called an example or an instance .
if a subset of the examples is separated from the training set and is used for estimation of classification accuracy , it is called a test set . in this study
a decision tree is a rooted tree in which non - leaf nodes are labeled with explaining genes , the arcs from non - leaf nodes are labeled with possible characteristics of explaining genes , and the leaves of the tree are labeled with the states of the predicted gene .
an example of the decision tree for classification of the yeast gene cln2 is shown in figure 1 .
each pass from the root node to a leaf node in the tree presents a rule that defines a state of the predicted gene via expression levels of explaining genes .
it follows that every decision tree is equivalent to a list of decision rules ( see the next section for details ) . to make the verification of the classification results more straightforward we introduce a representation of classifiers in the form of simple rules .
the following language for rules is used : ' + a ' means that gene a is ' upregulated ' ; ' -a ' that gene a is ' downregulated ' , '  ' is used for simultaneous events , '  ' is used to distinguish between events that are divided in time .
for instance , + a+b-c means that c is ' downregulated ' when a and b are ' upregulated ' ; + b+a means that a is ' upregulated ' if b was ' upregulated ' ( for example , in the previous time point for the time series ) ; abc means that positive change in the expression level of a along with simultaneous negative change in expression of b coincides with simultaneous negative change of c expression ; ba means that positive change in expression level of b precedes negative change of a expression .
this method of representation allows the decomposition of decision trees of complex structure into simple and compactly presented relations , which can be independently compared to the existing knowledge .
we carried out literature searches through pubmed   and the yeast protein database ( ypd )   to find the biological relevance of the extracted rules ( see the following sections ) . for more precise definitions and formulations of the three problems
all major transitions in the budding yeast cell cycle are regulated by cyclins via associated cyclin - dependent kinase ( cdk ) activity . to test our approach we chose a small group of yeast genes .
these are the cyclin genes cln1 - 3 and clb1 - 6 , and cdc28 , mbp1 , cdc53 , cdc34 , skp1 , swi4 - 6 , hct1 , cdc20 , sic1 , and mcm1 , which are involved in cell - cycle regulation and whose interactions are well described .
the same set of genes ( with the addition of bck2 and the exclusion of clb3 , clb4 ) was used by chen et al . , who presented a mathematical model of the cell - cycle events .
as no reliable data were found for clb3 and bck2 in the cdc15 dataset , we did not include them in our study ( table 1 ) .
we carried out two computational experiments and compared their results . in the first experiment we considered eight cyclin genes , while in the second we added to them 12 other genes , the products of which
we used the microarray data from spellman et al .   and cho et al .  
obtained for s. cerevisiae cell cultures that were synchronized by three different methods : the cdc15 , cdc28 and alpha - factor datasets .
the data - transformation method used by spellman et al . represents background corrected signal log ratios , with control as an average expression level extracted from " asynchronous cultures of the same cells growing exponentially at the same temperature in the same medium " ( the dataset of cho   was integrated with other data using appropriate renormalization and included in the analysis by spellman et al . as the cdc28 dataset ) .
we chose the cdc15 experiment for the training dataset because it has the largest number of data points ( samples ) , which consequently , provided us with the largest number of instances .
for the first classification problem we used all the data , for the other two problems we used only adjacent equidistant measurements .
the remaining experimental datasets , cdc28 and alpha - factor , were used as test sets .
the accuracy of the classifiers for the cdc15 training set was estimated in three different ways : by 10-fold stratified cross - validation , and by cdc28 and alpha - factor datasets   as test sets . only those classifiers that have high accuracy by all three estimations were selected for constructing decision rules .
we ' compressed ' all possible expression intervals into ' upregulated'/'downregulated ' and used the rule language described above .
for example , the decision tree for cln2 given in figure 1 , implies only one rule + swl5 cln2 , because only one branch of this tree ( ' swi5 > 1.1 ' , meaning that expression of swi5 is more than 110% of the average level ) can be interpreted in terms of ' upregulated'/'downregulated ' .
the other branches are more difficult to interpret ; indeed , the fact that the expression of cln1 is more than 80% of the average ( cln1 > 0.8 ) does not unambiguously imply ' upregulated ' or ' downregulated ' .
we do not consider any relations that can not be described in terms ' upregulated'/'downregulated ' .
nevertheless , this does not mean that they are irrelevant ; these relations exist in the data and some additional analysis is needed to confirm or to reject them .
this table presents ' simultaneous ' , ' time delay ' and ' changes ' relations in gene activities .
the absence of some genes from table 1 means that the algorithms used did not extract reliable rules for them .
the three datasets selected for our experiments do not contain all possible information about gene interactions , and it is likely that information about some of the interactions is not in all of them . taking this into account , our procedure of the classifier selection is rather conservative and not all rules that are present in the data were extracted .
however , we use this conservative approach in order to minimize the possibility of extracting some ' strong ' but misleading dependencies by chance , that is , to avoid false positives . the combination of our approach with the follow - up validation of the results by other experimental methods could help to confirm the questionable rules presented in the lower part of table 2 .
these rules have clear biological explanations in the literature , but they failed in one or two of the accuracy tests ( see additional data files for all accuracy estimates ) .
for example , the accuracy estimated by 10-fold cross - validation for skp1 under ' simultaneous ' events is almost 92% , but the performance of the classifier was not confirmed by estimations with cdc28 and alpha - factor test sets .
examples of highly accurate rules are those created for genes clb1 and clb2 ( table 2 ) .
the accuracy of the clb1 classifier for ' simultaneous ' events ( table 3 , 20 genes ) is 95.8% by the 10-fold cross - validation test along with 88.2% and 88.9% for the estimations where cdc28 and alpha - factor were used as test sets .
it means that not only does cross - validation produce highly accurate estimates , but the information extracted for clb1 from the cdc15 dataset is consistent with the information about this gene contained in the cdc28 and alpha - factor datasets .
we can compare our classification rules with the analysis of expression time series , performed by spellman et al .
the better the score the more likely the gene is to be periodically regulated . by establishing a threshold for the score values the authors identified cell - cycle - regulated yeast genes . among those genes selected for our experiments
these are skp1 , mbp1 , cdc34 , cdc53 , swi6 , hct1 , cdc28 and mcm1 .
we obtained no accurate rules for these genes , except for the questionable ones for skp1 , mbp1 and cdc34 .
all these questionable rules have high 10-fold cross - validation accuracy on cdc15 data and are inconsistent with cdc28 and alpha - factor datasets .
the reason for this is clear : these genes have much stronger signals during the cdc15 experiment than during the other two ( signal peak to trough ratio for cdc15 is two or even three times higher than for cdc28 and alpha - factor datasets ) .
the situation is rather different for cdc53 , swi6 , hct1 , cdc28 and mcm1 : their expression levels are not significantly different across all three experiments .
their scores indicate that they can serve as negative controls and , indeed , no accurate rules were obtained for these genes .
this fact reflects that our rule - extraction procedure performed well and that we did not extract rules randomly .
it should be noted that the size of the used training sets is relatively small for a machine - learning approach .
classification is an individual problem in the case of each gene , and the size of the training set sufficient to achieve good accuracy can vary from gene to gene .
the advantage of our approach is that to make classification more precise one can just add new experimental data ( expression profiles ) to the dataset .
we also plan to biuld an expert system for gene network reconstruction , based on the method presented here .
our starting point is a gene - expression data matrix , x , where each row represents a gene and each column represents a sample .
each element , xij , of x indicates the expression level of a gene i in a sample j and is called a gene - expression value .
the exact meaning of expression values may be different for different matrices , representing absolute or comparative measurements .
here we use gene - expression log ratios obtained from comparisons of gene expression in a sample versus control , although , in fact , any consistent way of measuring gene expression can be used .
as already mentioned , we assume that the transcription machinery of a gene can be in a finite number of different states .
for example , one can use states ' expressed'/'not expressed '   or ' upregulated'/'downregulated ' .
here we distinguish between two different states ' expressed more than average'/'expressed less than average ' .
more precisely , we define the state , sij , of a gene i under condition j as follows given a gene g , we predict its state from expression measurements of other genes .
the gene g is called the predicted gene , while the genes on which we make the prediction are called the explaining genes .
note that the concept of state is used here only for predicted genes , while the expression values are used for explaining genes . having selected time - series datasets
given a gene - expression matrix x and a gene i , we are going to predict : one , the state of the gene i in sample j from the expression values of other genes in the same sample ; two , the state of the gene i in sample j from the expression values of genes from the previous sample / samples ; and three , the change in the state of the gene i from the changes in states of other genes .
our ultimate goal is to build classifiers that can be used as elements of putative gene networks .
we will use the notation ' simultaneous ' for the events covered by the first problem and ' time delay ' for the second .
the third problem describes events , which may or may not be separated in time and we use the notation ' changes ' for them .
the functions determining states of predicted genes from data are called classifiers , while algorithms building such classifiers on the basis of data with known states are called inducers or induction algorithms . each expression profile ( the column of the expression matrix x ) with a known state of a predicted gene is called an example or an instance .
if a subset of the examples is separated from the training set and is used for estimation of classification accuracy , it is called a test set . in this study
a decision tree is a rooted tree in which non - leaf nodes are labeled with explaining genes , the arcs from non - leaf nodes are labeled with possible characteristics of explaining genes , and the leaves of the tree are labeled with the states of the predicted gene .
an example of the decision tree for classification of the yeast gene cln2 is shown in figure 1 .
each pass from the root node to a leaf node in the tree presents a rule that defines a state of the predicted gene via expression levels of explaining genes .
it follows that every decision tree is equivalent to a list of decision rules ( see the next section for details ) . to make the verification of the classification results more straightforward we introduce a representation of classifiers in the form of simple rules .
the following language for rules is used : ' + a ' means that gene a is ' upregulated ' ; ' -a ' that gene a is ' downregulated ' , '  ' is used for simultaneous events , '  ' is used to distinguish between events that are divided in time .
for instance , + a+b-c means that c is ' downregulated ' when a and b are ' upregulated ' ; + b+a means that a is ' upregulated ' if b was ' upregulated ' ( for example , in the previous time point for the time series ) ; abc means that positive change in the expression level of a along with simultaneous negative change in expression of b coincides with simultaneous negative change of c expression ; ba means that positive change in expression level of b precedes negative change of a expression .
this method of representation allows the decomposition of decision trees of complex structure into simple and compactly presented relations , which can be independently compared to the existing knowledge .
we carried out literature searches through pubmed   and the yeast protein database ( ypd )   to find the biological relevance of the extracted rules ( see the following sections ) . for more precise definitions and formulations of the three problems
all major transitions in the budding yeast cell cycle are regulated by cyclins via associated cyclin - dependent kinase ( cdk ) activity . to test our approach we chose a small group of yeast genes .
these are the cyclin genes cln1 - 3 and clb1 - 6 , and cdc28 , mbp1 , cdc53 , cdc34 , skp1 , swi4 - 6 , hct1 , cdc20 , sic1 , and mcm1 , which are involved in cell - cycle regulation and whose interactions are well described .
the same set of genes ( with the addition of bck2 and the exclusion of clb3 , clb4 ) was used by chen et al . , who presented a mathematical model of the cell - cycle events .
as no reliable data were found for clb3 and bck2 in the cdc15 dataset , we did not include them in our study ( table 1 ) .
we carried out two computational experiments and compared their results . in the first experiment we considered eight cyclin genes , while in the second we added to them 12 other genes , the products of which are known to be essential for cell - cycle regulation ( see above ) .
we used the microarray data from spellman et al .   and cho et al .  
obtained for s. cerevisiae cell cultures that were synchronized by three different methods : the cdc15 , cdc28 and alpha - factor datasets . the data - transformation method used by spellman et al . represents background corrected signal log ratios , with control as an average expression level extracted from " asynchronous cultures of the same cells growing exponentially at the same temperature in the same medium " ( the dataset of cho   was integrated with other data using appropriate renormalization and included in the analysis by spellman et al .
we chose the cdc15 experiment for the training dataset because it has the largest number of data points ( samples ) , which consequently , provided us with the largest number of instances .
for the first classification problem we used all the data , for the other two problems we used only adjacent equidistant measurements .
the remaining experimental datasets , cdc28 and alpha - factor , were used as test sets .
the accuracy of the classifiers for the cdc15 training set was estimated in three different ways : by 10-fold stratified cross - validation , and by cdc28 and alpha - factor datasets   as test sets . only those classifiers that have high accuracy by all three estimations were selected for constructing decision rules .
we ' compressed ' all possible expression intervals into ' upregulated'/'downregulated ' and used the rule language described above .
for example , the decision tree for cln2 given in figure 1 , implies only one rule + swl5 cln2 , because only one branch of this tree ( ' swi5 > 1.1 ' , meaning that expression of swi5 is more than 110% of the average level ) can be interpreted in terms of ' upregulated'/'downregulated ' .
the other branches are more difficult to interpret ; indeed , the fact that the expression of cln1 is more than 80% of the average ( cln1 > 0.8 ) does not unambiguously imply ' upregulated ' or ' downregulated ' .
we do not consider any relations that can not be described in terms ' upregulated'/'downregulated ' .
nevertheless , this does not mean that they are irrelevant ; these relations exist in the data and some additional analysis is needed to confirm or to reject them .
this table presents ' simultaneous ' , ' time delay ' and ' changes ' relations in gene activities .
the absence of some genes from table 1 means that the algorithms used did not extract reliable rules for them .
the three datasets selected for our experiments do not contain all possible information about gene interactions , and it is likely that information about some of the interactions is not in all of them . taking this into account ,
our procedure of the classifier selection is rather conservative and not all rules that are present in the data were extracted .
however , we use this conservative approach in order to minimize the possibility of extracting some ' strong ' but misleading dependencies by chance , that is , to avoid false positives .
the combination of our approach with the follow - up validation of the results by other experimental methods could help to confirm the questionable rules presented in the lower part of table 2 .
these rules have clear biological explanations in the literature , but they failed in one or two of the accuracy tests ( see additional data files for all accuracy estimates ) . for example , the accuracy estimated by 10-fold cross - validation for skp1 under ' simultaneous ' events is almost 92% , but the performance of the classifier was not confirmed by estimations with cdc28 and alpha - factor test sets .
examples of highly accurate rules are those created for genes clb1 and clb2 ( table 2 ) .
the accuracy of the clb1 classifier for ' simultaneous ' events ( table 3 , 20 genes ) is 95.8% by the 10-fold cross - validation test along with 88.2% and 88.9% for the estimations where cdc28 and alpha - factor were used as test sets .
it means that not only does cross - validation produce highly accurate estimates , but the information extracted for clb1 from the cdc15 dataset is consistent with the information about this gene contained in the cdc28 and alpha - factor datasets .
we can compare our classification rules with the analysis of expression time series , performed by spellman et al .
the better the score the more likely the gene is to be periodically regulated . by establishing a threshold for the score values the authors identified cell - cycle - regulated yeast genes . among those genes selected for our experiments
these are skp1 , mbp1 , cdc34 , cdc53 , swi6 , hct1 , cdc28 and mcm1 .
we obtained no accurate rules for these genes , except for the questionable ones for skp1 , mbp1 and cdc34 .
all these questionable rules have high 10-fold cross - validation accuracy on cdc15 data and are inconsistent with cdc28 and alpha - factor datasets .
the reason for this is clear : these genes have much stronger signals during the cdc15 experiment than during the other two ( signal peak to trough ratio for cdc15 is two or even three times higher than for cdc28 and alpha - factor datasets ) .
the situation is rather different for cdc53 , swi6 , hct1 , cdc28 and mcm1 : their expression levels are not significantly different across all three experiments .
their scores indicate that they can serve as negative controls and , indeed , no accurate rules were obtained for these genes .
this fact reflects that our rule - extraction procedure performed well and that we did not extract rules randomly .
it should be noted that the size of the used training sets is relatively small for a machine - learning approach .
classification is an individual problem in the case of each gene , and the size of the training set sufficient to achieve good accuracy can vary from gene to gene .
the advantage of our approach is that to make classification more precise one can just add new experimental data ( expression profiles ) to the dataset .
we also plan to biuld an expert system for gene network reconstruction , based on the method presented here .
to verify the biological relevance of our results we consider the expression of the genes in association with the consecutive phases of the cell cycle , g1 , s , g2 , m , m / g1 , which are usually used in the literature . the highest - accuracy classifiers were obtained for the group of cyclins for which almost all possible known relations were reconstructed : + clb5+clb6 ; + clb6+clb5 ; clb2clb1 ; -clb1-clb2 ; -clb2+cln2 ; + cln2+cln1 and + clb6-clb1 ; + clb6-clb2 ; clb1cln2
. our rules are consistent with the knowledge that the maximum of clb2 transcription is in g2 phase , whereas cln1 , cln2 , clb5 and clb6 , whose expression patterns are very similar , all have their expression maximum in g1 .
the rules obtained are in agreement with clb2 and clb1 being expressed simultaneously in g2 .
questionable rules , cln2clb5 and -clb2+cln1 , from the lower part of table 2 have the same explanations ( see classification rules for explanation of questionable rules ) .
rules that we obtained for the expanded set of genes do not conflict with the ones for cyclins .
they confirm several additional details about coordination of cyclin transcription with expression of genes involved in cell - cycle regulation .
for example , transcription of swi5 and clb1 is g2/m specific and activated in late s phase ; the expression pattern of swi5 is similar to that of clb1 and clb2 and the peak of mrna concentration of swi5 is in g2 .
the following classification rules for cln1 , cln2 and swi5 are in agreement with these data : + swi5-cln2 , -clb1-swi5 , -clb2-swi5 and questionable rules cln2swi5,+swi5-cln1 . clearly , ' simultaneous ' as well as ' changes ' rules for mbp1 and cdc34 , skp1 ( table 2 , lower part ) can be explained by the fact that their activities as parts of the mbf and scf complexes are completely separated in time .
cdc20 is transcribed in late s / g2 phase and its product is required for metaphase - to - anaphase transition , whereas cln2 and cln1 have their transcription maximum in g1 . at the same time , there is a group of eight genes for which no accurate classifiers were obtained .
there are several possible reasons for this and we discussed some in classification rules . one obvious restriction of the microarray methodology is that it gives us information about gene regulation only at the level of transcription .
furthermore , mrna extractions in the cdc15 experiment were made every 10 minutes during three cell cycles , which may not be frequent enough to observe all events .
for example , some of the selected genes are expressed at a low and nearly constant level , making the detection of slight changes in mrna concentrations difficult .
cdc28 is assumed to be expressed constitutively , as it is involved in all cell - cycle phases .
it is required for initiation of mitosis , dna replication , polarization of the actin cytoskeleton , spindle - pole - body duplication and bud emergence . furthermore , most of the regulatory interactions of cdc28 are at the protein level , which can not be straightforwardly detected by the microarray experiments considered .
the data - quality issues in the context of gene - network reconstruction are discussed in .
there are a few rules among those extracted that reflect symmetric relations between genes , and which , therefore , can be potentially obtained by clustering .
however , the majority of extracted rules have a structure that is sufficiently different from the clustering - like one . dependencies between explaining and predicted genes of the decision trees , from which the rules were constructed , are even more complex and hardly can be retrieved by clustering algorithms ( for decision trees see additional data files ) .
these relationships may not be the optimal for constructing the full network of gene interactions ; nevertheless , they exist in the data and may be clearly explained with the help of existing knowledge . using the obtained results we can construct networks of gene interrelationships by connecting genes by directed edges according to classifiers .
classifiers in such a network are considered to be the control functions , which map the expression levels of other genes into the state of a corresponding gene .
connecting genes from table 2 gives us the network presented in figure 2 , which is simply a graphical representation of the dependencies between gene - expression levels contained in the extracted decision rules .
every node in this graph represents a gene , and every arc indicates the relation between genes defined by the corresponding decision rule .
an advantage of network reconstruction using our approach is that , given accurate classifiers , one is able to construct a network correctly , reproducing the architecture and the logic of a network consistent with the data .
moreover , one can easily improve classifiers by adding new expression profiles to the dataset .
it is important that such iterative improvements can be part of an interactive process , when the researcher decides when to stop adding new data and what biological meaning is comprised in the network .
thus , our methodology can be considered as a basis for an interactive expert system for gene - interaction network reconstruction .
all the extracted classification rules are consistent with the data reported in the literature and even though the selected microarray experiments were not designed specifically for gene - network reconstruction , we were still able to find several features of gene transcriptional activities .
although here we apply our approach to a relatively small subset of genes , it seems likely that it can be applied to larger gene sets .
time - course data are not the only type of data to which our approach is applicable .
it is possible to explore various cases where potential dependencies between different experimental samples might occur .
a future goal is to use the method described to deduce larger gene - interaction networks and to investigate groups of genes with unknown interactions .
we also plan to build an expert system for gene - network reconstruction , based on the method presented here .
first , we give more formal definitions and formulations of the problems informally introduced in definitions .
the columns yj = ( x1j, ... ,xkj ) of the gene - expression matrix x are called sample expression profiles .
we also define a partial expression profile yj / i , where the expression value of gene i is missing . as already discussed , we assume that the transcription machinery of gene i can be in a finite number of different states sij for sample j. more precisely , we define the state function i for an arbitrary given gene i as a function such that given a real value x it returns a value from a discrete domain .
let us assume here that i is a function , which returns ' + 1 ' if gene i is ' upregulated ' ( xij > ) and ' -1 ' if it is ' downregulated ' ( xij < ) , where   is the average expression value of gene i. thus , in this particular case i(x )  { -1,+1}. given the expression value xij of gene i , and the function i , we can define the state of the gene as sij = i(xij ) .
our goal is , given a gene - expression matrix x and a gene i , to predict : one , the state of the gene i under condition j from the expression values of other genes in the same sample ( that is , from the partial expression profile yj / i ) ; two , the state of the gene i under condition j from the expression values of genes from the previous sample / samples ( that is , from the partial expression profile yj-1/i ) ; three , the change in the state of the gene from the changes in states of other genes .
,yn } be the set of all sample expression profiles and y / i = { y1/i, ...
,yn / i } be the set of partial sample expression profiles for the given gene i from matrix x. let us define a classifier , c , as a function that maps a vector y to a discrete value s. sometimes , in the context of classification , vector y is called a feature vector , while s is a label .
the subset of y vectors with correct labels assigned to them is called a dataset , d , for a particular classification problem .
an induction algorithm i maps a dataset d into a classifier c. thus , to solve the problems above we need to define datasets and then choose appropriate induction algorithms .
we want to predict the state of gene l from matrix x. induction algorithm i maps the dataset d= ( y / l , sl ) , into the classifier c. ( we use index l for dand cin order to emphasize that they correspond to the lth gene . ) for the given dataset d , we want to create a classifier that predicts the state of gene l correctly , that is , i(d , yj / l ) = c(yj / l ) = slj . for the first problem ,
the predicted gene l and the explaining genes belong to the same sample j. formulation of the second problem is the same , except that the dataset now is d= ( y'/l , s'l ) , where y'/l= { y1/l, ... ,yn-1/l } and s'l = ( sl2 , ... , sln ) .
the classifier cis said to classify gene l for sample j correctly , if c(yj / l ) = slj+1 .
note that for this problem the explaining genes belong to the sample preceding the sample of the predicted gene g. to define the third problem we construct a matrix d consisting of elements dij = sij+1-sij , where sij= i(xij ) .
the formulation of the third problem is equivalent to that of the first if we use dij instead of xij and consider the pair ( y / l , dl ) as the dataset for the third problem .
note that now yj / l = ( d1j, ... ,dl-1j , dl+1j, ... ,dkj ) and dl is the row from the new matrix of dij values associated with the predicted gene g. as a result , features and labels in this particular case belong to the same domain { -1,0,+1 } , where ' + 1 ' means that gene changed its state from ' downregulated ' to ' upregulated ' , ' -1 ' means the opposite change and ' 0 ' is used for the situation when the gene 's state remained unchanged in the transition from one sample ( experimental condition ) to another . to solve the first two problems defined above
, we have to use classifiers for continuous data , that is , any discretization should be a part of the classification algorithm .
this enables us to find abundance thresholds of explaining genes , which are specific for different gene interactions in the network and sufficient for the switching of the predicting gene from one state to the other .
this way every gene has its own unique discretization thresholds for input signals . as a part of the classification problem it is necessary to find which genes are relevant to the prediction of a particular gene .
two kinds of methods for feature subset selection have been generally presented in the literature - filter and wrapper methods . in the filter approach ,
the feature set is filtered to find the ' most promising ' subset by evaluating some objective function before running the induction algorithm .
the weak point of this approach is that the properties of a particular induction algorithm are ignored . in the wrapper approach
the wrapper approach of kohavi was reported as performing better than the filter approach for many real and artificial datasets .
the idea of the wrapper algorithm is to tune parameters of an induction algorithm assuming it to be a black box in order to optimize some objective function ( for example , the accuracy of a classifier ) .
the set of attributes relevant to classification may be considered as parameters of an induction algorithm . selecting the parameters that maximize the objective function gives us a list of ' good ' features . for
the classification rules that we obtain support the validity of the assumption that only a limited number of explaining genes are sufficient for accurate predictions . in this paper
c4.5 is an algorithm that constructs the classification model inductively , generalizing information from given examples of correct classification , and was selected as an algorithm of proven performance for a large variety of datasets .
, the data prediscretized by an entropy - based scheme with fayyad and irani stopping criteria   were used in the inducer with wrappers .
this supervised discretization technique uses the information entropy of the partitions induced by different thresholds to find the appropriate discretization boundaries , and it stops the search following the stopping criterion based on the so - called minimum description length principle ( mdl ) .
thus the information entropy is used as the objective function in the search for the best splitting boundaries and , as the inductive splitting procedure requires some termination conditions , mdl is used as a criterion for termination . because c4.5 was constructed as an algorithm that can be applied to continuous data , in the second approach we used c4.5 without additional discretization techniques .
in addition , as used by kohavi and sahami , c4.5 can be used as an alternative to the fayyad and irani method for data discretization .
all the classifiers were constructed with the help of the weka package of machine - learning tools .
the main reasons for selecting the classification techniques described above are that their results ( in the form of decision trees ) are easy to interpret , they are algorithmically simple and there exist numerous comparisons of their performance in the literature .
although each classification problem requires several classification techniques to be compared , and it is possible that more sophisticated and efficient induction algorithms exist for the datasets we used ( although this is not proven ) , comparative analysis of induction algorithms and their development are not the topics of this study .
the reader may consult the excellent studies of kohavi   and lim et al .   for a more detailed discussion of this problem .
all the algorithms were run with default settings in order to use the results of comparisons of induction algorithms already reported in the literature and to avoid the additional bias associated with the tuning of parameters .
the accuracy estimates shown in table 3 are for those ' simultaneous ' events classifiers for which the performance of classifiers on the test sets is high .
the table presents estimates for c4.5 with wrappers on the data prediscretized by the fayyad and irani method .
because of the high variability of the estimates for cross - validation , it was repeated 30 times for different random partitions of the training sets for each selected classifier and the average values are shown . as two independent test sets were used
, the cross - validation accuracy estimates serve only as an additional indicator of the performance of the created classifiers . as
the number of training instances is small , estimating the confidence limits for the accuracy mean is not straightforward .
moreover , as has been pointed out by many researchers , the common assumptions concerning independence of different estimates are violated when cross - validation is used . in the presence of two independent test sets
we did not do a rigorous analysis of stability of the classifiers , but , nevertheless , we observed that most of the final classifiers ( not the questionable ones ) were stable under different 10-fold splits . as is common practice ,
at the same time , 95% confidence intervals are shown for the accuracy estimates when the test sets were used . as the number of instances is small in both cdc28 and alpha - factor test sets , standard methodology based on the normal approximation of the binomial distribution
instead , we estimated confidence intervals with the help of the beta probability distribution using the methodology proposed in .
additional data file 1 is a list of the classifiers for c4.5 by quinlan with ' wrappers ' by kohavi on the cdc15 dataset with continuous features discretized by the fayyad and irani method .
the first three tables present in additional data file 1 the classifiers for the set of 20 genes and the last three for the set of cyclins .
the notation ' simultaneous ' is used for the classifiers corresponding to the first problem , ' time delay ' to the second problem , ' changes ' to the third problem ( see definitions above ) .
additional data file 2 is a list of the classifiers for c4.5 by quinlan on the cdc15 dataset with continuous features discretized by c4.5 itself .
additional data file 3 contains accuracy estimates for the classifiers provided in additional data file 1 .
abbreviations : 10-cv , 10-fold cross - validation ; cdc28 and  , accuracy estimates where cdc28 and alpha - factor datasets were used as test sets ; overall , test accuracy that was estimated by forming the unified cdc28-alpha - factor test set and testing the classifiers on it .
cross - validation estimates are presented only for the classifiers from table 2 to discriminate them from the others .
bold font is used for the final rules , excluding the questionable ones , and normal is used for the questionable rules .
cross - validation estimates are shown along with the standard deviations , while 95% confidence intervals are presented for those estimates where the test sets were used .
test accuracy was estimated under the assumption that the measurements of the cdc28 and alpha - factor test sets are independent .
additional data file 4 contains accuracy estimates for the classifiers provided in additional data file 2 .
a list of the classifiers for c4.5 by quinlan with ' wrappers ' by kohavi on the cdc15 dataset with continuous features discretized by the fayyad and irani method .
click here for additional data file a list of the classifiers for c4.5 by quinlan on the cdc15 dataset with continuous features discretized by c4.5 itself .
click here for additional data file accuracy estimates for the classifiers provided in additional data file 1 .
click here for additional data file accuracy estimates for the classifiers provided in additional data file 2 .
the weka package distributed under the gnu general public license was used for classifier creation and accuracy estimation .
we thank helen parkinson , johan rung and misha kapushesky for useful discussions and the anonymous referees for their valuable comments .
cln2 is the predicted gene ; swi5 , cln1 and cdc28 are the explaining genes .
expression thresholds of the respective explaining genes mark all the arcs . the network of gene interactions constructed using the decision rules for the cdc15 dataset ( see table 2 ) .
the network is a graphical representation of the information comprised in the extracted decision rules .
every node in this graph represents a gene and every arc indicates the relation between the genes defined by the corresponding decision rule . note the existence of two separate modules in the constructed network .
the list of genes considered classification rules with high accuracy in all three accuracy tests ( cv-10 and cdc28 , alpha - factor test sets ) are shown in the upper part of the table .
questionable rules ( see classification rules for explanation ) are shown in the lower part of the table .
accuracy of final classifiers for ' simultaneous ' events in the cdc15 dataset estimates are shown for c4.5 by quinlan with wrappers by kohavi on the cdc15 dataset with continuous features discretized by the fayyad and irani method .
10-cv , 10-fold cross - validation ; cdc28 and  , accuracy estimations where cdc8 and alpha - factor datasets were used as test sets .
 one of the most important problems in gene network reconstruction is finding , for each gene in the network , which genes can affect it . 
 a supervised learning approach was used to address this question in budding yeast by building decision - tree - related classifiers , which predict gene expression from the expression data of other genes . 
Background
Results
Definitions
Classification rules
Discussion
Conclusions
Materials and methods
Additional data files
Supplementary Material
Acknowledgements
Figures and Tables