BACKGROUND
network reconstruction methods infere mathematical models of real world networks directly from experimental data .
we have recently described an approach to the reconstruction of causal interaction networks from time series data sets  <cit> .
the original algorithm has two significant properties.
it delivers provenly all minimal networks which are able to reproduce the time series data that served as input and  the algorithm is exact as it does not involve any heuristic decisions by the operator so that the results are independent of any personal bias.
having a complete list of alternative networks which are compatible with experimental data shall facilitate the design of new experiments aimed at ruling out alternatives to systematically find a final, unique solution.
the output of the algorithm can be encoded as simple place/transition petri net  containing only the minimal number of nodes and arcs required to fit the given data set.
in order to exactly reproduce the experimental observations, we additionally use priorities among transitions to enforce an order in which competing transitions fire  <cit> .
the priorities reflect relative kinetic rate constants.
the algorithm starts by assigning one place to each  component or factor which has been measured in the form of a time series and tries to connect these places by a minimal set of transitions .
transitions may be interpreted as  chemical reactions .
if the number of components measured in the time series is not sufficiently high in order to create a petri net which is able to reproduce the data, the algorithm adds one place and restarts the reconstruction process and continues to do so until solutions are found  <cit> .
for the trivial example shown in figure  <dig> the solution of the reconstruction problem is obvious: the two successive states of the system which are reflected by the time series data set  are the result of the firing of a single transition connecting three places .
in more complex data sets however, the differences measured between two successive time points may have been caused by the firing of more than one transition.
therefore the algorithm has to identify all combinations of putative transition firing events the sum of which might lead to the difference observed between two successively measured time points .
according to the sampling theorem, the number of time points taken in a series needs to be sufficiently high to correctly capture the time-dependent change of the measured components in the form of a time-discrete characteristics .
potential oscillations of individual components which occur asynchronously or which are by far too fast to be observed at the time scale of interest  were not considered by the algorithm as this would cause an explosion of solutions  <cit>  and because such events cannot be observed anyway.
it follows that the original reconstruction algorithm  <cit>  considers only macroscopic changes that are measured within the chosen time scale of a given data set.
the resulting assumption of monotonicity of the time course of the components in turn puts a severe limit to the formal representation of any form of catalysis or inhibition if, as in  <cit> , only standard petri nets  are used for the reconstruction process.
as the formation and the decay of enzyme-substrate complexes in most cases are so fast and do occur asynchronously at the level of individual molecules, individual turnovers  are usually not resolved by experimental time series measurements.
representing the formation and decay of the enzyme-substrate-complex of an enzymatic  reaction by a single transition that directly connects the two places substrate  and product  of the enzymatic reaction through a bidirected arc  solves this dilemma.
in fact, our originally described algorithm does not work with so-called extended petri nets which in addition to standard arcs may contain read arcs and inhibitory arcs.
in order to include catalytic and inhibitory reactions, we had to fundamentally redesign our network reconstruction algorithm.
considering catalysis and inhibition significantly extends the practical applicability over the original algorithm  <cit>  as demonstrated in the present paper.
the new algorithm now allows for the reconstruction of signal transduction and gene regulatory networks.
it also allows the use of data sets that compare the behaviours of wild-type and mutant cells.
although the concept of providing a complete list of solutions remains and the basic principle of reconstructing the network in part is the same as in reference  <cit> , this work is based on fundamental methodological improvements  <cit>   of the underlying mathematics as compared to refs.
<cit> :
while in  <cit>  all possible reaction sequences are enumerated by simulation, the new approach uses an implicite representation of all possible combinations, thereby avoiding combinatorial explosion.
terminal states of the network are now applied in a new way which again reduces the number of combinations to be analysed.
reaction vectors and catalytic events in the form of control arcs are now treated completely independent from each other by introducing control functions.
this again greatly reduces the number of combinations to be analysed.
the new algorithm allows that reactions may depend on arbitrary logic combinations of the presence or absence of components allowing to represent complex regulatory dependencies.
a detailed description of the mathematical model extended by the new concept of control functions and the mathematical proof of the completeness of solutions provided by the algorithm will be publised in a compagnion paper  <cit>  .
in this manuscript, we describe its application to the reconstruction of signal transduction and gene regulatory networks.
a standard experimental approach in molecular biology is to introduce structural changes into a network and to study the resulting change in its static or dynamic behaviour.
such structural changes can be introduced by genetic or pharmacological intervention, for example.
many reactions in a biochemical network depend on the presence or the absence of a certain component while there may be no obvious, measurable time-dependent change in concentration or abundance of these respective components.
enzymes catalyze biochemical reactions, like e.g.
the phosphorylation or dephosphorylation of proteins in a regulatory network.
formally, and based on the original definition of catalysis by berzelius, a gene may be seen to catalyse an even far downstream process.
deleting an enzyme-encoding gene for example may abolish a certain biochemical reaction.
although transcription and translation are in between, the gene indirectly acts as a catalyst of the biochemical reaction in the sense that the gene is necessary for the biochemical reaction to occur, but it is not consumed by the reaction.
reactions in biochemical or genetic networks may be subject to the control by inhibitors as well.
deletion of a gene encoding an inhibitory subunit of a specific protein may render this protein constitutively active.
a biochemical reaction or the expression of a gene may be controled by different factors and/or might occur through alternative mechanisms.
the described regulatory dependencies of reactions can be modeled with the help of read arcs  and inhibitory arcs in the extended petri net formalism.
these control arcs determine whether a given transition is able to fire depening on the marking of its pre-places .
the reader interested in the mathematical details of the algorithm and the proof of its correctness is referred to the compagnion paper  <cit> .
RESULTS
neglecting catalysis and inhibition, each transition t can be encoded by a reaction vector rt and the collection of all such vectors yields the incidence matrix of the studied network.
considering catalysis and inhibition we deal with controled reactions: each set of such transitions that connect the same places in the same way is encoded by a controled reaction rc = , a pair, where is the reaction vector indicating the change in the marking of places caused by firing of any of the transitions of the set and fr is a control function encoding control arcs connected to the transitions.
in other words, reaction vectors and control functions separately describe two different structural properties of one and the same extended petri net:  the reaction vectors r describe how the places of a petri net are connected by transitions through directed standard arcs, and how the marking of the places accordingly changes upon firing of the transitions.
the control function fr describes which places are connected to given transitions through control arcs .
the control function also defines the conditions under which firing of at least one of all transitions with the same reaction vector can occur.
the control function is  <dig>  for a given transition if the marking of all pre-places that are connected by control arcs to that transition licenses this transition to fire.
when a transition is not connected to any control arc, the value of the control function fr is one and the firing of the transition depends only on the marking of its pre-places .
when a transition is connected by a control arc  to a place, the control function is  <dig> and the transition is allowed to fire only if the marking of this place is as defined by the control arc.
if the control arc is a read arc as in the example of figure 5b, the condition for firing is fulfilled, only if there is at least one token in the controling place .
if the control arc is an inhibitory arc, the condition is fulfilled only if there is no token in the pre-place connected by the inhibitory arc to the transition.
if the firing of a given transition is under the control of more than one control arc , the control function is one if all conditions are fullfilled.
in the petri net of figure 5c this is the case if there is at least one token in c and if there is no token in d. a controled reaction r may eventually represent more than one transition of the same reaction vector.
in this case the control function represents all conditions for the firing of any of the transitions of this set, indicating whether the reaction can occur by firing of any one of those transitions .
the marking of the regulating places may indeed be updated through transitions connected through standard arcs to other places of the network.
essential function of the algorithm
we describe the essential function of the algorithm by taking the small petri net of figure 6a as an example.
the small net is used to generate a discrete time series data set starting with the initial marking shown.
in this context, a time series data set indicates how the values of the components  change as a function of time.
as the marking of the net may not necessarily change with each measured time point, the time series data set is compiled into a state matrix  which indicates how the marking of the net develops as the tokens pass through until a terminal state is reached .
a terminal state is defined as a state where the marking of all places in the petri net does not change anymore.
compilation eliminates redundancy in the time series data by deleting information for time points where no change was detected as compared to the previous measurement.
information from several time series data sets obtained in different experiments and/or performed with networks after structural intervention  may be combined into a single state matrix to be used as input for the reconstruction algorithm .
from the state matrix, the difference vector matrix is computed with difference vectors indicating how the marking of the net  changes from one state to the next.
the two states x <dig> and x <dig>  the difference vector d <dig> = x <dig> - x <dig>  and the terminal state x <dig> are arbitrarily chosen to demonstrate subsequent steps of the algorithm.
as it is not known a priori whether the change in marking of places represented by a given difference vector is caused by the firing of one or of several transitions, all difference vectors are decomposed into the maximal sets of possible individual reaction vectors r to be listed in one reaction vector matrix.
the reaction vector matrix lists all possible connections of places and transitions by standard arcs as putative nodes of a reconstructed petri net.
which of these connections indeed is suitable to be a transition in alternative reconstructed networks and in which temporal order the transitions fire is estimated at a later stage of the analysis.
figure 6d shows the decomposition of the difference vector d <dig> = t into seven different reaction vectors as an example.
for the sake of clarity, the reaction vectors obtained by exhaustive decomposition of d <dig> are graphically represented as petri nets in figure 6e.
referring to a biochemical model, complete decomposition takes into account that it is not known whether the chemical components a, b, and c react with each other or  separately.
in case a, b and c are involved in more than one chemical reaction, it is open in which temporal sequence these reactions do occur.
therefore, all possible permutations of all reaction vector combinations that give a difference vector have to be considered .
this may however lead to intermediate states of the system that have not been observed in the time series data set.
this is demonstrated by taking the two possible permutations of the sequence of r <dig> and r <dig> as example .
in the first permutation , the system proceeds from state x <dig> to state x <dig> through an additional, intermediate state y <dig>  in the second permutation , the additional, intermediate state is y <dig>  for the sake of completeness it is essential to compute all potential additional, intermediate states and this complete set is required for performing the next step of the algorithm in which all reactions that cannot be part of a functional reconstructed petri net are filtered out.
filtering is performed by testing all reactions of the reaction vector matrix with all states of the state matrix which has been extended by all additional states y. all sums of a state vector and a reaction vector are evaluated.
this is performed by asking which reaction is applicable in each individual state of the system .
a reaction, by definition, is applicable to a state if it does not generate an invalid successor state with entires out of bound .
the remaining pairs of state vector and applicable reaction vector are analysed for the potential control by the control function the value of which may change in a marking-dependent manner while the tokens flow through the net.
each individual transition might potentially be under the control of test- and/or of inhibitory arcs that might emerge from any of the places and hence all reactions must be considered for such potential control.
if a reaction is applied to  a given state, the control function fr must have the value of  <dig> at that state.
if a reaction is applicable to one of the terminal states , the reaction must be disabled at this state, because otherwise the state would not be terminal.
in this case the control function must be fr=  <dig>  by comparison of state vectors where the reaction is enabled and state vectors of terminal states where the reaction has to be disabled, one then identifies potential places, the marking of which might control the firing licence of the respective transition of a petri net in terms of an argument of the control function.
in the example shown in figure 6g , reaction r <dig> occurs at the state x <dig> which has a token in a but no token in place f. because the terminal state x <dig>  has no token in a but a token in f, either of the two places can control r <dig>  in other words, the reaction r <dig> may be mediated by a transition which is connected to place a by a test arc, or it may be mediated by a transition which is connected to place f by an inhibitory arc.
note that, in the simple case, only one of the two controled reactions  or  needs to be chosen to compose the reconstructed petri net.
when a reaction occurs at multiple different states and has to be disabled at multiple terminal states, more complex control is possible .
to summarize, when a reaction r is applied to a certain state x, it has to be enabled by its control function at that state  = 1).
if the reaction is applicable at some terminal state x', the control function has to disable the reaction  = 0), otherwise r could produce a successor state of x' contradicting its property to be a terminal state.
with respect to their associated control function fr, reactions r as elements of a controled reaction rc =  fall into three groups:
a reaction that is not applicable to any terminal state can be enabled at all times fr ≡ 1) which means that by minimality no control arcs are pointing to the respective transition in the reconstructed petri nets.
a reaction which is applicable to an intermediate state of the system which has the same state vector x as a terminal state has, must be deleted , because the control function fr cannot be  <dig>  and  <dig>  at identical marking of the petri net.
hence no appropriate control arcs exist in this case.
in all other cases the control of the reaction by control arcs is possible .
this allows to identify places that potentially do control the reaction through a control arc.
mathematical details are given in  <cit> .
exhaustive decomposition of all difference vectors into reaction vectors with all possible permutations in the order  of the reactions and testing them against the state vectors finally yields a complete list of controled reactions ) as potential elements of a reconstructed extended petri net.
reverse engineered petri nets are then composed simply by combining for each difference vector one arbitrarily chosen set of controled reactions that results from the decomposition of each of the subsequent difference vectors.
figure 7a shows one possible trajectory for obtaining one possible petri net that is consistent with the input data set.
all petri nets obtained accordingly through different trajectories are compatible with the input data  <cit> .
an example of how sets of controled reactions translate into petri net structures is shown in figure 7b.
the lower the number of sets of controled reactions found for any given difference vector is, the lower is the number of alternative petri nets that are compatible with the input data set.
a unique petri net is obtained if there is only one reaction set for each difference vector.
if more or even many alternative petri nets are obtained, the implicit representation of solutions is useful for the design of experiments as it directly shows which parts of the underlying network are still ill-defined.
the phosphate regulatory network as a test case
the phosphate regulatory network is a network of interacting phosphate-sensing and signal transducing proteins regulating the expression of a battery of genes which are arranged in the pho operon.
these jointly controlled genes encode proteins related to the phosphate metabolism of enteric bacteria  <cit> .
the network serves as a non-trivial test case as the corresponding petri net contains negative feed-back loops  <cit>  which have to be recognized by the reconstruction algorithm.
in the following, we will first briefly describe the biological function of the phosphate regulatory network and its implementation in the form of a petri net model as far as it is relevant for understanding the in silico experiments on genetic  perturbation.
subsequently, we will describe the in silico experiments performed to obtain the time series data set.
finally, we will demonstrate step by step how the network was reconstructed on the basis of this data set.
biology of phosphate regulation
growth of micro-organisms requires the presence of inorganic phosphate , an essential component for the synthesis of nucleic acids .
inorganic phosphate is taken up by the pstscab complex, which transports inorganic phosphate into the cytoplasm against its concentration gradient .
under natural growth conditions, the concentration of inorganic phosphate may become a growth-limiting factor.
when inorganic phosphate is absent, the phosphate transporter lacks substrate and relays this information through a cascade of three proteins, phou, phor, and phob to cause, among others, the transcription of the phoa gene which encodes alkaline phosphatase.
this enzyme is synthesized and exported from the cytoplasm into the periplasm where it accumulates in considerable amounts.
by degrading organic phosphate compounds that may originate from decaying organisms, alkaline phosphatase provides inorganic phosphate which is taken up into the cell by the pstscab complex.
as the biosynthesis of high amounts of alkaline phosphatase is energetically expensive, transcription of the phoa gene is tightly controled by the concentration of inorganic phosphate through negative feed-back loops that stop the transcriptional activation of the phoa gene when sufficient pi is available.
note that this paper does not make any scientific contribution to the biology of phosphate regulation.
the petri net model of the phosphate regulatory network is only used as a test case for the network reconstruction algorithm.
petri net model of the phosphate regulatory network
the biochemical interaction of the proteins of the phosphate regulatory network and established feed-back mechanisms  <cit>  have been translated into a petri net model   <cit>  with the help of the petri net tool snoopy  <cit> .
influences of protein conformation on the activity of biochemical reactions, e.g.
the phosphorylation of phor caused by the active form of phou has been modeled by read arcs.
using the simulation mode of snoopy, the response of the network to addition and removal of inorganic phosphate has been analysed in silico to obtain time series data sets.
in silico experiments were chosen to mimic common experimental methodology and, therefore, produce realistic input data for the reconstruction.
reconstructing the phosphate regulatory network
for reconstructing the phosphate regulatory network, we started with protein components.
the task was to find the wiring diagram based on the simulated time-series data sets.
the time series data indicated the phosphorylation status of pstscab, phor, and phob in response to external inorganic phosphate.
we did not use any kinetic information on the interconversion of the phou protein between its inactive and its active state supposing that the corresponding conformational change cannot be directly measured, but the algorithm was told that these two forms, active and inactive, exist.
we then generated in silico deletion mutants for the pstscab, phou, phor, and phob genes by adjusting the initial marking of the net accordingly  and analysed the response of each of those mutants to the removal of inorganic phosphate as compared to the wild-type.
for each experiment, the type of experimental perturbation and the implementation of this perturbation in the form of the intitial marking of the petri net of figure 8a is indicated.
genetic background column: Δphor means that the phor gene is deleted and that the phor protein is absent accordingly, etc.
Δpsite means that the phosphorylation site in the respective protein is deleted, while the protein as such is present.
the table is useful to assign the state vectors listed in tables  <dig> and  <dig> to the subsequently occurring molecular events.
starting with the initial marking as shown in figure 8a, we generated a time series data set for the wild-type by allowing the tokens to step by step move through the net, which directly gave the first part of the state matrix .
the state matrix was subsequently extended by adding compiled time series data for all experiments listed in table  <dig> to represent the subsequent occurrence of all states of the system observed in all in silico experiments in the form of one comprehensive data set.
the state matrix was then used to calculate the difference vector matrix as described .
the difference vectors obtained in all experiments are listed only once, i.e.
the same difference vector observed in several experiments gives only one entry as a column in the difference vector matrix.
decomposition of the difference vectors into all possible sums of reaction vectors yielded the reaction vector matrix.
at this point p-invariants restricted the number of possible reactions.
states are assigned to the experiments during which they occurred.
the state vectors of experiments  <dig> to  <dig> are shown in this table, the state vectors of experiments  <dig> to  <dig> are shown in table  <dig>  states of pst, phou, phor, and phob were considered as p-invariants.
phosphate, phor, phorp and the cytoplasmic phoa protein were excluded as catalytic factors based on biological knowledge.
states are assigned to the experiments during which they occurred.
the state vectors of experiments  <dig> to  <dig> are shown in table  <dig>  difference vectors and additional decomposed reactions that appeared in more than one experiment are listed only once.
states of pst, phou, phor, and phob were considered as p-invariants.
phosphate, phor, phorp and the cytoplasmic phoa protein were excluded as catalytic factors based on biological knowledge.
each single reaction vector was then analysed whether it is applied to carry the system from one state xi to a subsequent state xi+ <dig>  if a reaction was applicable to a state xi which is also a terminal state, the reaction must be disabled in the terminal state, as defined by the appropriate control function .
if the reaction could not be switched off, the reaction was deleted from the set of solutions.
finding appropriate control functions for all corresponding reaction vectors as described above, and excluding contradictory reactions from the set finally lead to the wiring of places and transitions and to the control of certain transitions by read arcs or inhibitory arcs.
the original phosphate regulatory network and the result of the reconstruction procedure are shown in figure  <dig>  the algorithm reproduced the wiring of the original petri net.
for four transitions of the original petri net however, the algorithm found alternatives some of which in fact suggest alternative molecular mechanisms that would give rise to the same dynamic behaviour in the considered experiments while others merely make sense and can be ruled out accordingly.
the algorithm suggested that inorganic phosphate  is transported by the pstscab complex into the cell .
the alternative mechanism that pi disappears in the periplasm and appears in the cytoplasm mediated by independent, non-coupled reactions both catalyzed by the pstscab complex would imply the existence of additional pools of inorganic phosphate different from cytoplasm and periplasm that would serve as source and sink, respectively.
this alternative is ruled out as unlikely mechanism.
alternative mechanisms of phou inactivation that occur by conformational coupling with the pstscab complex are more difficult to distinguish .
the algorithm suggests biochemically meaningful mechanisms, namely that inactivation of phou may be catalyzed by the phosphorylated form of the pstscab complex, or inhibited by the dephosphorylated form of pstscab.
in principle, both mechanisms could be true but in the context of a minimal model, only one regulatory interaction, catalysis or inhibition is allowed.
the third alternative suggests that inactivation of phou is catalyzed by periplasmic pi.
this alternative is discarded since the two molecules reside in different spatial compartments.
a reaction where the molecular mechanism is unclear based on the results of the reconstruction algorithm concerns the dephosphorylation of phobp .
phobp dephosphorylation may be catalyzed by inactive phou or by the phosphorylated form of the pstscab complex or by periplasmic pi.
while direct interaction with periplasmic pi again is discarded, other alternatives cannot be ruled out by argumentation.
phobp dephosphorylation may be inhibited by active phou or by the dephosphorylated form of the pstscab complex.
in silico phenotypes of deletion mutants did not allow to discriminate between these alternatives, suggesting to investigate these alternatives with the help of in vitro experiments where the biochemical activity of the individual proteins on the phosphorylated form of phob is analysed.
such in vitro data could certainly also be fed into the reconstruction algorithm.
a final ambiguity in mechanisms can simply be resolved .
the algorithm suggests that the cytoplasmic phoa protein is transported into the periplasm.
alternatively, cytoplasmic phoa would disappear into an unknown pool and appear in the periplasm from an unknown pool in independent non-coupled reactions.
as a protein appearing in the periplasm must have been synthesized in the cytoplasm at some point, transport across the cytoplasmic membrane in a prokaryotic cell seems to be the right mechanism rather than exocytosis through cytoplasmic vesicles.
in summary, the algorithm found a core network with defined wiring .
wiring alternatives found for four transitions can be discarded based on biological knowledge or suggested biochemically meaningful alternatives: activation of a reaction by one form of a protein or inhibition of the same reaction by its covalently modified or otherwise differently active form.
discussion
we have described a new algorithm for the reconstruction of extended petri nets from time series data sets.
the algorithm delivers a complete list of solutions expressed in the form of petri nets all of which are compatible with the input data.
as for the previously published method  <cit>  there is a guarantee through mathematical proof that the list of provided minimal models is complete, in that no possible alternative petri net is missing that might also be able to explain the data  <cit> .
the new algorithm however provides a significant advance in delivering petri nets with read arcs and inhibitory arcs, so-called extended petri nets.
extended petri nets are more powerful and straigt-forward in representing regulatory interactions in signal transduction and genetic networks.
encoding regulatory interactions including catalysis and inhibition with the help of simple place/transition petri nets  is possible but it requires the introduction of additional places and transitions leading to an explosion of the number of generated solutions in network reconstruction through multiple alternative combinations of symmetric motifs redundant in terms of the encoded regulatory properties.
by avoiding redundancy, the present algorithm allows to reconstruct networks from time series data sets that are obtained with mutants or e.g.
after pharmacological intervention both of which can be regarded as structural alterations introduced into a network by targeting elements that exert regulatory control.
using a model of the phosphate regulatory network of enterobacteria as a test case, the algorithm correctly reconstructed the petri net which was used to generate in silico time series data sets for wild-type cells, deletion mutants and site-directed mutants.
for four transitions of the original network the algorithm found alternatively wired transitions that would also be consistent with the data set.
the alternative wiring translates into reasonable alternative molecular mechanisms which might be tested experimentally.
attempts to reconstruct a network from a time series data set where multiple components were measured in response to a specific perturbation  typically gives a large number of alternative networks.
the implicit representation of these networks e.g.
as a column of controled reactions listed for each difference vector  is useful to identify those difference vectors and in turn those components of the system, the ill-resolved wiring of which greately increases the number of alternative network structures  <cit> .
comparative analysis of time series measured with wild-type and mutants in different genes is an efficient way to reduce the number of alternative network structures delivered by the reconstruction algorithm.
when sufficient experiments with different mutants are evaluated, the algorithm may give only one or few solutions as in the phosphate regulatory network that served as a test case in the present study.
feeding the algorithm with even more data indeed might lead to a situation where not even a single solution is found without that additional components  are introduced.
the current algorithm does not support the introduction of additional components as an earlier implementation without read arcs did.
this feature is to be implemented in a future version of the algorithm.
according to the original definition, petri nets represent concurrent processes.
transitions that have the licence to fire do not necessarily fire immediately which makes the behaviour of the network nondeterministic.
reaction rates corresponding to rate constants in chemical kinetics can be introduced by assigning a probablilistic hazard function to each transition, yielding a stochastic petri net  <cit> .
for network reconstruction purposes, relative reaction rates can be encoded in the form of priorities to enforce in which temporal sequence competing transitions fire  <cit> .
considering priorities in the reconstruction process may again considerably reduce the number of alternative solutions.
the present form of the algorithm does not consider priorities.
CONCLUSIONS
the algorithm described in this work reconstructs extended petri nets from time series data sets by finding all alternative minimal networks that are consistent with the data.
it suggested reasonable alternative molecular mechanisms for certain reactions in the network that can be tested experimentally.
the algorithm integrated data obtained for wild-type and for mutant cells and may, in the way shown, be useful to integrate physiological, biochemical, pharmacological, and genetic data into a consistent petri net model.
the algorithm works with discretized data or with data that are per se discrete like e.g.
the presence or the absence of a phenotype.
we consciously keep computational methods of data discretization or statistical treatment of data strictly separated from the reconstruction algorithm.
with reliable, i.e.
statistically significant and reproducible experimental data sets, the algorithm can be used to obtain certified results based on the proven property to deliver all possible minimal networks.
with enough input data, one may obtain one unique network.
having data sets that give more or even many possible networks as solutions, the implicit representation of the networks can clearly show which firm conclusions can be drawn from the experimental data in terms of proven causal connections that are identical in all deliviered networks, and alternatives for the causal connection of components may be used for experimental design.
the results presented in this work were obtained by manual computation.
we are currently exploring the potential of answer set programming  to efficiently compute large data sets to reconstruct large networks  <cit> .

 network reconstruction methods infere mathematical models of real world networks directly from experimental data. we have recently described an approach to the reconstruction of causal interaction networks from time series data sets. the original algorithm has two significant properties. it delivers provenly all minimal networks which are able to reproduce the time series data that served as input and the algorithm is exact as it does not involve any heuristic decisions by the operator so that the results are independent of any personal bias. having a complete list of alternative networks which are compatible with experimental data shall facilitate the design of new experiments aimed at ruling out alternatives to systematically find a final, unique solution. the output of the algorithm can be encoded as simple place/transition petri net containing only the minimal number of nodes and arcs required to fit the given data set. in order to exactly reproduce the experimental observations, we additionally use priorities among transitions to enforce an order in which competing transitions fire. the priorities reflect relative kinetic rate constants. the algorithm starts by assigning one place to each component or factor which has been measured in the form of a time series and tries to connect these places by a minimal set of transitions. transitions may be interpreted as chemical reactions. if the number of components measured in the time series is not sufficiently high in order to create a petri net which is able to reproduce the data, the algorithm adds one place and restarts the reconstruction process and continues to do so until solutions are found. for the trivial example shown in figure the solution of the reconstruction problem is obvious: the two successive states of the system which are reflected by the time series data set are the result of the firing of a single transition connecting three places. in more complex data sets however, the differences measured between two successive time points may have been caused by the firing of more than one transition. therefore the algorithm has to identify all combinations of putative transition firing events the sum of which might lead to the difference observed between two successively measured time points. according to the sampling theorem, the number of time points taken in a series needs to be sufficiently high to correctly capture the time-dependent change of the measured components in the form of a time-discrete characteristics. potential oscillations of individual components which occur asynchronously or which are by far too fast to be observed at the time scale of interest were not considered by the algorithm as this would cause an explosion of solutions and because such events cannot be observed anyway. it follows that the original reconstruction algorithm considers only macroscopic changes that are measured within the chosen time scale of a given data set. the resulting assumption of monotonicity of the time course of the components in turn puts a severe limit to the formal representation of any form of catalysis or inhibition if, as in, only standard petri nets are used for the reconstruction process. as the formation and the decay of enzyme-substrate complexes in most cases are so fast and do occur asynchronously at the level of individual molecules, individual turnovers are usually not resolved by experimental time series measurements. representing the formation and decay of the enzyme-substrate-complex of an enzymatic reaction by a single transition that directly connects the two places substrate and product of the enzymatic reaction through a bidirected arc solves this dilemma. in fact, our originally described algorithm does not work with so-called extended petri nets which in addition to standard arcs may contain read arcs and inhibitory arcs. in order to include catalytic and inhibitory reactions, we had to fundamentally redesign our network reconstruction algorithm. considering catalysis and inhibition significantly extends the practical applicability over the original algorithm as demonstrated in the present paper. the new algorithm now allows for the reconstruction of signal transduction and gene regulatory networks. it also allows the use of data sets that compare the behaviours of wild-type and mutant cells. although the concept of providing a complete list of solutions remains and the basic principle of reconstructing the network in part is the same as in reference, this work is based on fundamental methodological improvements of the underlying mathematics as compared to refs.: while in all possible reaction sequences are enumerated by simulation, the new approach uses an implicite representation of all possible combinations, thereby avoiding combinatorial explosion. terminal states of the network are now applied in a new way which again reduces the number of combinations to be analysed. reaction vectors and catalytic events in the form of control arcs are now treated completely independent from each other by introducing control functions. this again greatly reduces the number of combinations to be analysed. the new algorithm allows that reactions may depend on arbitrary logic combinations of the presence or absence of components allowing to represent complex regulatory dependencies. a detailed description of the mathematical model extended by the new concept of control functions and the mathematical proof of the completeness of solutions provided by the algorithm will be publised in a compagnion paper. in this manuscript, we describe its application to the reconstruction of signal transduction and gene regulatory networks. a standard experimental approach in molecular biology is to introduce structural changes into a network and to study the resulting change in its static or dynamic behaviour. such structural changes can be introduced by genetic or pharmacological intervention, for example. many reactions in a biochemical network depend on the presence or the absence of a certain component while there may be no obvious, measurable time-dependent change in concentration or abundance of these respective components. enzymes catalyze biochemical reactions, like e.g. the phosphorylation or dephosphorylation of proteins in a regulatory network. formally, and based on the original definition of catalysis by berzelius, a gene may be seen to catalyse an even far downstream process. deleting an enzyme-encoding gene for example may abolish a certain biochemical reaction. although transcription and translation are in between, the gene indirectly acts as a catalyst of the biochemical reaction in the sense that the gene is necessary for the biochemical reaction to occur, but it is not consumed by the reaction. reactions in biochemical or genetic networks may be subject to the control by inhibitors as well. deletion of a gene encoding an inhibitory subunit of a specific protein may render this protein constitutively active. a biochemical reaction or the expression of a gene may be controled by different factors and/or might occur through alternative mechanisms. the described regulatory dependencies of reactions can be modeled with the help of read arcs and inhibitory arcs in the extended petri net formalism. these control arcs determine whether a given transition is able to fire depening on the marking of its pre-places. the reader interested in the mathematical details of the algorithm and the proof of its correctness is referred to the compagnion paper.  neglecting catalysis and inhibition, each transition t can be encoded by a reaction vector rt and the collection of all such vectors yields the incidence matrix of the studied network. considering catalysis and inhibition we deal with controled reactions: each set of such transitions that connect the same places in the same way is encoded by a controled reaction rc =, a pair, where is the reaction vector indicating the change in the marking of places caused by firing of any of the transitions of the set and fr is a control function encoding control arcs connected to the transitions. in other words, reaction vectors and control functions separately describe two different structural properties of one and the same extended petri net: the reaction vectors r describe how the places of a petri net are connected by transitions through directed standard arcs, and how the marking of the places accordingly changes upon firing of the transitions. the control function fr describes which places are connected to given transitions through control arcs. the control function also defines the conditions under which firing of at least one of all transitions with the same reaction vector can occur. the control function is for a given transition if the marking of all pre-places that are connected by control arcs to that transition licenses this transition to fire. when a transition is not connected to any control arc, the value of the control function fr is one and the firing of the transition depends only on the marking of its pre-places. when a transition is connected by a control arc to a place, the control function is and the transition is allowed to fire only if the marking of this place is as defined by the control arc. if the control arc is a read arc as in the example of figure 5b, the condition for firing is fulfilled, only if there is at least one token in the controling place. if the control arc is an inhibitory arc, the condition is fulfilled only if there is no token in the pre-place connected by the inhibitory arc to the transition. if the firing of a given transition is under the control of more than one control arc, the control function is one if all conditions are fullfilled. in the petri net of figure 5c this is the case if there is at least one token in c and if there is no token in d. a controled reaction r may eventually represent more than one transition of the same reaction vector. in this case the control function represents all conditions for the firing of any of the transitions of this set, indicating whether the reaction can occur by firing of any one of those transitions. the marking of the regulating places may indeed be updated through transitions connected through standard arcs to other places of the network. essential function of the algorithm we describe the essential function of the algorithm by taking the small petri net of figure 6a as an example. the small net is used to generate a discrete time series data set starting with the initial marking shown. in this context, a time series data set indicates how the values of the components change as a function of time. as the marking of the net may not necessarily change with each measured time point, the time series data set is compiled into a state matrix which indicates how the marking of the net develops as the tokens pass through until a terminal state is reached. a terminal state is defined as a state where the marking of all places in the petri net does not change anymore. compilation eliminates redundancy in the time series data by deleting information for time points where no change was detected as compared to the previous measurement. information from several time series data sets obtained in different experiments and/or performed with networks after structural intervention may be combined into a single state matrix to be used as input for the reconstruction algorithm. from the state matrix, the difference vector matrix is computed with difference vectors indicating how the marking of the net changes from one state to the next. the two states x and x the difference vector d = x - x and the terminal state x are arbitrarily chosen to demonstrate subsequent steps of the algorithm. as it is not known a priori whether the change in marking of places represented by a given difference vector is caused by the firing of one or of several transitions, all difference vectors are decomposed into the maximal sets of possible individual reaction vectors r to be listed in one reaction vector matrix. the reaction vector matrix lists all possible connections of places and transitions by standard arcs as putative nodes of a reconstructed petri net. which of these connections indeed is suitable to be a transition in alternative reconstructed networks and in which temporal order the transitions fire is estimated at a later stage of the analysis. figure 6d shows the decomposition of the difference vector d = t into seven different reaction vectors as an example. for the sake of clarity, the reaction vectors obtained by exhaustive decomposition of d are graphically represented as petri nets in figure 6e. referring to a biochemical model, complete decomposition takes into account that it is not known whether the chemical components a, b, and c react with each other or separately. in case a, b and c are involved in more than one chemical reaction, it is open in which temporal sequence these reactions do occur. therefore, all possible permutations of all reaction vector combinations that give a difference vector have to be considered. this may however lead to intermediate states of the system that have not been observed in the time series data set. this is demonstrated by taking the two possible permutations of the sequence of r and r as example. in the first permutation, the system proceeds from state x to state x through an additional, intermediate state y in the second permutation, the additional, intermediate state is y for the sake of completeness it is essential to compute all potential additional, intermediate states and this complete set is required for performing the next step of the algorithm in which all reactions that cannot be part of a functional reconstructed petri net are filtered out. filtering is performed by testing all reactions of the reaction vector matrix with all states of the state matrix which has been extended by all additional states y. all sums of a state vector and a reaction vector are evaluated. this is performed by asking which reaction is applicable in each individual state of the system. a reaction, by definition, is applicable to a state if it does not generate an invalid successor state with entires out of bound. the remaining pairs of state vector and applicable reaction vector are analysed for the potential control by the control function the value of which may change in a marking-dependent manner while the tokens flow through the net. each individual transition might potentially be under the control of test- and/or of inhibitory arcs that might emerge from any of the places and hence all reactions must be considered for such potential control. if a reaction is applied to a given state, the control function fr must have the value of at that state. if a reaction is applicable to one of the terminal states, the reaction must be disabled at this state, because otherwise the state would not be terminal. in this case the control function must be fr= by comparison of state vectors where the reaction is enabled and state vectors of terminal states where the reaction has to be disabled, one then identifies potential places, the marking of which might control the firing licence of the respective transition of a petri net in terms of an argument of the control function. in the example shown in figure 6g, reaction r occurs at the state x which has a token in a but no token in place f. because the terminal state x has no token in a but a token in f, either of the two places can control r in other words, the reaction r may be mediated by a transition which is connected to place a by a test arc, or it may be mediated by a transition which is connected to place f by an inhibitory arc. note that, in the simple case, only one of the two controled reactions or needs to be chosen to compose the reconstructed petri net. when a reaction occurs at multiple different states and has to be disabled at multiple terminal states, more complex control is possible. to summarize, when a reaction r is applied to a certain state x, it has to be enabled by its control function at that state = 1). if the reaction is applicable at some terminal state x', the control function has to disable the reaction = 0), otherwise r could produce a successor state of x' contradicting its property to be a terminal state. with respect to their associated control function fr, reactions r as elements of a controled reaction rc = fall into three groups: a reaction that is not applicable to any terminal state can be enabled at all times fr ≡ 1) which means that by minimality no control arcs are pointing to the respective transition in the reconstructed petri nets. a reaction which is applicable to an intermediate state of the system which has the same state vector x as a terminal state has, must be deleted, because the control function fr cannot be and at identical marking of the petri net. hence no appropriate control arcs exist in this case. in all other cases the control of the reaction by control arcs is possible. this allows to identify places that potentially do control the reaction through a control arc. mathematical details are given in. exhaustive decomposition of all difference vectors into reaction vectors with all possible permutations in the order of the reactions and testing them against the state vectors finally yields a complete list of controled reactions ) as potential elements of a reconstructed extended petri net. reverse engineered petri nets are then composed simply by combining for each difference vector one arbitrarily chosen set of controled reactions that results from the decomposition of each of the subsequent difference vectors. figure 7a shows one possible trajectory for obtaining one possible petri net that is consistent with the input data set. all petri nets obtained accordingly through different trajectories are compatible with the input data. an example of how sets of controled reactions translate into petri net structures is shown in figure 7b. the lower the number of sets of controled reactions found for any given difference vector is, the lower is the number of alternative petri nets that are compatible with the input data set. a unique petri net is obtained if there is only one reaction set for each difference vector. if more or even many alternative petri nets are obtained, the implicit representation of solutions is useful for the design of experiments as it directly shows which parts of the underlying network are still ill-defined. the phosphate regulatory network as a test case the phosphate regulatory network is a network of interacting phosphate-sensing and signal transducing proteins regulating the expression of a battery of genes which are arranged in the pho operon. these jointly controlled genes encode proteins related to the phosphate metabolism of enteric bacteria. the network serves as a non-trivial test case as the corresponding petri net contains negative feed-back loops which have to be recognized by the reconstruction algorithm. in the following, we will first briefly describe the biological function of the phosphate regulatory network and its implementation in the form of a petri net model as far as it is relevant for understanding the in silico experiments on genetic perturbation. subsequently, we will describe the in silico experiments performed to obtain the time series data set. finally, we will demonstrate step by step how the network was reconstructed on the basis of this data set. biology of phosphate regulation growth of micro-organisms requires the presence of inorganic phosphate, an essential component for the synthesis of nucleic acids. inorganic phosphate is taken up by the pstscab complex, which transports inorganic phosphate into the cytoplasm against its concentration gradient. under natural growth conditions, the concentration of inorganic phosphate may become a growth-limiting factor. when inorganic phosphate is absent, the phosphate transporter lacks substrate and relays this information through a cascade of three proteins, phou, phor, and phob to cause, among others, the transcription of the phoa gene which encodes alkaline phosphatase. this enzyme is synthesized and exported from the cytoplasm into the periplasm where it accumulates in considerable amounts. by degrading organic phosphate compounds that may originate from decaying organisms, alkaline phosphatase provides inorganic phosphate which is taken up into the cell by the pstscab complex. as the biosynthesis of high amounts of alkaline phosphatase is energetically expensive, transcription of the phoa gene is tightly controled by the concentration of inorganic phosphate through negative feed-back loops that stop the transcriptional activation of the phoa gene when sufficient pi is available. note that this paper does not make any scientific contribution to the biology of phosphate regulation. the petri net model of the phosphate regulatory network is only used as a test case for the network reconstruction algorithm. petri net model of the phosphate regulatory network the biochemical interaction of the proteins of the phosphate regulatory network and established feed-back mechanisms have been translated into a petri net model with the help of the petri net tool snoopy. influences of protein conformation on the activity of biochemical reactions, e.g. the phosphorylation of phor caused by the active form of phou has been modeled by read arcs. using the simulation mode of snoopy, the response of the network to addition and removal of inorganic phosphate has been analysed in silico to obtain time series data sets. in silico experiments were chosen to mimic common experimental methodology and, therefore, produce realistic input data for the reconstruction. reconstructing the phosphate regulatory network for reconstructing the phosphate regulatory network, we started with protein components. the task was to find the wiring diagram based on the simulated time-series data sets. the time series data indicated the phosphorylation status of pstscab, phor, and phob in response to external inorganic phosphate. we did not use any kinetic information on the interconversion of the phou protein between its inactive and its active state supposing that the corresponding conformational change cannot be directly measured, but the algorithm was told that these two forms, active and inactive, exist. we then generated in silico deletion mutants for the pstscab, phou, phor, and phob genes by adjusting the initial marking of the net accordingly and analysed the response of each of those mutants to the removal of inorganic phosphate as compared to the wild-type. for each experiment, the type of experimental perturbation and the implementation of this perturbation in the form of the intitial marking of the petri net of figure 8a is indicated. genetic background column: Δphor means that the phor gene is deleted and that the phor protein is absent accordingly, etc. Δpsite means that the phosphorylation site in the respective protein is deleted, while the protein as such is present. the table is useful to assign the state vectors listed in tables and to the subsequently occurring molecular events. starting with the initial marking as shown in figure 8a, we generated a time series data set for the wild-type by allowing the tokens to step by step move through the net, which directly gave the first part of the state matrix. the state matrix was subsequently extended by adding compiled time series data for all experiments listed in table to represent the subsequent occurrence of all states of the system observed in all in silico experiments in the form of one comprehensive data set. the state matrix was then used to calculate the difference vector matrix as described. the difference vectors obtained in all experiments are listed only once, i.e. the same difference vector observed in several experiments gives only one entry as a column in the difference vector matrix. decomposition of the difference vectors into all possible sums of reaction vectors yielded the reaction vector matrix. at this point p-invariants restricted the number of possible reactions. states are assigned to the experiments during which they occurred. the state vectors of experiments to are shown in this table, the state vectors of experiments to are shown in table states of pst, phou, phor, and phob were considered as p-invariants. phosphate, phor, phorp and the cytoplasmic phoa protein were excluded as catalytic factors based on biological knowledge. states are assigned to the experiments during which they occurred. the state vectors of experiments to are shown in table difference vectors and additional decomposed reactions that appeared in more than one experiment are listed only once. states of pst, phou, phor, and phob were considered as p-invariants. phosphate, phor, phorp and the cytoplasmic phoa protein were excluded as catalytic factors based on biological knowledge. each single reaction vector was then analysed whether it is applied to carry the system from one state xi to a subsequent state xi+ if a reaction was applicable to a state xi which is also a terminal state, the reaction must be disabled in the terminal state, as defined by the appropriate control function. if the reaction could not be switched off, the reaction was deleted from the set of solutions. finding appropriate control functions for all corresponding reaction vectors as described above, and excluding contradictory reactions from the set finally lead to the wiring of places and transitions and to the control of certain transitions by read arcs or inhibitory arcs. the original phosphate regulatory network and the result of the reconstruction procedure are shown in figure the algorithm reproduced the wiring of the original petri net. for four transitions of the original petri net however, the algorithm found alternatives some of which in fact suggest alternative molecular mechanisms that would give rise to the same dynamic behaviour in the considered experiments while others merely make sense and can be ruled out accordingly. the algorithm suggested that inorganic phosphate is transported by the pstscab complex into the cell. the alternative mechanism that pi disappears in the periplasm and appears in the cytoplasm mediated by independent, non-coupled reactions both catalyzed by the pstscab complex would imply the existence of additional pools of inorganic phosphate different from cytoplasm and periplasm that would serve as source and sink, respectively. this alternative is ruled out as unlikely mechanism. alternative mechanisms of phou inactivation that occur by conformational coupling with the pstscab complex are more difficult to distinguish. the algorithm suggests biochemically meaningful mechanisms, namely that inactivation of phou may be catalyzed by the phosphorylated form of the pstscab complex, or inhibited by the dephosphorylated form of pstscab. in principle, both mechanisms could be true but in the context of a minimal model, only one regulatory interaction, catalysis or inhibition is allowed. the third alternative suggests that inactivation of phou is catalyzed by periplasmic pi. this alternative is discarded since the two molecules reside in different spatial compartments. a reaction where the molecular mechanism is unclear based on the results of the reconstruction algorithm concerns the dephosphorylation of phobp. phobp dephosphorylation may be catalyzed by inactive phou or by the phosphorylated form of the pstscab complex or by periplasmic pi. while direct interaction with periplasmic pi again is discarded, other alternatives cannot be ruled out by argumentation. phobp dephosphorylation may be inhibited by active phou or by the dephosphorylated form of the pstscab complex. in silico phenotypes of deletion mutants did not allow to discriminate between these alternatives, suggesting to investigate these alternatives with the help of in vitro experiments where the biochemical activity of the individual proteins on the phosphorylated form of phob is analysed. such in vitro data could certainly also be fed into the reconstruction algorithm. a final ambiguity in mechanisms can simply be resolved. the algorithm suggests that the cytoplasmic phoa protein is transported into the periplasm. alternatively, cytoplasmic phoa would disappear into an unknown pool and appear in the periplasm from an unknown pool in independent non-coupled reactions. as a protein appearing in the periplasm must have been synthesized in the cytoplasm at some point, transport across the cytoplasmic membrane in a prokaryotic cell seems to be the right mechanism rather than exocytosis through cytoplasmic vesicles. in summary, the algorithm found a core network with defined wiring. wiring alternatives found for four transitions can be discarded based on biological knowledge or suggested biochemically meaningful alternatives: activation of a reaction by one form of a protein or inhibition of the same reaction by its covalently modified or otherwise differently active form. discussion we have described a new algorithm for the reconstruction of extended petri nets from time series data sets. the algorithm delivers a complete list of solutions expressed in the form of petri nets all of which are compatible with the input data. as for the previously published method there is a guarantee through mathematical proof that the list of provided minimal models is complete, in that no possible alternative petri net is missing that might also be able to explain the data. the new algorithm however provides a significant advance in delivering petri nets with read arcs and inhibitory arcs, so-called extended petri nets. extended petri nets are more powerful and straigt-forward in representing regulatory interactions in signal transduction and genetic networks. encoding regulatory interactions including catalysis and inhibition with the help of simple place/transition petri nets is possible but it requires the introduction of additional places and transitions leading to an explosion of the number of generated solutions in network reconstruction through multiple alternative combinations of symmetric motifs redundant in terms of the encoded regulatory properties. by avoiding redundancy, the present algorithm allows to reconstruct networks from time series data sets that are obtained with mutants or e.g. after pharmacological intervention both of which can be regarded as structural alterations introduced into a network by targeting elements that exert regulatory control. using a model of the phosphate regulatory network of enterobacteria as a test case, the algorithm correctly reconstructed the petri net which was used to generate in silico time series data sets for wild-type cells, deletion mutants and site-directed mutants. for four transitions of the original network the algorithm found alternatively wired transitions that would also be consistent with the data set. the alternative wiring translates into reasonable alternative molecular mechanisms which might be tested experimentally. attempts to reconstruct a network from a time series data set where multiple components were measured in response to a specific perturbation typically gives a large number of alternative networks. the implicit representation of these networks e.g. as a column of controled reactions listed for each difference vector is useful to identify those difference vectors and in turn those components of the system, the ill-resolved wiring of which greately increases the number of alternative network structures. comparative analysis of time series measured with wild-type and mutants in different genes is an efficient way to reduce the number of alternative network structures delivered by the reconstruction algorithm. when sufficient experiments with different mutants are evaluated, the algorithm may give only one or few solutions as in the phosphate regulatory network that served as a test case in the present study. feeding the algorithm with even more data indeed might lead to a situation where not even a single solution is found without that additional components are introduced. the current algorithm does not support the introduction of additional components as an earlier implementation without read arcs did. this feature is to be implemented in a future version of the algorithm. according to the original definition, petri nets represent concurrent processes. transitions that have the licence to fire do not necessarily fire immediately which makes the behaviour of the network nondeterministic. reaction rates corresponding to rate constants in chemical kinetics can be introduced by assigning a probablilistic hazard function to each transition, yielding a stochastic petri net. for network reconstruction purposes, relative reaction rates can be encoded in the form of priorities to enforce in which temporal sequence competing transitions fire. considering priorities in the reconstruction process may again considerably reduce the number of alternative solutions. the present form of the algorithm does not consider priorities.  the algorithm described in this work reconstructs extended petri nets from time series data sets by finding all alternative minimal networks that are consistent with the data. it suggested reasonable alternative molecular mechanisms for certain reactions in the network that can be tested experimentally. the algorithm integrated data obtained for wild-type and for mutant cells and may, in the way shown, be useful to integrate physiological, biochemical, pharmacological, and genetic data into a consistent petri net model. the algorithm works with discretized data or with data that are per se discrete like e.g. the presence or the absence of a phenotype. we consciously keep computational methods of data discretization or statistical treatment of data strictly separated from the reconstruction algorithm. with reliable, i.e. statistically significant and reproducible experimental data sets, the algorithm can be used to obtain certified results based on the proven property to deliver all possible minimal networks. with enough input data, one may obtain one unique network. having data sets that give more or even many possible networks as solutions, the implicit representation of the networks can clearly show which firm conclusions can be drawn from the experimental data in terms of proven causal connections that are identical in all deliviered networks, and alternatives for the causal connection of components may be used for experimental design. the results presented in this work were obtained by manual computation. we are currently exploring the potential of answer set programming to efficiently compute large data sets to reconstruct large networks. 
