BACKGROUND
the temporal and spatial coordination of gene expression patterns is the result of a complex integration of regulatory signals at the promotor of target genes  <cit> .
in the last years numerous methods have been developed and applied to reconstruct the structure and dynamic rules of gene-regulatory networks from different high-throughput data sources, mainly microarray based gene expression analysis, promotor sequence information, chromatin immunoprecipitation  and protein-protein interaction assays  <cit> .
popular reconstruction methods include bayesian networks  <cit> , robust regression  <cit> , partial correlations  <cit> , mutual information  <cit>  and system-theoretic approaches  <cit> .
approaches using gene expression data either focus on static data or on time series of gene expression.
the later approach has the advantage of being able to identify causal relations, i.e.
gene-regulatory relations, between genes without the need of actively perturbing the system.
the reconstruction of gene networks is in general complicated by the high dimensionality of high-throughput data, i.e.
many genes are measured in parallel, with only few replicates per gene.
together with observational noise, these complications impose a limit on the reconstruction of gene networks  <cit> .
in this study we focus on the following three challenges that a reconstruction of gene-regulatory networks from time series of gene expression data is facing.
• the quality of data derived from high-throughput gene expression experiments is largely limited by noise.
for example the typical magnitude of observational noise in microarray measurements is about 20–30% of the signal  <cit> .
in high-throughput techniques dynamical noise maybe expected to play a minor role due to the underlying population sampling of the data.
in contrast, data derived from gene expression at the single cell level can exhibit a significant amount of dynamical noise as well as strong cell to cell variations  <cit> .
• data size, i.e.
length of a time series and number of replicates, is limited by the cost of experiments.
the typical length of time series measurements in microarray studies is around 10– <dig> time points  <cit>  and 3– <dig> replicates.
therefore, any model underlying network reconstruction methods must be simple, i.e.
contain as few parameters as possible, and robust.
• gene regulation is due to the activity of transcription factors  which is in most cases post-translationally controlled by additional factors.
this activity is not directly observed by measuring tf expression levels.
however, many network reconstruction methods based on time series assume the activity of tfs to be directly related with their expression levels, thereby omitting additional hidden variables  <cit> .
accounting for hidden variables in the framework of network reconstruction methods based on time series demands more data in order to estimate the additional parameters and can complicate a biological interpretation of the hidden variables  <cit> .
a systematic study requires data of several gene regulatory networks where the structure is known in detail.
since no experimental data fulfilling these requirements is currently available we use an ensemble of synthetic gene regulatory networks to generate gene expression data.
this approach allows us to investigate in depth the effect of noise, data size and hidden variables in the form of unobserved processes on the reconstruction of gene regulatory networks.
we evaluate three methods for the reconstruction of gene regulatory networks from time series which are either based on a discrete or a continuous representation of the network states: discrete dynamic bayesian networks , linear gaussian dbns and linear regression in combination with variable selection.
all these techniques have been used in former studies, however a comparison of the three methods using temporal gene expression data is missing so far.
time series can be measured under different experimental conditions including changes in the culture conditions or perturbations of network components by gene knock-outs .
for example the time series experiments conducted by spellman et al.
generated data under different culture conditions and using different mutant backgrounds in order to reveal a more comprehensive picture about gene regulation during the yeast cell cycle  <cit> .
we study different experimental design strategies in order to identify optimal experiments for the identification of the underlying network structure.
additionally, we investigate the requirements on data size and data quality that must be met by a successful network reconstruction.
beside gene expression data, other data sources or a combination of them can be called in to reveal the structure of gene-regulatory networks.
these data sources include chromatin immuno-precipitation  experiments, promoter analysis and protein-protein interaction assays.
within a bayesian learning framework, these additional data sources can be incorporated as prior knowledge.
for example p-values of tf-dna interactions given by chip experiments have been applied as prior knowledge about gene-gene interactions  <cit> .
here, we investigate the influence of prior knowledge on the reconstruction of gene-regulatory networks.
we present a model for prior knowledge based on probabilities for gene-gene interactions.
the model is used to generate prior knowledge with different levels of accuracy.
the accuracy of the inferred networks is compared to the accuracy of the prior knowledge using different amounts of gene expression data.
this allows us to identify conditions when the use of prior knowledge can improve the prediction accuracy.
in a typical study of a gene-regulatory network the states of many molecular components of the network are not observed, such as the phosphorylation-level of proteins or their cellular localization.
using synthetic gene-regulatory networks enables us to study the effect of unobserved processes on the network reconstruction by artificially hiding subsets of the complete data, such as protein levels and promotor states.
we investigate the influence of these unobserved states on the identification of the network structure by time series experiments and gene kos.
the paper is organized as follows.
in the first section the generation of the different data sets from an ensemble of  <dig> synthetic networks is explained.
in the second section the reconstruction of the gene networks using linear gaussian dbns is studied.
here, we also focus on the optimal type of biological experiment in order to identify the underlying network structure.
in section three two alternative network reconstruction methods, discrete dbns and variable selection based on f-statistics, are evaluated and compared with linear gaussian dbns.
section four studies the impact of data sizes and observational noise.
in section five we investigate the network reconstruction based on prior knowledge and gene expression data.
in the last section the effect of unobserved processes, e.g.
protein-protein and protein-dna interactions, on the structure and identification of gene-gene interaction networks is studied.
RESULTS
data generation and evaluation
in order to evaluate the performance of the different network reconstruction methods we generate an ensemble of  <dig> synthetic networks.
this approach allows us to evaluate the average performance of a method without biasing the evaluation in favor of a single network or network feature.
each network consists of  <dig> genes of which  <dig> are tfs and  <dig> are pure target genes.
a tf can itself be target gene while a pure target gene is not allowed as a transcriptional regulator of another gene.
the distinction between transcriptional regulator and pure target gene allows us to substantially reduce the possible number of regulatory interactions and with it the amount of data needed to identify them.
our approach is also applicable in situations where the total number of genes is much larger compared to the number of involved transcriptional regulators as the computational cost of the network reconstruction methods applied scale linearly with the number of pure target genes .
continuous gene expression data is generated by simulating the network dynamics with non-linear odes .
observational error is incorporated via an additive-multiplicative error model  <cit> .
this error model corresponds with a first order approximation to log-normal distributed expression levels  <cit> .
in order to identify the optimal data type and experiment for the identification of the underlying network structure we apply different simulation scheme.
either random perturbations from steady state or specific perturbations of the steady state by tf kos are simulated and time series are sampled during relaxation of the network back to steady state.
in order to apply discrete dbns to the continuous data obtained from odes the data is subsequently discretized.
among different discretization scheme we choose binary quantile discretization for which we observe the lowest error rates of the reconstructed networks.
for the evaluation of discrete dbns we also simulate the networks with probabilistic boolean logic resulting in binary gene expression data.
the effect of hidden variables is investigated using a 54-dimensional network of non-linear odes which models the interaction of  <dig> genes with their respective promotor, mrna and protein states  <cit> .
as above, we generate time series data by single gene kos and subsequent sampling during relaxation to a new steady state.
however, we use only the mrna data in order to reconstruct the gene-gene interaction network.
this approach corresponds to a microarray experiment where the promotor or protein states are not observed.
based on the studied question, we use two alternative approaches for the evaluation of the reconstructed networks.
in the first three sections we evaluate our results by calculating three error rates which are based on an edge-wise comparison of the best reconstructed network with the true network:  the false negative rate  gives the percentage of missed edges from all true edges.
the false positive rate  gives the percentage of predicted edges from all false edges.
the realized false discovery rate  gives the percentage of false edges among the predicted edges .
in the last two sections we study the effect of prior knowledge and hidden variables.
here, mcmc simulations are applied in order to calculate posterior probabilities for single gene-gene interactions .
receiver operating characteristic  curves and the corresponding area under the roc curve are used as a measure for the overall accuracy of the network reconstruction based on mcmc simulations.
reconstruction of gene networks using linear gaussian dbns
we start our investigation by evaluating the reconstruction of  <dig> gene regulatory networks using linear gaussian dbns.
figure  <dig> shows box plots of the three error rates of network reconstruction based on data of a single time series for each network.
each time series is generated by a random perturbation of the corresponding network from its steady state and consists of  <dig> data points per gene.
the observational noise level is 2%.
as indicated by the high error rates, the average network reconstruction from this data sets is very poor.
almost 60% of the predicted edges are wrong ), while only 30% of the true interactions are also predicted ).
most of the network structures cannot be identified although the temporal resolution of the underlying data is relatively high due to a high sampling rate.
in figure  <dig> we change the sampling rate and the number of replicates.
here, for each network we generate  <dig> time series with  <dig> data points each as opposed to the previous approach where one time series with  <dig> data points per network is used.
thus, the total size of the data is equivalent in both approaches.
however, for each of the  <dig> time series the steady states of the networks are perturbed independently.
the resulting error rates are considerably smaller.
only about 30% of the predicted edges are wrong while about 50% of all true edges are also discovered.
these results clearly indicate that several random perturbations contain more information about the gene regulatory interactions compared to a single time series with an equivalent data size, i.e.
with a higher sampling rate.
in general perturbations are necessary to push the gene regulatory network out of its steady state.
however, a single perturbation of all genes is unlikely to reveal the regulatory impact of all tfs onto their target genes as some of these tfs will be perturbed in a similar manner.
therefore several uncorrelated perturbations are necessary to distinguish between the regulatory impact of each tf onto its target genes.
however, conducting several independent, random perturbation of all the components of a gene-regulatory network is not experimentally feasible.
moreover, perturbations which change the structure and function of the underlying network unspecifically should be avoided.
we therefore study specific perturbations of the gene regulatory networks in the form of tf knock-outs .
each of the  <dig> tfs in the  <dig> synthetic networks is knocked out separately and time series are sampled while the system relaxes back to its new steady state.
the resulting error rates of the network reconstructions are shown in figure  <dig>  all three error rates are significantly smaller  compared to the error rates based on random perturbations as shown in figure  <dig>  on average only 20% of the predicted edges are wrong while almost 60% of all true interactions are discovered.
thus, specific tf kos additionally improve the identification of the network structures.
the additional gain over random perturbations as in figure  <dig> can be explained by the specificity of the tf kos.
the perturbations applied in figure  <dig> change the levels of all genes at the same time and do not reveal the specific impact of a single tf.
in contrast, our results indicate that a perturbation by tf kos gives the required specificity in order to reveal the regulatory connections between the genes.
depending on the biological system studied, several tf kos represent a considerable experimental effort in order to achieve independent and specific perturbations of the biological system.
high-throughput rnai based gene kos are an attractive possibility to generate the data required for a successful reconstruction of gene-regulatory networks  <cit> .
in a study based on static bayesian networks werhli et al.
<cit>  come to a similar the conclusion.
they show that active interventions improve the identification of the network structure over an inference solely based on passive observations.
here, active interventions are necessary in order to resolve the ambiguity of certain edge directions intrinsic to the inference of network structures based on static and passive observations.
active interventions can break the symmetry of correlations between nodes in a network and identify the causal, i.e.
assymmetric, relation between the nodes.
it is important to note that the improvement due to tf kos we observe is not due to a similar phenomenon as observed by werhli et al.
for static bayesian networks.
all edges in the dbns we apply are directed in time and represent causal relations per se.
the gain of tf kos over a single replicate time series as in figure  <dig> is only due to the larger number of independent replicates in the form of specific perturbations of the underlying network.
this can be already seen by the improvements of the error rates from figure  <dig> to  <dig>
reconstruction of gene networks with alternative methods: discrete dbns and variable selection
in this section we compare linear gaussian dbns to more commonly used and related methods to reconstruct gene regulatory networks from time series.
first, we focus on discrete dbns.
the data underlying figure  <dig> is discretized prior to the application of discrete dbns.
we use a binary quantile discretization.
the resulting error rates are shown in figure  <dig>  it turns out that the overall performance of discrete dbns is rather poor compared with the performance of linear gaussian dbns on the corresponding continuous data.
the average fdr is 50% meaning that half of the predicted edges are wrong.
only about 25% of all true gene-gene interactions are also identified.
both error rates are considerably higher than the corresponding error rates of linear gaussian dbns  and figure 2).
these results suggest that discretization of the continuous data leads to a large information loss.
in order to improve our results we also tested a different discretization method, i.e.
ternary quantile discretization in combination with an information preserving coalescence of discretization levels  <cit> .
we observe no significant improvement between the corresponding fdrs .
data discretization leads to a qualitative and coarse representation of the dynamics.
different time scales of the dynamics cannot be reflected without considering a finer sampling rate and a higher number of discretization levels.
however, more discretization levels also require an increase in data size in order to identify all the necessary parameters of the corresponding multinomial conditional probability distributions.
for the data sizes and networks studied, we observe a considerably better performance of linear gaussian dbns compared to discrete dbns despite the fact that linear gaussian dbns make stronger assumptions about the underlying dynamics.
we therefore conclude that the advantage of discrete dbns to capture also non-linear effects can only be utilized with much larger data sizes than we consider and that are usually available in a time series microarray experiment.
alternative to the discretization of continuous data is the simulation of the network dynamics by probabilistic boolean logic.
we simulate the dynamics by applying simple activation and inhibition rules to the regulation of a gene and combine the regulation by different tfs in a logic or gate.
we also incorporate dynamical noise into the simulation in form of random switches in the outcome of the regulatory rules .
in figure  <dig> we show the corresponding error rates based on the network reconstruction from boolean data.
as one can see, the overall performance of discrete dbns on boolean data has much improved.
especially the average fdr is very low, i.e.
about 10%.
the fnr indicates that 55% of all true edges are identified on average.
these results are considerably better than the performance of discrete dbns on the discretized data in figure  <dig> and the fpr and fdr are significantly better as the corresponding rates of linear gaussian dbns on the continuous data in figure  <dig> .
these results might question which of the two modeling frameworks, continuous odes or boolean logic in combination with dynamical noise, accurately reflect cellular dynamics?
boolean networks are a very crude representation of the time-continuous cellular dynamics underlying gene regulatory networks.
especially the different time scales involved in the regulation of genes cannot be described by boolean networks without considering additional hidden variables.
in contrast, non-linear odes are a natural framework for the description of cellular processes as they incorporate time scales as well as the concentration of transcripts directly.
the consideration of dynamical noise is important in order to understand the dynamics on a single cell level  <cit> .
here, dynamical noise can play a role due to the low concentrations of molecular species and random thermal fluctuations of the cellular environment.
additionally, cell to cell variations in the kinetic parameters, e.g.
induced by variable expression levels of the enzymes, are important.
however, high-throughput techniques based on population sampling cannot reveal a single cell resolution in a time series.
here, observational noise plays the dominant role.
based on our results we suggest the use of linear gaussian dbns as they better fit the data generated by high-throughput experiments.
next we investigated an alternative network reconstruction method that can be applied to continuous time series data: variable selection based on f-statistics.
the method we use is based on a linear regression of the tf expression levels at time t against the expression levels of each target gene at time t +  <dig>  in an repetitive step-wise selection and elimination procedure a set of optimal predictors, i.e.
tfs, is build for each target gene according to a partial f-test.
the tf with the significantly highest partial correlation coefficient is included in the set of predictors, while the tf in the set with the lowest, non-significant partial correlation coefficient is excluded.
this step-wise selection procedure leads to a local optimization of the set of tfs for each gene.
figure  <dig> shows the corresponding error rates of the networks reconstructed by variable selection based on the data underlying figure  <dig>  all three error rates are on average similar to the error rates of the reconstruction using linear gaussian dbns.
the average fnr is 50%, thus about half of the true gene-gene interactions are identified.
at the same time about 15% false interactions are predicted.
the overall good performance of the variable selection procedure seen in figure  <dig> can be attributed to the relatively large data size  and the limited number of regressors  as well as the simplicity of the regulatory model which excludes any interactions between tfs.
it is important to note, that the realized error rates are governed by the parameters of the f-statistics and the significance level α of the partial correlations between the expression levels of tfs and target genes in the final network.
in the given example α ≤  <dig>  is chosen to give a fnr comparable with figure  <dig>  larger significance levels lead to a larger fpr and fdr.
thus, in order to get low error rates only tfs with a small p-value are included in the network.
one has to keep in mind that a clear interpretation of the p-values is not possible due to the problem of multiple testing.
the effect of data size and noise
in this section we investigate the impact of data size and observational noise on the reconstruction of gene regulatory networks by linear gaussian dbns.
figure  <dig> shows the average fnrs and fdrs of the reconstruction of  <dig> networks with respect to data size and different observational noise levels.
as in figure  <dig>  the underlying data is generated by single ko experiments of all  <dig> tfs of a given network.
the data size is varied by using different sampling rates in the tf ko experiments.
on the x-axis of figure  <dig> the length of the time series of a single tf ko experiment is given.
a time series of length  <dig> indicates a total data size of  <dig> time points per gene, i.e.
<dig> data points per time series ×  <dig> tf ko experiments.
as expected, the error rates increase with the noise level but decrease with data size.
conducting  <dig> tf ko experiments each with  <dig> data points per gene leads to a fdr of about 50% given a measurement error in the order of 20%.
the fdr can be lowered in two ways.
a fdr of 40% is achieved either by halving the measurement error to 10% or by measuring longer time series, i.e.
<dig> data points per gene.
as the measurement error is intrinsic to the experimental method, our results can be interpreted as an estimate for the required number of data points per gene needed in order to identify a network structure of a certain quality.
it is important to note that the tf ko experiments underlying figure  <dig> represent an optimal experimental design for the identification of the true network structure.
as mentioned above, a single time series of an equivalent data size contain much less information about the underlying network structure.
therefore our estimates represent only a lower bond for the required number of data points per gene if other design strategies are used.
realistic observational noise levels of microarray experiments are in the order of 20%–30% of the signal  <cit>  while the data size of time series experiments usually range from 10– <dig> time points per gene  <cit> .
our results indicate, that network reconstruction with currently available data will still give rise to many false predictions .
the influence of prior knowledge
prior knowledge can potentially improve the accuracy of the inferred networks  <cit> .
however, the degree of improvement depends on the quality of the prior knowledge as well as the amount of available gene expression data.
in this section we investigate the benefits of the use of prior knowledge in form of prior probabilities for gene-gene interactions within a bayesian learning scheme.
we compare the accuracy of a network reconstruction based on prior knowledge alone with the accuracy of a reconstruction based on the corresponding posterior probabilities calculated by mcmc simulations.
this enables us to predict under what circumstances, i.e.
quality of the prior, amount of gene expression data, the use of prior knowledge can be a benefit for the reconstruction of gene regulatory networks.
we develop a simple model where the prior knowledge is given by the probability of a gene-gene interaction based on two probability distributions for true and false interactions respectively.
the model is depicted in figure  <dig>  the prior interaction probabilities are drawn from two truncated normal distributions, x ± ~ n ±  where n+ is the probability distribution for true interactions and n- is the probability distribution for false interactions.
the parameters μ is set to  <dig>  and the standard deviation σ is set to  <dig> .
the accuracy of the prior knowledge is controlled by the parameter δ which is used to separate the means of both distributions.
we use the model to generate prior probabilities for a subset of  <dig> networks each consisting of  <dig> genes.
the accuracy of the prior knowledge is calculated using receiver operating characteristic  curves.
roc curves display the tpr in dependence of the fpr.
the tpr and fpr are determined in dependence of a prediction threshold for the prior probabilities; edges with a probability above the threshold are included in the network.
the accuracy corresponds with the area under the roc curve .
a random prediction has an accuracy of  <dig>  meaning that on average the prediction cannot distinguish between true and false edges.
it is interesting to compare whether the posterior networks are always of a higher accuracy compared to the accuracy of the prior networks.
figure  <dig> depicts the average accuracy of the prior networks versus the average accuracy of the posterior networks for different data sizes.
points above the dashed line show an increase in accuracy of the posterior networks relative to the accuracy of the prior networks.
points below the dashed line indicate a respective decrease in accuracy.
the four curves in figure  <dig> depict the dependency between prior and posterior accuracy for four different data sizes.
the bisecting line indicates the situation when no gene expression data is used: prior and posterior accuracy are the same.
if gene expression data is included the slope of the curves decreases from one.
this can be explained by the fact that the posterior probability of a network structure is given by the product of the prior and the likelihood .
as the prior is data-independent and the likelihood is proportional to the data size, the impact of the prior onto the posterior decreases with data size.
this implies, that the slope of the curves decrease with larger data sizes.
this can be seen in figure  <dig> by comparing the slopes of the curve corresponding to  <dig> and  <dig> data points.
the slope of the curve will approach one in the limit of small gene expression data as in this case the likelihood of the data will also approach one.
the average accuracy of the networks predicted by gene expression data alone, i.e.
by using an uninformative prior, corresponds with the leftmost points in the graph.
for example the average accuracy of networks predicted by using  <dig> data points per gene is 68%.
this prediction can be increased by using more informative priors.
however, this increase in accuracy is relatively weak as indicated by the slope of the curves.
once the curves cross the dashed line, prior knowledge alone gives a better prediction than a combination of prior knowledge and gene expression data.
this indicates that the use of a combination of prior knowledge and gene expression data within a bayesian learning framework is not always of an advantage.
only situations where the amount of gene expression data is very limited can show a considerable increase in accuracy by the use of prior knowledge.
however, under these data situations a prediction based on the prior knowledge alone might lead to more accurate networks.
as the prior and posterior accuracy cannot be determined using real data, it is not possible to decide whether a combination of prior knowledge and gene expression data will give any benefit.
our results indicate that the overall gain by combining data in a bayesian learning framework, i.e.
data situations corresponding to points above the dashed line in figure  <dig>  is limited.
nevertheless, prior knowledge can be of a benefit in the reconstruction of networks from time series.
it can be used to restrict the number of possible gene-gene interactions, e.g.
by allowing gene-gene interactions only between tfs and target genes which have a significant prior probability.
this improves heuristic search procedures as it restricts the space of the possible posterior models .
however, if detailed information on the promotor structure is available, alternative approaches which do not use the temporal information of the gene expression data explicitly are even more appropriate  <cit> .
the effect of hidden variables
a gene-regulatory network is always integrated into a larger biochemical network which also includes proteins, small signalling molecules and regulated transport between cellular compartments.
these processes and quantities are usually not resolved or measured parallel to expression studies, i.e.
they are hidden to the experimentator.
we study the effect of hidden variables using a gene-regulatory network developed by  <cit>  which is based on a coupled system of odes for  <dig> variables including mrnas, proteins and promotors.
figure  <dig> shows the structure of the gene-gene interaction network as given in  <cit> .
nodes in the graph represent genes, solid edges represent interactions based on direct transcriptional regulation, i.e.
the mrna product of the gene is a tf which binds to the promoter of the respective target gene and regulates its expression whereas the dotted edges represent protein-protein interactions.
all the depicted interactions are indirect in the system of odes, since the interaction between genes is communicated by their products and promotor states.
thus, figure  <dig> is an abstraction of the underlying physical model.
since our network reconstruction method assumes direct dependencies via the first order markov assumption of fully-observed dbns, we cannot expect that the recovered structure resembles the network in figure  <dig>  but we can deduce a more realistic reference network from the system of odes.
all direct interactions in the system of odes are defined by the structure of corresponding jacobian matrix.
this structure can be used to deduce an interaction graph for the subset of observed variables, i.e.
mrnas .
figure  <dig> displays the structure of the model reduced to the observed mrna components.
again, all shown interactions in the network are indirect.
interpreting mrna nodes as gene nodes, all interactions present in figure  <dig> are also present in figure  <dig>  however, many more indirect interactions arise.
all of them have a clear physical justification: a change in the level of one mrna directly influences the levels of the corresponding target mrnas.
therefore, the edges in the network of figure  <dig> correspond either to direct transcriptional regulation ) or indirect regulation due to unobserved processes.
because of the first order markov assumption underlying our method we expect, that all of the edges in figure  <dig> can be recovered by a network reconstruction based on time series data.
our results indicate that networks reconstructed from time series gene expression data can contain many regulatory interactions which are not based on direct transcriptional regulation, but reflect regulation due to unobserved processes, e.g.
protein-protein interactions.
a biological example of a process, unobserved in microarray experiments that is crucial for the regulation of target genes involves the swi4/swi <dig>  controlled transcription of g1-specific genes during the yeast cell cycle.
phosphorylation of the sbf repressor whi <dig> by cln3/cdk <dig> leads to a derepression of g1-specific transcription  <cit> .
the transcriptional activity of the sbf complex is not determined by the expression level of its components.
in terms of reconstructing gene networks this means that the first order markov assumption of dbns, i.e.
a relation between the expression level of a transcription factor and its regulatory potential, is not fulfilled due to hidden variables.
alternative approaches include hidden variables directly into their model in order to increase the prediction accuracy  <cit> .
however, a clear biological interpretation of these additional variables is difficult, as the nature and number of the hidden variables is usually unknown.
the hidden activity of tfs can be revealed by relating tf binding sites in promotor regions of target genes with the expression levels of the target genes  <cit> .
the crucial difference between these approaches and the approach studied in this paper is that the former group genes with similar tf binding sites and use their expression levels as measurement replicates for the reconstruction of the hidden tf activity.
these approaches have less requirements on the number of data points per gene, but are only applicable if additional information about the promotor structure of genes is available.
also, temporal information is not explicitly used.
in order to reconstruct directed gene regulatory networks, i.e.
networks that distinguish between regulator and target, from gene-expression data alone, either time series experiments, several gene ko experiments or, as indicated by this study, a combination of both must be conducted.
however, our results indicate an inherent limitation to the reconstruction of gene-gene networks by gene expression data alone as the recovered edges between genes do not necessarily reflect direct transcriptional regulations.
CONCLUSIONS
in this study we identify suitable reconstruction methods, types of experiments and requirements on data size and quality in order to reverse engineer gene regulatory networks from time series data.
our results suggest that linear gaussian dbns and variable selection are both appropriate methods to reconstruct the network structure from time series of gene expression data.
discrete dbns are well suited for the reconstruction of probabilistic boolean networks.
however, we find that their ability to reconstruct networks from discretized gene expression data is limited by their higher requirements on data size.
in order to optimally identify the structure of gene-regulatory networks we show that experimental data should be generated while specifically perturbing the underlying network.
we suggest tf kos as specific perturbations that allow a network reconstruction from relatively short time series.
the trade-off between observational noise and data size is described and estimates for the amount of data needed in order to reconstruct accurate networks given a certain level of observational noise are provided.
for example at least  <dig> data points per gene are necessary in order to perform better than a random prediction given observational noise levels of 20% which corresponds with the noise level of data commonly derived from microarray measurements.
we identify conditions under which prior knowledge can improve the prediction accuracy.
the benefit of prior knowledge within a bayesian learning framework is limited to a particular data setting where only a small amount of gene expression data is available.
we show that unobserved cellular processes lead to the reconstruction of regulatory relations between genes which are not based on direct transcriptional regulation.
the ambiguity of the regulatory relations represent an inherent limitation to the reconstruction of gene-regulatory networks from time series of gene expression.

 the temporal and spatial coordination of gene expression patterns is the result of a complex integration of regulatory signals at the promotor of target genes. in the last years numerous methods have been developed and applied to reconstruct the structure and dynamic rules of gene-regulatory networks from different high-throughput data sources, mainly microarray based gene expression analysis, promotor sequence information, chromatin immunoprecipitation and protein-protein interaction assays. popular reconstruction methods include bayesian networks, robust regression, partial correlations, mutual information and system-theoretic approaches. approaches using gene expression data either focus on static data or on time series of gene expression. the later approach has the advantage of being able to identify causal relations, i.e. gene-regulatory relations, between genes without the need of actively perturbing the system. the reconstruction of gene networks is in general complicated by the high dimensionality of high-throughput data, i.e. many genes are measured in parallel, with only few replicates per gene. together with observational noise, these complications impose a limit on the reconstruction of gene networks. in this study we focus on the following three challenges that a reconstruction of gene-regulatory networks from time series of gene expression data is facing. • the quality of data derived from high-throughput gene expression experiments is largely limited by noise. for example the typical magnitude of observational noise in microarray measurements is about 20–30% of the signal. in high-throughput techniques dynamical noise maybe expected to play a minor role due to the underlying population sampling of the data. in contrast, data derived from gene expression at the single cell level can exhibit a significant amount of dynamical noise as well as strong cell to cell variations. • data size, i.e. length of a time series and number of replicates, is limited by the cost of experiments. the typical length of time series measurements in microarray studies is around 10– time points and 3– replicates. therefore, any model underlying network reconstruction methods must be simple, i.e. contain as few parameters as possible, and robust. • gene regulation is due to the activity of transcription factors which is in most cases post-translationally controlled by additional factors. this activity is not directly observed by measuring tf expression levels. however, many network reconstruction methods based on time series assume the activity of tfs to be directly related with their expression levels, thereby omitting additional hidden variables. accounting for hidden variables in the framework of network reconstruction methods based on time series demands more data in order to estimate the additional parameters and can complicate a biological interpretation of the hidden variables. a systematic study requires data of several gene regulatory networks where the structure is known in detail. since no experimental data fulfilling these requirements is currently available we use an ensemble of synthetic gene regulatory networks to generate gene expression data. this approach allows us to investigate in depth the effect of noise, data size and hidden variables in the form of unobserved processes on the reconstruction of gene regulatory networks. we evaluate three methods for the reconstruction of gene regulatory networks from time series which are either based on a discrete or a continuous representation of the network states: discrete dynamic bayesian networks, linear gaussian dbns and linear regression in combination with variable selection. all these techniques have been used in former studies, however a comparison of the three methods using temporal gene expression data is missing so far. time series can be measured under different experimental conditions including changes in the culture conditions or perturbations of network components by gene knock-outs. for example the time series experiments conducted by spellman et al. generated data under different culture conditions and using different mutant backgrounds in order to reveal a more comprehensive picture about gene regulation during the yeast cell cycle. we study different experimental design strategies in order to identify optimal experiments for the identification of the underlying network structure. additionally, we investigate the requirements on data size and data quality that must be met by a successful network reconstruction. beside gene expression data, other data sources or a combination of them can be called in to reveal the structure of gene-regulatory networks. these data sources include chromatin immuno-precipitation experiments, promoter analysis and protein-protein interaction assays. within a bayesian learning framework, these additional data sources can be incorporated as prior knowledge. for example p-values of tf-dna interactions given by chip experiments have been applied as prior knowledge about gene-gene interactions. here, we investigate the influence of prior knowledge on the reconstruction of gene-regulatory networks. we present a model for prior knowledge based on probabilities for gene-gene interactions. the model is used to generate prior knowledge with different levels of accuracy. the accuracy of the inferred networks is compared to the accuracy of the prior knowledge using different amounts of gene expression data. this allows us to identify conditions when the use of prior knowledge can improve the prediction accuracy. in a typical study of a gene-regulatory network the states of many molecular components of the network are not observed, such as the phosphorylation-level of proteins or their cellular localization. using synthetic gene-regulatory networks enables us to study the effect of unobserved processes on the network reconstruction by artificially hiding subsets of the complete data, such as protein levels and promotor states. we investigate the influence of these unobserved states on the identification of the network structure by time series experiments and gene kos. the paper is organized as follows. in the first section the generation of the different data sets from an ensemble of synthetic networks is explained. in the second section the reconstruction of the gene networks using linear gaussian dbns is studied. here, we also focus on the optimal type of biological experiment in order to identify the underlying network structure. in section three two alternative network reconstruction methods, discrete dbns and variable selection based on f-statistics, are evaluated and compared with linear gaussian dbns. section four studies the impact of data sizes and observational noise. in section five we investigate the network reconstruction based on prior knowledge and gene expression data. in the last section the effect of unobserved processes, e.g. protein-protein and protein-dna interactions, on the structure and identification of gene-gene interaction networks is studied.  data generation and evaluation in order to evaluate the performance of the different network reconstruction methods we generate an ensemble of synthetic networks. this approach allows us to evaluate the average performance of a method without biasing the evaluation in favor of a single network or network feature. each network consists of genes of which are tfs and are pure target genes. a tf can itself be target gene while a pure target gene is not allowed as a transcriptional regulator of another gene. the distinction between transcriptional regulator and pure target gene allows us to substantially reduce the possible number of regulatory interactions and with it the amount of data needed to identify them. our approach is also applicable in situations where the total number of genes is much larger compared to the number of involved transcriptional regulators as the computational cost of the network reconstruction methods applied scale linearly with the number of pure target genes. continuous gene expression data is generated by simulating the network dynamics with non-linear odes. observational error is incorporated via an additive-multiplicative error model. this error model corresponds with a first order approximation to log-normal distributed expression levels. in order to identify the optimal data type and experiment for the identification of the underlying network structure we apply different simulation scheme. either random perturbations from steady state or specific perturbations of the steady state by tf kos are simulated and time series are sampled during relaxation of the network back to steady state. in order to apply discrete dbns to the continuous data obtained from odes the data is subsequently discretized. among different discretization scheme we choose binary quantile discretization for which we observe the lowest error rates of the reconstructed networks. for the evaluation of discrete dbns we also simulate the networks with probabilistic boolean logic resulting in binary gene expression data. the effect of hidden variables is investigated using a 54-dimensional network of non-linear odes which models the interaction of genes with their respective promotor, mrna and protein states. as above, we generate time series data by single gene kos and subsequent sampling during relaxation to a new steady state. however, we use only the mrna data in order to reconstruct the gene-gene interaction network. this approach corresponds to a microarray experiment where the promotor or protein states are not observed. based on the studied question, we use two alternative approaches for the evaluation of the reconstructed networks. in the first three sections we evaluate our results by calculating three error rates which are based on an edge-wise comparison of the best reconstructed network with the true network: the false negative rate gives the percentage of missed edges from all true edges. the false positive rate gives the percentage of predicted edges from all false edges. the realized false discovery rate gives the percentage of false edges among the predicted edges. in the last two sections we study the effect of prior knowledge and hidden variables. here, mcmc simulations are applied in order to calculate posterior probabilities for single gene-gene interactions. receiver operating characteristic curves and the corresponding area under the roc curve are used as a measure for the overall accuracy of the network reconstruction based on mcmc simulations. reconstruction of gene networks using linear gaussian dbns we start our investigation by evaluating the reconstruction of gene regulatory networks using linear gaussian dbns. figure shows box plots of the three error rates of network reconstruction based on data of a single time series for each network. each time series is generated by a random perturbation of the corresponding network from its steady state and consists of data points per gene. the observational noise level is 2%. as indicated by the high error rates, the average network reconstruction from this data sets is very poor. almost 60% of the predicted edges are wrong ), while only 30% of the true interactions are also predicted ). most of the network structures cannot be identified although the temporal resolution of the underlying data is relatively high due to a high sampling rate. in figure we change the sampling rate and the number of replicates. here, for each network we generate time series with data points each as opposed to the previous approach where one time series with data points per network is used. thus, the total size of the data is equivalent in both approaches. however, for each of the time series the steady states of the networks are perturbed independently. the resulting error rates are considerably smaller. only about 30% of the predicted edges are wrong while about 50% of all true edges are also discovered. these results clearly indicate that several random perturbations contain more information about the gene regulatory interactions compared to a single time series with an equivalent data size, i.e. with a higher sampling rate. in general perturbations are necessary to push the gene regulatory network out of its steady state. however, a single perturbation of all genes is unlikely to reveal the regulatory impact of all tfs onto their target genes as some of these tfs will be perturbed in a similar manner. therefore several uncorrelated perturbations are necessary to distinguish between the regulatory impact of each tf onto its target genes. however, conducting several independent, random perturbation of all the components of a gene-regulatory network is not experimentally feasible. moreover, perturbations which change the structure and function of the underlying network unspecifically should be avoided. we therefore study specific perturbations of the gene regulatory networks in the form of tf knock-outs. each of the tfs in the synthetic networks is knocked out separately and time series are sampled while the system relaxes back to its new steady state. the resulting error rates of the network reconstructions are shown in figure all three error rates are significantly smaller compared to the error rates based on random perturbations as shown in figure on average only 20% of the predicted edges are wrong while almost 60% of all true interactions are discovered. thus, specific tf kos additionally improve the identification of the network structures. the additional gain over random perturbations as in figure can be explained by the specificity of the tf kos. the perturbations applied in figure change the levels of all genes at the same time and do not reveal the specific impact of a single tf. in contrast, our results indicate that a perturbation by tf kos gives the required specificity in order to reveal the regulatory connections between the genes. depending on the biological system studied, several tf kos represent a considerable experimental effort in order to achieve independent and specific perturbations of the biological system. high-throughput rnai based gene kos are an attractive possibility to generate the data required for a successful reconstruction of gene-regulatory networks. in a study based on static bayesian networks werhli et al. come to a similar the conclusion. they show that active interventions improve the identification of the network structure over an inference solely based on passive observations. here, active interventions are necessary in order to resolve the ambiguity of certain edge directions intrinsic to the inference of network structures based on static and passive observations. active interventions can break the symmetry of correlations between nodes in a network and identify the causal, i.e. assymmetric, relation between the nodes. it is important to note that the improvement due to tf kos we observe is not due to a similar phenomenon as observed by werhli et al. for static bayesian networks. all edges in the dbns we apply are directed in time and represent causal relations per se. the gain of tf kos over a single replicate time series as in figure is only due to the larger number of independent replicates in the form of specific perturbations of the underlying network. this can be already seen by the improvements of the error rates from figure to reconstruction of gene networks with alternative methods: discrete dbns and variable selection in this section we compare linear gaussian dbns to more commonly used and related methods to reconstruct gene regulatory networks from time series. first, we focus on discrete dbns. the data underlying figure is discretized prior to the application of discrete dbns. we use a binary quantile discretization. the resulting error rates are shown in figure it turns out that the overall performance of discrete dbns is rather poor compared with the performance of linear gaussian dbns on the corresponding continuous data. the average fdr is 50% meaning that half of the predicted edges are wrong. only about 25% of all true gene-gene interactions are also identified. both error rates are considerably higher than the corresponding error rates of linear gaussian dbns and figure 2). these results suggest that discretization of the continuous data leads to a large information loss. in order to improve our results we also tested a different discretization method, i.e. ternary quantile discretization in combination with an information preserving coalescence of discretization levels. we observe no significant improvement between the corresponding fdrs. data discretization leads to a qualitative and coarse representation of the dynamics. different time scales of the dynamics cannot be reflected without considering a finer sampling rate and a higher number of discretization levels. however, more discretization levels also require an increase in data size in order to identify all the necessary parameters of the corresponding multinomial conditional probability distributions. for the data sizes and networks studied, we observe a considerably better performance of linear gaussian dbns compared to discrete dbns despite the fact that linear gaussian dbns make stronger assumptions about the underlying dynamics. we therefore conclude that the advantage of discrete dbns to capture also non-linear effects can only be utilized with much larger data sizes than we consider and that are usually available in a time series microarray experiment. alternative to the discretization of continuous data is the simulation of the network dynamics by probabilistic boolean logic. we simulate the dynamics by applying simple activation and inhibition rules to the regulation of a gene and combine the regulation by different tfs in a logic or gate. we also incorporate dynamical noise into the simulation in form of random switches in the outcome of the regulatory rules. in figure we show the corresponding error rates based on the network reconstruction from boolean data. as one can see, the overall performance of discrete dbns on boolean data has much improved. especially the average fdr is very low, i.e. about 10%. the fnr indicates that 55% of all true edges are identified on average. these results are considerably better than the performance of discrete dbns on the discretized data in figure and the fpr and fdr are significantly better as the corresponding rates of linear gaussian dbns on the continuous data in figure. these results might question which of the two modeling frameworks, continuous odes or boolean logic in combination with dynamical noise, accurately reflect cellular dynamics? boolean networks are a very crude representation of the time-continuous cellular dynamics underlying gene regulatory networks. especially the different time scales involved in the regulation of genes cannot be described by boolean networks without considering additional hidden variables. in contrast, non-linear odes are a natural framework for the description of cellular processes as they incorporate time scales as well as the concentration of transcripts directly. the consideration of dynamical noise is important in order to understand the dynamics on a single cell level. here, dynamical noise can play a role due to the low concentrations of molecular species and random thermal fluctuations of the cellular environment. additionally, cell to cell variations in the kinetic parameters, e.g. induced by variable expression levels of the enzymes, are important. however, high-throughput techniques based on population sampling cannot reveal a single cell resolution in a time series. here, observational noise plays the dominant role. based on our results we suggest the use of linear gaussian dbns as they better fit the data generated by high-throughput experiments. next we investigated an alternative network reconstruction method that can be applied to continuous time series data: variable selection based on f-statistics. the method we use is based on a linear regression of the tf expression levels at time t against the expression levels of each target gene at time t + in an repetitive step-wise selection and elimination procedure a set of optimal predictors, i.e. tfs, is build for each target gene according to a partial f-test. the tf with the significantly highest partial correlation coefficient is included in the set of predictors, while the tf in the set with the lowest, non-significant partial correlation coefficient is excluded. this step-wise selection procedure leads to a local optimization of the set of tfs for each gene. figure shows the corresponding error rates of the networks reconstructed by variable selection based on the data underlying figure all three error rates are on average similar to the error rates of the reconstruction using linear gaussian dbns. the average fnr is 50%, thus about half of the true gene-gene interactions are identified. at the same time about 15% false interactions are predicted. the overall good performance of the variable selection procedure seen in figure can be attributed to the relatively large data size and the limited number of regressors as well as the simplicity of the regulatory model which excludes any interactions between tfs. it is important to note, that the realized error rates are governed by the parameters of the f-statistics and the significance level α of the partial correlations between the expression levels of tfs and target genes in the final network. in the given example α ≤ is chosen to give a fnr comparable with figure larger significance levels lead to a larger fpr and fdr. thus, in order to get low error rates only tfs with a small p-value are included in the network. one has to keep in mind that a clear interpretation of the p-values is not possible due to the problem of multiple testing. the effect of data size and noise in this section we investigate the impact of data size and observational noise on the reconstruction of gene regulatory networks by linear gaussian dbns. figure shows the average fnrs and fdrs of the reconstruction of networks with respect to data size and different observational noise levels. as in figure the underlying data is generated by single ko experiments of all tfs of a given network. the data size is varied by using different sampling rates in the tf ko experiments. on the x-axis of figure the length of the time series of a single tf ko experiment is given. a time series of length indicates a total data size of time points per gene, i.e. data points per time series × tf ko experiments. as expected, the error rates increase with the noise level but decrease with data size. conducting tf ko experiments each with data points per gene leads to a fdr of about 50% given a measurement error in the order of 20%. the fdr can be lowered in two ways. a fdr of 40% is achieved either by halving the measurement error to 10% or by measuring longer time series, i.e. data points per gene. as the measurement error is intrinsic to the experimental method, our results can be interpreted as an estimate for the required number of data points per gene needed in order to identify a network structure of a certain quality. it is important to note that the tf ko experiments underlying figure represent an optimal experimental design for the identification of the true network structure. as mentioned above, a single time series of an equivalent data size contain much less information about the underlying network structure. therefore our estimates represent only a lower bond for the required number of data points per gene if other design strategies are used. realistic observational noise levels of microarray experiments are in the order of 20%–30% of the signal while the data size of time series experiments usually range from 10– time points per gene. our results indicate, that network reconstruction with currently available data will still give rise to many false predictions. the influence of prior knowledge prior knowledge can potentially improve the accuracy of the inferred networks. however, the degree of improvement depends on the quality of the prior knowledge as well as the amount of available gene expression data. in this section we investigate the benefits of the use of prior knowledge in form of prior probabilities for gene-gene interactions within a bayesian learning scheme. we compare the accuracy of a network reconstruction based on prior knowledge alone with the accuracy of a reconstruction based on the corresponding posterior probabilities calculated by mcmc simulations. this enables us to predict under what circumstances, i.e. quality of the prior, amount of gene expression data, the use of prior knowledge can be a benefit for the reconstruction of gene regulatory networks. we develop a simple model where the prior knowledge is given by the probability of a gene-gene interaction based on two probability distributions for true and false interactions respectively. the model is depicted in figure the prior interaction probabilities are drawn from two truncated normal distributions, x ± ~ n ± where n+ is the probability distribution for true interactions and n- is the probability distribution for false interactions. the parameters μ is set to and the standard deviation σ is set to. the accuracy of the prior knowledge is controlled by the parameter δ which is used to separate the means of both distributions. we use the model to generate prior probabilities for a subset of networks each consisting of genes. the accuracy of the prior knowledge is calculated using receiver operating characteristic curves. roc curves display the tpr in dependence of the fpr. the tpr and fpr are determined in dependence of a prediction threshold for the prior probabilities; edges with a probability above the threshold are included in the network. the accuracy corresponds with the area under the roc curve. a random prediction has an accuracy of meaning that on average the prediction cannot distinguish between true and false edges. it is interesting to compare whether the posterior networks are always of a higher accuracy compared to the accuracy of the prior networks. figure depicts the average accuracy of the prior networks versus the average accuracy of the posterior networks for different data sizes. points above the dashed line show an increase in accuracy of the posterior networks relative to the accuracy of the prior networks. points below the dashed line indicate a respective decrease in accuracy. the four curves in figure depict the dependency between prior and posterior accuracy for four different data sizes. the bisecting line indicates the situation when no gene expression data is used: prior and posterior accuracy are the same. if gene expression data is included the slope of the curves decreases from one. this can be explained by the fact that the posterior probability of a network structure is given by the product of the prior and the likelihood. as the prior is data-independent and the likelihood is proportional to the data size, the impact of the prior onto the posterior decreases with data size. this implies, that the slope of the curves decrease with larger data sizes. this can be seen in figure by comparing the slopes of the curve corresponding to and data points. the slope of the curve will approach one in the limit of small gene expression data as in this case the likelihood of the data will also approach one. the average accuracy of the networks predicted by gene expression data alone, i.e. by using an uninformative prior, corresponds with the leftmost points in the graph. for example the average accuracy of networks predicted by using data points per gene is 68%. this prediction can be increased by using more informative priors. however, this increase in accuracy is relatively weak as indicated by the slope of the curves. once the curves cross the dashed line, prior knowledge alone gives a better prediction than a combination of prior knowledge and gene expression data. this indicates that the use of a combination of prior knowledge and gene expression data within a bayesian learning framework is not always of an advantage. only situations where the amount of gene expression data is very limited can show a considerable increase in accuracy by the use of prior knowledge. however, under these data situations a prediction based on the prior knowledge alone might lead to more accurate networks. as the prior and posterior accuracy cannot be determined using real data, it is not possible to decide whether a combination of prior knowledge and gene expression data will give any benefit. our results indicate that the overall gain by combining data in a bayesian learning framework, i.e. data situations corresponding to points above the dashed line in figure is limited. nevertheless, prior knowledge can be of a benefit in the reconstruction of networks from time series. it can be used to restrict the number of possible gene-gene interactions, e.g. by allowing gene-gene interactions only between tfs and target genes which have a significant prior probability. this improves heuristic search procedures as it restricts the space of the possible posterior models. however, if detailed information on the promotor structure is available, alternative approaches which do not use the temporal information of the gene expression data explicitly are even more appropriate. the effect of hidden variables a gene-regulatory network is always integrated into a larger biochemical network which also includes proteins, small signalling molecules and regulated transport between cellular compartments. these processes and quantities are usually not resolved or measured parallel to expression studies, i.e. they are hidden to the experimentator. we study the effect of hidden variables using a gene-regulatory network developed by which is based on a coupled system of odes for variables including mrnas, proteins and promotors. figure shows the structure of the gene-gene interaction network as given in. nodes in the graph represent genes, solid edges represent interactions based on direct transcriptional regulation, i.e. the mrna product of the gene is a tf which binds to the promoter of the respective target gene and regulates its expression whereas the dotted edges represent protein-protein interactions. all the depicted interactions are indirect in the system of odes, since the interaction between genes is communicated by their products and promotor states. thus, figure is an abstraction of the underlying physical model. since our network reconstruction method assumes direct dependencies via the first order markov assumption of fully-observed dbns, we cannot expect that the recovered structure resembles the network in figure but we can deduce a more realistic reference network from the system of odes. all direct interactions in the system of odes are defined by the structure of corresponding jacobian matrix. this structure can be used to deduce an interaction graph for the subset of observed variables, i.e. mrnas. figure displays the structure of the model reduced to the observed mrna components. again, all shown interactions in the network are indirect. interpreting mrna nodes as gene nodes, all interactions present in figure are also present in figure however, many more indirect interactions arise. all of them have a clear physical justification: a change in the level of one mrna directly influences the levels of the corresponding target mrnas. therefore, the edges in the network of figure correspond either to direct transcriptional regulation ) or indirect regulation due to unobserved processes. because of the first order markov assumption underlying our method we expect, that all of the edges in figure can be recovered by a network reconstruction based on time series data. our results indicate that networks reconstructed from time series gene expression data can contain many regulatory interactions which are not based on direct transcriptional regulation, but reflect regulation due to unobserved processes, e.g. protein-protein interactions. a biological example of a process, unobserved in microarray experiments that is crucial for the regulation of target genes involves the swi4/swi controlled transcription of g1-specific genes during the yeast cell cycle. phosphorylation of the sbf repressor whi by cln3/cdk leads to a derepression of g1-specific transcription. the transcriptional activity of the sbf complex is not determined by the expression level of its components. in terms of reconstructing gene networks this means that the first order markov assumption of dbns, i.e. a relation between the expression level of a transcription factor and its regulatory potential, is not fulfilled due to hidden variables. alternative approaches include hidden variables directly into their model in order to increase the prediction accuracy. however, a clear biological interpretation of these additional variables is difficult, as the nature and number of the hidden variables is usually unknown. the hidden activity of tfs can be revealed by relating tf binding sites in promotor regions of target genes with the expression levels of the target genes. the crucial difference between these approaches and the approach studied in this paper is that the former group genes with similar tf binding sites and use their expression levels as measurement replicates for the reconstruction of the hidden tf activity. these approaches have less requirements on the number of data points per gene, but are only applicable if additional information about the promotor structure of genes is available. also, temporal information is not explicitly used. in order to reconstruct directed gene regulatory networks, i.e. networks that distinguish between regulator and target, from gene-expression data alone, either time series experiments, several gene ko experiments or, as indicated by this study, a combination of both must be conducted. however, our results indicate an inherent limitation to the reconstruction of gene-gene networks by gene expression data alone as the recovered edges between genes do not necessarily reflect direct transcriptional regulations.  in this study we identify suitable reconstruction methods, types of experiments and requirements on data size and quality in order to reverse engineer gene regulatory networks from time series data. our results suggest that linear gaussian dbns and variable selection are both appropriate methods to reconstruct the network structure from time series of gene expression data. discrete dbns are well suited for the reconstruction of probabilistic boolean networks. however, we find that their ability to reconstruct networks from discretized gene expression data is limited by their higher requirements on data size. in order to optimally identify the structure of gene-regulatory networks we show that experimental data should be generated while specifically perturbing the underlying network. we suggest tf kos as specific perturbations that allow a network reconstruction from relatively short time series. the trade-off between observational noise and data size is described and estimates for the amount of data needed in order to reconstruct accurate networks given a certain level of observational noise are provided. for example at least data points per gene are necessary in order to perform better than a random prediction given observational noise levels of 20% which corresponds with the noise level of data commonly derived from microarray measurements. we identify conditions under which prior knowledge can improve the prediction accuracy. the benefit of prior knowledge within a bayesian learning framework is limited to a particular data setting where only a small amount of gene expression data is available. we show that unobserved cellular processes lead to the reconstruction of regulatory relations between genes which are not based on direct transcriptional regulation. the ambiguity of the regulatory relations represent an inherent limitation to the reconstruction of gene-regulatory networks from time series of gene expression. 
