The context of this work is the reconstruction of Petri net models for biological systems from experimental data. Such methods aim at generating all network alternatives fitting the given data. For a successful reconstruction, the data need to satisfy two properties: reproducibility and monotonicity. In this paper, we focus on a necessary preprocessing step for a recent reconstruction approach. We test the data for reproducibility, provide a feasibility test to detect cases where the reconstruction from the given data may fail, and provide a strategy to cope with the infeasible cases. After having performed the preprocessing step, it is guaranteed that the (given or modified) data are appropriate as input for the main reconstruction algorithm.
The aim of systems biology is to analyze and understand different phenomena as,
e.g., responses of cells to environmental changes, host-pathogen interactions, or
effects of gene defects. To gain the required insight into the underlying biological
systems, experiments are performed and the resulting experimental data have to
be interpreted in terms of models that reflect the observed phenomena.
Depending on the biological aim and the type and quality of the available data, different
types of mathematical models are used and corresponding methods for their
reconstruction have been developed. We focus on Petri nets, a framework which
turned out to coherently model both static interactions in terms of networks and
dynamic processes in terms of state changes [
In fact, a (standard) network P = (P; T; A; w) reflects the involved system components by places p 2 P and their interactions by transitions t 2 T , the arcs in A (P T ) [ (T P ) link places and transitions, and the arc weights w : A ! N reflect stoichiometric coefficients of the corresponding reactions. Moreover, each place p 2 P can be marked with an integral number xp of tokens defining a system state x 2 Zj+P j. If a capacity cap(p) is given for the places, then xp cap(p) follows and we obtain X := fx 2 NjP j : xp cap(p)g as set of potential states. A transition t 2 T is enabled in a state x if xp w(p; t) for all p with (p; t) 2 A (and xp + w(t; p) cap(p) for all (t; p) 2 A), switching or firing t yields a successor state succ(x) = x0 with x0p = xp w(p; t) for all (p; t) 2 A and x0p = xp + w(t; p) for all (t; p) 2 A. Dynamic processes are represented by sequences of such state changes.
Petri net models can be reconstructed from experimental time-series data by
means of exact, exclusively data-driven reconstruction approaches [
In general, there can be more than one transition enabled at a state. The decision which transition switches is typically taken randomly (and the dynamic behavior is analyzed in terms of reachability, starting from a certain initial state). To properly predict the dynamic behavior, (standard) Petri nets have to be equipped with additional activation rules to force the switching or firing of special transitions, and to prevent all others from switching.
This can be done by using priority relations and control-arcs and leads to
the notion of X 0-deterministic Petri nets [
For a successful reconstruction, the data X 0 need to satisfy two properties:
reproducibility (for each xj 2 X 0 there is a unique observed successor state
succX 0 (xj ) = xj+1 2 X 0) and monotonicity (meaning that all essential responses
are indeed reported in the experiments), see Section 2.1. Having reproducible
data is clearly evident for a successful reconstruction; the necessity of monotone
data is shown in [
In this paper, we focus on a necessary preprocessing step for the
reconstruction approach described in [
Reconstructing Petri Nets from Experimental Data
In this section we describe the input and the desired output of the reconstruction
method from [
First, a set of components P (later represented by the set of places) is chosen which is expected to be crucial for the studied phenomenon and which can be treated in terms of measurements1.
To perform an experiment, the system is stimulated in a state x0 (by external stimuli like the change of nutrient concentrations or the exposition to some pathogens) to generate an initial state x1 2 X . Then the system’s response to the stimulation is observed and the resulting state changes are measured at certain time points. This yields a sequence (x1; : : : ; xk) of states xi 2 X reflecting the time-dependent response of the system to the stimulation, denoted by
X 0(x1; xk) = (x0; x1; : : : ; xk): Note that we also provide the state x0 as the starting point for the stimulation, which will be needed later (see Section 3.2). Every sequence has an observed terminal state xk 2 X , without further changes of the system. The set of all terminal states in X 0 is denoted by Xt0erm.
For technical reasons, we interpret a terminal state xk 2 Xt0erm as a state which has itself as observed successor state, i.e., xk = succX 0 (xk).
Typically, several experiments starting from different initial states in a set Xi0ni X are necessary to describe the whole phenomenon, and we obtain experimental time-series data of the form
X 0 = fX 0(x1; xk) : x1 2 Xi0ni; xk 2 Xt0ermg:
We write x 2 X 0 to indicate that x is an element of a sequence X 0(x1; xk) 2 X 0.
Example 1. As running example, we consider the light-induced sporulation of
Physarum polycephalum [
In the best case, two consecutively measured states xj ; xj+1 2 X 0 are also consecutive system states, i.e., xj+1 can be obtained from xj by switching a single transition. This is, however, in general not the case (and depends on the chosen time points to measure the states in X 0), but xj+1 is obtained from xj 1 Possibly, it is known that a certain component plays a crucial role, but it is not possible to measure the values of that component experimentally. by a switching sequence of some length, where the intermediate states are not reported in X 0.
For a successful reconstruction, the data X 0 need to satisfy two properties: reproducibility and monotonicity. The data X 0 are reproducible if for each xj 2 X 0 there is a unique observed successor state succX 0 (xj ) = xj+1 2 X 0. Moreover, the data X 0 are monotone if for each such pair (xj ; xj+1) 2 X 0, the possible intermediate states xj = y1; y2; :::; ym+1 = xj+1 satisfy yp1 yp1 yp2 yp2 : : : : : : ym p ym p ym+1 for all p 2 P with xj p p ypm+1 for all p 2 P with xjp xj+1 and
p xjp+1.
Whereas reproducibility is obviously necessary, it was shown in [
Remark 1. When continuous data is discretized for the reconstruction approach, all local minima and maxima of the measured values have to be kept for each p 2 P to ensure monotonicity. A standard Petri net P = (P; T; A; w) fits the given data X 0 when it is able to perform every observed state change from xj 2 X 0 to succX 0 (xj ) = xj+1 2 X 0. This can be interpreted as follows. With P, an incidence matrix M 2 ZjP j jT j is associated, where each row corresponds to a place p 2 P of the network, and each column M t to the update vector rt of a transition t 2 T : rpt = Mpt := 8> w(p; t) <
+w(t; p)
>:0
if (p; t) 2 A;
if (t; p) 2 A;
otherwise:
Reaching xj+1 from xj by a switching sequence using the transitions from a
subset T 0 T is equivalent to obtain the state vector xj+1 from xj by adding
the corresponding columns M t of M for all t 2 T 0:
xj + X M t = xj+1:
Hence, T has to contain enough transitions to perform all experimentally
observed switching sequences. The network P = (P; T; A; w) is conformal with X 0
if, for any two consecutive states xj ; succX 0 (xj ) = xj+1 2 X 0, the linear
equation system xj+1 xj = M has an integral solution 2 NjT j such that is
the incidence vector of a sequence (t1; :::; tm) of transition switches, i.e., there
are intermediate states xj = y1; y2; :::; ym+1 = xj+1 with yl + M tl = yl+1
for 1 l m. Hereby, monotonicity avoids unnecessary solutions, since no
homogeneous solutions of equation (1) have to be considered, see [
To also force that the networks exhibit the experimentally observed dynamic
behavior in a simulation, we equip standard networks with additional activation
rules to further control the switching of enabled transitions, see [
On the one hand, the concept of control-arcs can be used to represent catalytic or inhibitory dependencies. An extended Petri net P = (P; T; (A [ AR [ AI ); w) is a Petri net which has, besides the (standard) arcs in A, two additional sets of so-called control-arcs: the set of read-arcs AR P T and the set of inhibitor-arcs AI P T . We denote the set of all arcs by A = A [ AR [ AI . Here, an enabled transition t 2 T coupled with a read-arc (resp. an inhibitorarc) to a place p 2 P can switch in a state x only if a token (resp. no token) is present in p; we denote by TA(x) the set of all such transitions.
On the other hand, in [
For a deterministic behavior, TA;O(x) must contain at most one element for
each state x to enforce that x has a unique successor state succX (x), see [
The extended Petri net P = (P; T; A; w) is catalytically conformal with X 0 if tl 2 TA(yl) for each intermediate state yl of any pair (xj ; xj+1) 2 X 0, and the extended Petri net with priorities (P; O) is X 0-deterministic if ftlg = TA;O(yl) holds for all yl.
The desired output of the reconstruction approach consists of the set of all X 0deterministic extended Petri nets (P; cap; O) (all having the same set P of places and the same capacities cap deduced from X 0 by cap(p) = maxfxp : x 2 X 0g).
Figure 2 shows an X 0-deterministic extended Petri net fitting the experimental data from Example 1.
FR t1
t4 Pr Pfr t2 R commited t3
Sp Before the reconstruction is started, a preprocessing step is necessary in order to verify or falsify whether the experimental time-series data X 0 is suitable for reconstructing X 0-deterministic extended Petri nets (see Section 3.1). If the test is successful, the reconstruction algorithm can be applied. For the case that the given data are not suitable for the reconstruction, we provide a method to handle the infeasible cases (see Section 3.2).
For that, we interpret (as in [
AD := f(xj ; xj+1) : xj+1 = succX 0 (xj )g for the observed responses, AS := f(x0; x1) : X 0(x1; xk) = (x0; x1; : : : ; xk)g for the stimulations. We call D(X 0) the experiment graph of X 0. It can be interpreted as a minor of the reachability graph, where observed responses may correspond to directed paths with intermediate states.
Our main objective is to test the given experimental time-series data X 0 for
reproducibility, i.e., whether each state x 2 X 0 has a unique successor state
succX 0 (x) 2 X 0. We provide a feasibility test to ensure this property (based
on previous tests for standard Petri nets [
X 0-Determinism Conflicts and Feasibility Test Definition 1. Let X 0 be experimental time-series data. We say that two timeseries Xi = X 0(xi0 ; xik ) and X` = X 0(x`0 ; x`m ) are in X 0-determinism conflict, when there exists a state x 2 X 0 with succXi (x) 6= succX` (x) and call x the corresponding X 0-determinism conflict state. We have a strong X 0-determinism conflict if xik 6= x`m or Xi = X`; a weak X 0-determinism conflict if xik = x`m and Xi 6= X`.
The definition of strong X 0-determinism conflicts includes the case discussed
in [
Example 2. In the experimental time-series data X 0 shown in Figure 1 we have no weak but two strong X 0-determinism conflicts: in the sequence X 0(x1; x4) the states x2 and x3 are equal but have different successor states, the sequences X 0(x5; x0) and X 0(x6; x8) have equal initial state x5 = x6, but different terminal states. Besides the initial states, the states x0 and x7 are X 0-determinism conflict states.
Obviously, every X 0-determinism conflict violates the condition of the data being reproducible, and the reconstruction of X 0-deterministic extended Petri nets from X 0 is not possible. However, the converse is true: Lemma 1. Let X 0 be experimental time-series data. If every state x 2 X 0 has a unique successor state succX 0 (x) 2 X 0 then there exists an X 0-deterministic extended Petri net.
Sketch of the proof. The pre-condition that every state has a unique successor in X 0 includes the cases that no non-terminal state has itself as successor and that no terminal state is an intermediate state of any experiment. This guarantees 2 Since P is only a projection from the real world, it is possible that some components of the system, crucial for the studied phenomenon, were not taken into account or could not be experimentally measured. the existence of a standard network P = (P; T; ; ) being conformal with X 0. Since every state has a unique successor state it follows for all states xj ; xl 2 X 0 with succ(xj ) 6= succ(xl) that there exists a non-empty subset P 0 P so that xjp 6= xlp holds for every p 2 P 0. Therefore, P can be made X 0-deterministic by adding appropriate control-arcs (p; t), where p 2 P 0 and t 2 T , in a way that exactly the transition is enabled which was observed in the experiments. tu
Two time-series X 0(xi0 ; xik ) and X 0(x`0 ; x`m ) with xik = x`m may be in weak X 0-determinism conflict, due to differently chosen time points of the measurements. We test the data for such a situation and try to resolve the conflict by linearizing these sequences, respecting monotonicity.
A linear order L (or total order ) on a set S is a partial order where additionally (a b) 2 L or (b a) 2 L holds for all a; b 2 S. In this case, we say that the set S is totally ordered (w.r.t. L). A totally ordered subset U S of a partially ordered set S is called a chain of S.
On a time-series X 0(x1; xk) = (x0; x1; : : : ; xk), a linear order is induced by the successor relation: xj xj+1 iff xj+1 = succX 0(x1;xk)(xj ), hence X 0 can be considered as a partially ordered set (ordered by the successor relation), where each time-series X 0(x1; xk) is a chain of X 0. Let succX 0 (xj ) = xj+1 and Box(xj ; xj+1) := (
xj y 2 X : p xjp yp yp xj+1
p xj+1 p if xjp if xjp xj+1 )
p xj+1 p : Note that due to monotonicity, all intermediate states y of any refined sequence from xj to xj+1 lie in Box(xj ; xj+1). Consequently, if two time-series Xi = X 0(xi0 ; xik ) and X` = X 0(x`0 ; x`m ) with xik = x`m are in weak X 0-determinism conflict, and x is a determinism conflict state then we have to test whether (i) succXi (x) 2 Box(x; succX` (x)) or (ii) succX` (x) 2 Box(x; succXi (x)), see Figure 3 for an illustration. If one of the two conditions holds, we conclude succXi (x) < succX` (x) (resp. succX` (x) < succXi (x)); otherwise we cannot find a X 0-deterministic linear order. Therefore, x is no longer a X 0-determinism conflict state, but a new X 0-determinism conflict state x0 is detected since either (i) x0 = succXi (x) has two successor states: succXi (succXi (x)), succX` (x) or (ii) x0 = succX` (x) has two successor states: succXi (x) and succX` (succX` (x)). Hence, the procedure has to be repeated for x0 until succXi (x0) = succX` (x0) holds or the test fails (see Algorithm 1). This works since in case of a weak X 0-determinism conflict at least the terminal states xik and x`m are equal.
Whenever the test described above is successful for x and all subsequent X 0-determinism conflict states x0, we say that it is resolvable, otherwise we say it is an unresolvable weak X 0-determinism conflict. We further obtain: Theorem 1. Let X 0 be experimental time-series data. There exists an X 0-deterministic extended Petri net if and only if there are neither strong X 0-determinism conflicts nor unresolvable weak X 0-determinism conflicts. xik = x`m
Sketch of the proof. If neither strong X 0-determinism conflicts nor unresolvable weak X 0-determinism conflicts exists, the statement follows from the procedure described above and from Lemma 1.
Conversely, suppose that an unresolvable weak (or strong) X 0-determinism conflict state exists. In the case that x = succX 0 (x) holds for at least one strong X 0-determinism conflict state x, then there does not exist any standard network being conformal with X 0. Otherwise, there exist conformal standard networks, but none of them can be made X 0-deterministic.
Let x be an unresolvable weak (or strong) X 0-determinism conflict state for two time-series Xi0 = X 0(xi0 ; xik ) and X`0 = X 0(x`0 ; x`m ). First note that x remains an unresolvable weak (or strong) X 0-determinism conflict state for every refined sequence (respecting the monotonicity constraint) of Xi0 and X`0. Thus, w.l.o.g. we can assume that succXi0 (x) 6= succX`0 (x) and denote the respective transitions by ti and t`. Since both transitions ti and t` are (and need to stay) enabled at x, there is no way to add priorities and/or control-arcs to force the network to deterministically show the observed behavior of Xi0 and of X`0 simultaneously. tu 3.2
Due to Theorem 1, it is impossible to reconstruct X 0-deterministic extended Petri nets from experimental time-series data X 0 containing a strong X 0-determinism conflict or an unresolvable weak X 0-determinism conflict. In this section we show how these conflicts can be resolved by using additional components.
For that we extend, as proposed in [
By using appropriate additional components, states that appear equal in
experimental time-series data X 0 become different in X 0 (see Figure 4 for an
illustration). It is already stressed in [
From Condition (i) we can conclude that we have x = succX 0 (x) if and only if x 2 Xterm. Condition (ii) ensures that a stimulation does not change 0 more than the target input component(s), and finally, Condition (iii) ensures a minimal number of label switches, while keeping the data as close as possible to the original measurements. Furthermore, due to symmetry reasons, we can choose a label for one state, e.g., a conflict state. Example 3. Besides symmetric solutions, there are two possible valid labelings with a = 1 for the experimental time-series data from Figure 1. These two solutions are shown in Figure 4. The solutions are obtained by applying the conditions of Definition 2 as follows. We start by selecting an X 0-determinism conflict state, here x2, and choose its label as xz2 = 0. Due to Condition (ii), xz5 = 0 follows. Condition (i) implies that x3 (resp. x6) must be different from x2 (resp. x5). Therefore, xz3 = 1 and xz6 = 1 follows. Since we have d4 = d5, Condition (iii) implies that the only valid labels for x0 and x7 are 0 and 1, respectively. Condition (ii) shows xz1 = 0. Finally, we can choose a label for x4 and x8, respectively. However, since d3 = d6, if follows from (iii) that both labels must be equal. where equations (2a) ensure that every state has a unique successor state (Condition (i) from Definition 2), equations (2b) that no stimulation changes the state of additional components (Condition (ii)), and equations (2c) preserve equal difference vectors (Condition (iii)). The conditions (2d) ensure that we have binary decision variables yij . Each valid labeling corresponds to a vector in P(a).
Note, due to inequalities (2a) the optimization problem is non-linear and has a non-convex set of feasible solutions. However, it is only necessary to find the minimal a so that P(a) 6= ;. We can consider the set P(a) as the union of 2a convex sets (see Figure 5 for an illustration). Therefore, we can split the problem into 2a linear subproblems, each having a convex (=polyhedral) feasible region. For that, we define two sets for each subproblem 1 k 2a, namely P +(k) and P (k), so that P +(k) [ P (k) = f1; : : : ; ag and P +(k) \ P (k) = ; and P +(p) 6= P +(q), P (p) 6= P (q) for all p 6= q. The sets induce the indices i so that yji yli (ypi yqi) 0 and yji yli (ypi yqi) 0, respectively. Hereby, we have all possible combinations. For the sake of readability let zjlpqi = yji yli (ypi yqi). Then we replace inequalities (2a) by the following constraints
X i+2P +(k) zjlpqi+ zjlpqi zjlpqi+ 0 0
X i 2P (k) zjlpqi 1 for all (xj ; xl); (xp; xq) 2 AD; (3a) for all i+ 2 P +(k); where AD := f(xj ; xl); (xp; xq) 2 AD with xj = xp; xl 6= xqg. These linear subproblems can be solved by standard solvers, and the optimal solution a of the original problem is obtained if one subproblem turns out to be feasible. All (minimal) valid labelings are then in P(a).
In this work, we give a preprocessing step for a reconstruction algorithm from [
Firstly, the preprocessing step examines the given experimental time-series data for reproducibility, i.e., it tests if all measured states x 2 X 0 have a unique successor state (see Section 3.1). If this test is successful we can reconstruct an X 0-deterministic extended Petri net (Lemma 1).
Whenever two time-series Xi and X` have a common state x but different successor states in each of these sequences (i.e., succXi (x) 6= succX` (x)) we have an X 0-determinism conflict. Depending on whether the terminal states of these conflicts are equal or not, we have a weak or a strong X 0-determinism conflict.
When we encounter a weak X 0-determinism conflict we try to linearize the two sequences by the induced order of the successor relation. This is done in the second step of the preprocessing (see Section 3.1).
If linearizing the time-series is not possible or when there are strong X 0-determinism conflicts, we cannot reproduce X 0-deterministic extended Petri nets (Theorem 1). In this case we extend the data by adding additional components to every state of X 0 (see Section 3.2). Finally, in order to compute valid vectors of additional components, we solve an optimization problem.
After having performed the preprocessing step, the reproducibility of the (given or modified) data X 0 can be guaranteed such that X 0 can serve as appropriate input for the main reconstruction algorithm.