as a non-trivial test case, the phosphate regulatory network of enterobacteria was reconstructed using in silico-generated time-series data sets on wild-type and in silico mutants. we have previously reported a mathematical method which is exclusively data-driven, does not involve any heuristic decisions within the reconstruction process, and deliveres all possible alternative minimal networks in terms of simple place/transition petri nets that are consistent with a given discrete time series data set. the new exact algorithm reconstructs extended petri nets from time series data sets by finding all alternative minimal networks that are consistent with the data. the results of the reconstruction algorithm are encoded in the form of an extended petri net involving control arcs. network inference methods reconstruct mathematical models of molecular or genetic networks directly from experimental data sets. the algorithm is useful to combine data from wild-type and mutant cells and may potentially integrate physiological, biochemical, pharmacological, and genetic data in the form of a single model. it suggested alternative molecular mechanisms for certain reactions in the network.
 network inference methods reconstruct mathematical models of molecular or genetic networks directly from experimental data sets. we have previously reported a mathematical method which is exclusively data-driven, does not involve any heuristic decisions within the reconstruction process, and deliveres all possible alternative minimal networks in terms of simple place/transition petri nets that are consistent with a given discrete time series data set.  we fundamentally extended the previously published algorithm to consider catalysis and inhibition of the reactions that occur in the underlying network. the results of the reconstruction algorithm are encoded in the form of an extended petri net involving control arcs. this allows the consideration of processes involving mass flow and/or regulatory interactions. as a non-trivial test case, the phosphate regulatory network of enterobacteria was reconstructed using in silico-generated time-series data sets on wild-type and in silico mutants.  the new exact algorithm reconstructs extended petri nets from time series data sets by finding all alternative minimal networks that are consistent with the data. it suggested alternative molecular mechanisms for certain reactions in the network. the algorithm is useful to combine data from wild-type and mutant cells and may potentially integrate physiological, biochemical, pharmacological, and genetic data in the form of a single model. 