we compare the performance of different network reconstruction methods using synthetic data generated from an ensemble of reference networks. additionally, the impact of prior knowledge on network reconstruction as well as the effect of unobserved cellular processes is studied. it is shown that short time series generated under transcription factor knock-out are optimal experiments in order to reveal the structure of gene regulatory networks. in this study, we identify an optimal type of experiment, requirements on the gene expression data quality and size as well as appropriate reconstruction methods in order to reverse engineer gene regulatory networks from time series data. relative to the level of observational noise, we give estimates for the required amount of gene expression data in order to accurately reconstruct gene-regulatory networks. the benefit of using of prior knowledge within a bayesian learning framework is found to be limited to conditions of small gene expression data size. we show that these dependencies cannot be distinguished from transcription factor mediated gene regulation on the basis of gene expression data alone. currently available data size and data quality make the reconstruction of gene networks from gene expression data a challenge. cellular processes are controlled by gene-regulatory networks. we identify linear gaussian dynamic bayesian networks and variable selection based on f-statistics as suitable methods for the reconstruction of gene-regulatory networks from time series data. commonly used discrete dynamic bayesian networks perform inferior and this result can be attributed to the inevitable information loss by discretization of expression data. unobserved processes, like protein-protein interactions, induce dependencies between gene expression levels similar to direct transcriptional regulation. this study focusses on time series gene expression and gene knock-out data in order to identify the underlying network structure. several computational methods are currently used to learn the structure of gene-regulatory networks from data. data requirements as well as optimal experiments for the reconstruction of gene-regulatory networks are investigated.
 cellular processes are controlled by gene-regulatory networks. several computational methods are currently used to learn the structure of gene-regulatory networks from data. this study focusses on time series gene expression and gene knock-out data in order to identify the underlying network structure. we compare the performance of different network reconstruction methods using synthetic data generated from an ensemble of reference networks. data requirements as well as optimal experiments for the reconstruction of gene-regulatory networks are investigated. additionally, the impact of prior knowledge on network reconstruction as well as the effect of unobserved cellular processes is studied.  we identify linear gaussian dynamic bayesian networks and variable selection based on f-statistics as suitable methods for the reconstruction of gene-regulatory networks from time series data. commonly used discrete dynamic bayesian networks perform inferior and this result can be attributed to the inevitable information loss by discretization of expression data. it is shown that short time series generated under transcription factor knock-out are optimal experiments in order to reveal the structure of gene regulatory networks. relative to the level of observational noise, we give estimates for the required amount of gene expression data in order to accurately reconstruct gene-regulatory networks. the benefit of using of prior knowledge within a bayesian learning framework is found to be limited to conditions of small gene expression data size. unobserved processes, like protein-protein interactions, induce dependencies between gene expression levels similar to direct transcriptional regulation. we show that these dependencies cannot be distinguished from transcription factor mediated gene regulation on the basis of gene expression data alone.  currently available data size and data quality make the reconstruction of gene networks from gene expression data a challenge. in this study, we identify an optimal type of experiment, requirements on the gene expression data quality and size as well as appropriate reconstruction methods in order to reverse engineer gene regulatory networks from time series data. 