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 tting the given data. To keep the solution set small while guaranteeing its completeness, the idea is to generate only Petri nets being minimal in the sense that all other networks tting the data contain the reconstructed ones. In this paper, we consider Petri nets with extensions in two directions: priority relations among the transitions of a network in order to allow the modelization of deterministic systems, and control-arcs in order to represent catalytic or inhibitory dependencies. We dene a containment relation for Petri nets taking both concepts, priority relations and controlarcs, into account. We discuss the consequences for extended Petri nets diering in their sets of control-arcs and priority relations, and the impact of our results towards the reconstruction of such Petri nets.
Introduction The aim of systems biology is to analyze and understand dierent phenomena as, e.g., responses of cells to environmental changes, host-pathogen interactions, or eects 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 reect the observed phenomena.
Depending on the biological aim and the type and quality of the available
data, dierent types of mathematical models are used and corresponding
methods for their reconstruction have been developed, see for instance [
Here we focus on Petri nets, a framework which turned out to coherently
model both static interactions in terms of networks and the dynamic processes
in terms of state changes [
To obtain models of this type, we developed in [
Our approach takes as input a set P of places and discrete time-series data X 0 given by sequences (x0; x1; : : : ; xm) of experimentally observed system states 1. The goal is to determine all Petri nets (P; T; A; w) that are able to reproduce the data, i.e., where T contains enough transitions to perform for each xj 2 X 0 the experimentally observed state change to xj+1 2 X 0. This leads to the notion of Petri nets being conformal with the data X 0; our approach guarantees to generate all of them being minimal in the sense that no superuous transitions occur in any network, see Section 1.2.
This combinatorial approach has been extended in two directions [
On the one hand, we introduced in [
On the other hand, we adapted the approach from [
To keep the solution set small while guaranteeing its completeness, the idea is to generate only Petri nets being minimal in the sense that all other networks tting the data contain the reconstructed ones. For that, it is required to carefully dene a notion of minimality taking both concepts, priority relations and controlarcs, into account. The diculty hereby is that priority relations and control-arcs are concurrent concepts to prevent enabled transitions from switching. 1 Any continuous experimental time-series data need to be discretized in a preprocessing step. As a consequence of this, reconstructing Petri nets, which show exactly the same behavior as a system of ordinary dierential equations cannot be expected in general. 2 In contrast to the normally used stochastic simulation, the aim of this approach is to force the reconstructed Petri net to show the observed behavior of the experiments in a simulation.
The contribution of this paper is to dene a containment relation for Petri nets and to discuss the consequences for extended Petri nets diering in their sets of control-arcs and priority relations (Section 2). Finally, we discuss the impact of our results towards the reconstruction of minimal X 0-deterministic extended Petri nets (Section 3). 1.1
Petri Nets A Petri net P = (P; T; A; w) is a weighted directed bipartite graph with two kinds of nodes, places and transitions. The places p 2 P represent the system components (e.g. proteins, enzymes, genes, receptors or their conformational states) and the transitions t 2 T stand for their interactions (e.g., chemical reactions, activations or causal dependencies). The arcs in A (P T ) [ (T P ) link places and transitions, and the arc weights w : A ! N reect stoichiometric coecients of the reactions.
Each place p 2 P can be marked with an integral number xp of tokens, and any marking denes a state x 2 NjP j of the system. In biological systems, all components can be considered to be bounded, as the value xp of any state refers to the concentration of the studied component p 2 P , which can only increase up to a certain maximum cap(p). This leads to a capacitated Petri net (P; cap), i.e., a Petri net P = (P; T; A; w) together with a capacity function cap : P ! N, whose set of potential states is X := fx 2 NjP j j xp cap(p)g.
An extended Petri net P = (P; T; (AS [ AR [ AI ); w) is a Petri net which has, besides the standard-arcs in AS , two additional sets of special arcs (so-called control-arcs): the set of read-arcs 3 AR P T and the set of inhibitor-arcs AI P T . The set of all control-arcs, i.e., the set AR [ AI , is denoted by AC .
A transition t 2 T is enabled in a state x 2 X of a capacitated and extended Petri net if all the following conditions are satised: (i) xp w(p; t) for all p with (p; t) 2 AS , (ii) xp + w(t; p) cap(p) for all p with (t; p) 2 AS , (iii) xp w(p; t) for all p with (p; t) 2 AR, (iv) xp < w(p; t) for all p with (p; t) 2 AI .
If a transition is not enabled, we say it is disabled. In the case that condition (iii) (resp. (iv)) does not hold, we say that t is disabled due to a read-arc (resp. disabled due to an inhibitor-arc ).
When a transition t is enabled in a state x it can switch, leading to a successor state x0 2 X (denoted by x !t x0) whose marking is obtained by x0p :=
xp + w(t; p); >8xp < >:xp; w(p; t); for all p with (p; t) 2 AS ; for all p with (t; p) 2 AS ; otherwise: 3 A read-arc (p; t) 2 AR, also called test-arc, can be simulated in a standard Petri net by two standard-arcs; namely by the arcs (p; t) 2 AS and (t; p) 2 AS, where w(p; t) = w(t; p).
In general there can be more than one transition enabled in a state x 2 X , and
the decision which transition switches is typically taken non-deterministically
(and the dynamic behavior is analyzed in terms of reachability, starting from
a certain initial state). This is not appropriate for biological system showing a
deterministic behavior where, e.g., a certain stimulation always results in the
same response. In this case, additional activation rules are required in order to
force the switch from a state xj to a specic successor state xj+1. For this
purpose, priorities between the transitions of the network can be used to determine
which of the enabled transitions has to be taken. Note that these priorities
typically reect the rate of the corresponding reactions where the fastest reaction
has highest priority. In Marwan et al. [
Note that priorities can prevent enabled transitions from switching: for a state x 2 X , let T (x) := ft 2 T j t is enabled in xg, then only a transition t 2 T (x) is allowed to switch or can switch if there is no other transition t0 2 T (x) with (t < t0) 2 O. The set of all transitions that are allowed to switch in x is denoted by
TP;O(x) := ft 2 T (x) j there is no t0 2 T (x) with (t < t0) 2 Og: In this paper we consider capacitated extended Petri nets with priorities (P; cap; O): extended Petri nets P = (P; T; A; w) with a capacity function cap : P ! N on their places and a partial order O T T on their transitions. 1.2
Reconstructing Petri Nets from Experimental Data Our main goal is to reconstruct Petri nets from experimental time-series data. We rst briey describe the input, the main idea, and the generated output of the reconstruction approach.
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. For each of them, a capacity cap(p) is given so that all system states are represented by vectors from X = fx 2 NjP j; xp cap(p)g.
To perform an experiment, the system is stimulated in a state (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 reecting the
time-dependent response of the system to the stimulation, denoted by X (x1) =
(x1; : : : ; xk): Typically, several experiments starting from dierent initial states
in a set Ini X are necessary to describe the whole phenomenon, and we obtain
experimental time-series data of the form X 0 = fX (x1) j x1 2 Inig; see Example
1 or Example 2 for illustration and [
Thus, the experimental setting is given by (P; cap; X 0), and the task is to nd all networks P = (P; T; AS ; w) with P as set of places which are appropriate to explain the experimentally observed behavior reported in X 0.
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 in T . 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 by a switching sequence of some length, where the intermediate states are not reported in X 0.
In a network P tting the experimental data, 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 of a transition t 2 T :
Mpt := >8 w(p; t) <
+w(t; p) >:0 if (p; t) 2 AS ; if (t; p) 2 AS ; 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:
t2T 0 Hence, to t the experimental data, it is required to include enough transitions to perform all experimentally observed switching sequences. More formally, a network P = (P; T; AS ; w) with incidence matrix M 2 ZjP j jT j is conformal with X 0 if, for each x1 2 Ini and any two consecutive states xj ; xj+1 2 X (x1), 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; :::; tk) of transition switches, i.e., there are states xj = y1; y2; :::; yk+1 = xj+1 with yl + M tl = yl+1 for 1 l k.
This leads to the following problem (Network Reconstruction Problem): Given the experimental setting (P; cap; X 0), generate all the networks P = (P; T; AS ; w) being conformal with X 0.
For details on the reconstruction approach to solve this problem, we refer
to [
This approach works only to reconstruct standard Petri nets. To rene the dynamic behavior of the reconstructed networks, two dierent extensions have been considered which both impose further conditions for an enabled transition: priority relations on the transitions to force a deterministic behavior and controlarcs to represent catalytic or inhibitory dependencies.
We next briey explain the corresponding extensions of the reconstruction
approach from [
To determine a suitable partial order for a network P = (P; T; AS ; w) being conformal with X 0, consider, for any two consecutively measured states xj ; xj+1 2 X 0, the for P selected sequence of intermediate states xj = y1; y2; : : : ; yk+1 = xj+1 and impose priority relations that force, in all those states yi, this transition to have highest priority which is required to reach yi+1.
For any such priority relation O, we obtain a (capacitated) Petri net with priorities (P; cap; O) which is X 0-deterministic, as it shows a prescribed behavior on the experimentally observed subset X 0 of states.
To reconstruct extended Petri nets, where enzymatic reactions and inhibitions are represented with the help of control-arcs, analyze the mass or signal ow experimentally observed in of potential catalytically acting components, generate and evaluate a resulting logical formula, and insert the corresponding control-arcs in the studied reconstructed network P = (P; T; AS ; w).
X 0 in dependency This leads to the reconstruction of (capacitated) extended Petri nets which are catalytically conformal with the given data.
The nal goal for the reconstruction is the combination of the two latter methods to a global reconstruction approach producing all X 0-deterministic extended Petri nets tting the given data X 0. To keep the solution set small while guaranteeing its completeness, the idea is again to generate only Petri nets being minimal in the sense that all other networks tting the data contain the reconstructed ones.
While minimality could be easily related to set inclusion of the transition sets of two standard Petri nets, the diculty for extended Petri nets with priorities is that priority relations and control-arcs are concurrent concepts to prevent enabled transitions from switching. Therefore, it is required to carefully dene a notion of minimality taking both concepts, priority relations and control-arcs, into account, which will be the subject of the next section.
Classication of
In this section, we consider capacitated extended Petri nets with priority relations, generated by a reconstruction approach from experimental data X 0 and, therefore, all being X 0-deterministic conformal networks. Formalizing a minimality concept for such Petri nets can be done by dening suitable equivalence classes, and selecting a minimal one as representative of each equivalence class. Hence, we rst have to dene an appropriate equivalence relation as well as an inclusion relation for the studied Petri nets, in order to classify the minimal elements w.r.t. inclusion within the equivalence classes.
In the literature there are several concepts for the equivalence of Petri nets,
two often used ones are marking equivalence (see, e.g., [
Marking equivalence is dened in terms of reachability in a Petri net P = (P; T; A; w). A sequence of transitions t1 : : : tk in T is called a feasible switching sequence for a state x0 2 X in P, if tj 2 T (xj 1) for all 1 j k. A marking xk is reachable from an initial marking x0, if there exists a feasible switching sequence from x0 to xk. Two Petri nets are marking equivalent, if they have the same set of reachable markings, starting from the same initial marking.
Two Petri nets are bisimilar if every feasible transition sequence in one Petri net is a feasible transition sequence in the other Petri net and vice versa.
The two concepts of marking and bisimulation equivalence are not suitable for our purpose, as we need to compare two X 0-deterministic conformal networks starting from all initial states x1 2 Ini X 0 (and not just from one initial marking), but only on the states reported in X (x1) = (x1; : : : ; xk) (and not on all intermediate system states between x1 and any reachable state xk). We, therefore propose to consider for any two consecutively measured states xj ; xj+1 2 X 0 only that xj+1 is reachable from xj in terms of a feasible transition sequence. Denition 1. Two X 0-deterministic extended Petri nets (P; cap; O), (P^; cap; O^) are X 0-equivalent if both P and P^ have the same incidence matrix.
One can easily verify that this is indeed an equivalence relation. Note that all X 0-deterministic extended Petri nets in the same equivalence class have not only the same set of places (and therefore the same set X of potential states), but also the sets of transitions, the sets of standard-arcs and their weights are equal. We next dene for such Petri nets an inclusion relation, obtained from strengthening the concept of bisimulation equivalence. For that, we call a sequence of transitions t1 : : : tk O-feasible for a state x0 of (P; cap; O) if tj 2 TP;O(xj 1) for all 1 j k.
Denition 2. Consider two X 0-equivalent extended Petri nets (P; cap; O) and (P^; cap; O^). We say P is included in P^, denoted by P P^, if and only if for all states x 2 X , every O^-feasible switching sequence for x in P^ is a O-feasible switching sequence for x in P.
In order to state the denition of minimal, we need the following notions. For an X 0-deterministic extended Petri net ((P; T; AS [ AC ; w); cap; O)), a control-arc (p; t) 2 AC is necessary, if ((P; T; AS [(AC nf(p; t)g); w); cap; O) is not conformal to X 0; a priority (t < t0) 2 O is necessary, if O n f(t < t0)g is not a partial order or (P; cap; O n f(t < t0)g) is not X 0-deterministic; a priority (t < t0) 2 O is strictly necessary , if (P; cap; O n f(t < t0)g) is not X 0-deterministic.
If a priority is not (strictly) necessary, we call this element (strictly) unnecessary. Denition 3. Among all X 0-equivalent extended Petri nets, P is minimal i P does neither have unnecessary elements nor is included in another Petri net P^ being X 0-equivalent to P.
Based on this inclusion relation for X 0-equivalent Petri nets we compare X 0deterministic extended Petri nets. Firstly, we provide a general statement on the inclusion of X 0-deterministic extended Petri nets.
Lemma 1. Let (P; cap; O) and (P^; cap; O^) be two X 0-equivalent Petri nets. Then P P^ holds i for all states x 2 X we have TP^;O^ (x) TP;O(x).
In order to classify X 0-deterministic extended Petri nets for inclusion, we consider (P; cap; O) and (P^; cap; O^) with P = (P; T; AS [ AC ; w) and P^ = (P; T; AS [ A^C ; w^), respectively, and distinguish the following cases: O O^ and AC = A^C ; O = O^ and AC A^C ; O O^ and AC A^C ;
O^ O and AC A^C .
In other words, our aim is to determine, when we can safely remove a priority or a control-arc to get a smaller X 0-deterministic extended Petri net. Lemma 2. Let (P; cap; O) and (P^; cap; O^) be two X 0-equivalent Petri nets with O O^ and AC = A^C . Then P P^ holds.
One could be tempted to ask for the converse, i.e., if for two X 0-equivalent Petri nets (P; cap; O) and (P^; cap; O^) with O = O^ and AC A^C , the inclusion P P^ follows. However, it turns out to be not true in general, as the following counter example demonstrates.
Example 1. Consider the two extended Petri nets (P; 1; O) and (P^; 1; O^) shown on the left and the right side of Figure 1, respectively. Both Petri nets are X10equivalent for X10 given by (1 0 0 0 0) ! (0 0 0 1 0); (1 1 1 0 0) ! (1 1 0 0 1) ! (0 1 0 1 1); (0 1 1 0 0) ! (0 1 0 0 1) (1) and satisfy O = O^ and AC A^C . However, the behavior of both nets diers in a state x1 := (1 0 1 0 0) (indicated as marking in Figure 1), since we have TP;O(x1) = ft2g and TP^;O^ (x1) = ft1g. Thus, neither P P^ nor P^ P holds. C t2 F C t3 A t1 D t1
E t2 A B t1 < t2, t2 < t3, t1 < t3
Petri nets (P; cap; O) and (P^; cap; O^), neither P general. This is demonstrated in the next example.
P^ nor P^ P follows in Example 2. Consider the two extended Petri nets (P; 1; O) and (P^; 1; O^) shown on the left and the right side of Figure 2, respectively. Both Petri nets are X20equivalent for X20 given by and satisfy O O^ and AC A^C . However, their behavior diers in state x2 := (1 0 1 0 0 0) (indicated as marking in Figure 2); since we have TP;O(x2) = ft3g but TP^;O^ (x2) = ft1g. Thus, neither P P^ nor P^ P holds.
We provide a necessary and a sucient condition for P Theorem 2, respectively.
O and AC A^C .
P^ in Theorem 1 and Theorem 1. Let (P; cap; O) and (P^; cap; O^) be two X 0-equivalent Petri nets with O^ O and AC A^C .
If we have P P^ then for all (t < t0) 2 O n O^, where (t < t0) is strictly necessary, t and t0 are not both enabled in any state in P^.
Theorem 2. Let (P; cap; O) and (P^; cap; O^) be two X 0-equivalent Petri nets and let O^ O and AC A^C . Furthermore, let every control-arc in A^C be necessary.
If for all (t < t0) 2 O n O^ the following properties hold: (i) t and t0 are not both enabled in any state in P^, (ii) there does not exist a transition t00 with (t00 < t) 2 O^, (iii) (t < t0) is strictly necessary in P, then P
Remark 1. Note that conditions (ii) and (iii) in Theorem 2 are indeed necessary, as there exist counter examples, where the claimed inclusion does not hold anymore, if one of the conditions (ii) or (iii) is dropped.
Remark 2. Finally, note that the presented concepts and approaches work for Petri nets with arbitrary capacities. For the examples, we only consider the binary case to keep the set of potential states small for the required calculations. 3
Conclusion
In this work, we address the problem of reconstructing capacitated extended
Petri nets with priorities from experimental time-series data X 0. Already in the
case of reconstructing standard Petri nets [
While minimality can be easily related to set inclusion of the transition sets of standard Petri nets, the diculty for extended Petri nets with priorities is that priority relations and control-arcs are concurrent concepts to prevent enabled transitions from switching.
Our contribution is to dene a notion of minimality taking both concepts into account. For that, we dene when two X 0-deterministic extended Petri nets are equivalent (X 0-equivalence), and provide an inclusion relation for such networks, which allows to determine minimal elements in a class of X 0-equivalent Petri nets.
Furthermore, we address the question to classify X 0-equivalent Petri nets for their inclusion. It turns out that the case O O^ and AC = A^C implies P P^ (Lemma 2), there exists a necessary and a sucient condition (Theorem 1 and Theorem 2, respectively) to conclude from O^ O and AC A^C that P P^ holds, whereas Petri nets with O = O^ and AC A^C or O O^ and AC A^C are incomparable in general (see Example 1 and Example 2, respectively).
Our further goal is to identify some additional properties for capacitated extended Petri nets with priorities, so that also for the latter two cases some sucient conditions for their inclusion can be imposed.
Moreover, note that the rst case with O O^ and AC = A^C obviously provides a test for inclusion, which can be easily performed.
Also the two conditions from Theorem 1 and Theorem 2 for the case O^ O
and AC A^C can be veried eciently, since the tests whether there is a state,
where two transitions t; t0 are both enabled, as well as that there is no other
transition t00 with (t00 < t) can be done in polynomial time by [
Hence, here we provided conditions, which imply an inclusion of two X 0equivalent Petri Nets, that can indeed be applied practically to reduce the solution set of the studied reconstruction approach.