=Paper=
{{Paper
|id=None
|storemode=property
|title=Reconstructing X´-deterministic extended Petri nets from experimental time-series data X´
|pdfUrl=https://ceur-ws.org/Vol-988/paper5.pdf
|volume=Vol-988
|dblpUrl=https://dblp.org/rec/conf/apn/FavreW13
}}
==Reconstructing X´-deterministic extended Petri nets from experimental time-series data X´==
https://ceur-ws.org/Vol-988/paper5.pdf
Reconstructing X 0 -deterministic extended Petri
nets from experimental time-series data X 0
Marie C.F. Favre? , Annegret K. Wagler
Laboratoire d’Informatique, de Modélisation et d’Optimisation des Systèmes
(LIMOS, UMR CNRS 6158), Université Blaise Pascal (Clermont-Ferrand II)
BP 10125, 63173 Aubière Cedex, France
marie.favre@isima.fr wagler@isima.fr
Abstract. This work aims at reconstructing Petri net models for biolog-
ical systems from experimental time-series data X 0 . The reconstructed
models shall reproduce the experimentally observed dynamic behavior
in a simulation. For that, we consider Petri nets with priority relations
among the transitions and control-arcs, to obtain additional activation
rules for transitions to control the dynamic behavior. The contribution
of this paper is to present an integrative reconstruction method, taking
both concepts, priority relations and control-arcs, into account. Our ap-
proach is based on previous works for special cases and shows how these
known steps have to be modified and combined to generate the desired
integrative models, called X 0 -deterministic extended Petri nets.
1 Introduction
The overall aim of systems biology is to analyze biological systems and to un-
derstand different phenomena therein as, e.g., responses of cells to environmen-
tal changes, host-pathogen interactions, or effects of gene defects. To gain the
required insight into the underlying biological processes, experiments are per-
formed and the resulting experimental data are interpreted in terms of models.
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. Our work is dedicated to Petri nets,
a framework which turned out to coherently model static interactions in terms
of networks and dynamic processes in terms of state changes, see e.g. [5,9]. A
network (P, T, A, w) reflects the involved system components by places p ∈ P
and their interactions by transitions t ∈ T , linked by weighted directed arcs.
Each place p ∈ P can be marked with an integral number of tokens defining a
|P |
system state x ∈ Z+ , dynamic processes are represented by sequences of state
changes, performed by switching or firing enabled transitions (see Section 2).
?
This work was founded by the French National Research Agency, the European
Commission (Feder funds) and the Région Auvergne in the Framework of the LabEx
IMobS3 .
G. Balbo and M. Heiner (Eds.): BioPPN 2013, a satellite event of PETRI NETS 2013,
CEUR Workshop Proceedings Vol. 988, 2013.
46 Favre, Wagler
Our central question is to reconstruct models of this type from experimen-
tal time-series data by means of an exact, exclusively data-driven approach.
We base our method on earlier results from [1,2,3,4,8,12]. This approach takes
as input a set P of places and discrete time-series data X 0 given by sequences
(x0 , x1 , . . . , xk ) of experimentally observed system states. The goal is to de-
termine all Petri nets (P, T, A, w) that are able to reproduce the data, i.e., that
perform for each xj ∈ X 0 the experimentally observed state change to xj+1 ∈ X 0
in a simulation. Hence, in contrast to the normally used stochastic simulation,
we require that for states where at least two transitions are enabled, the decision
between the different alternatives is not taken randomly, but a specific transition
is selected. For that, (standard) Petri nets have to be equipped with additional
activation rules to force the switching or firing of special transitions (to reach
xj+1 from xj ), and to prevent all others from switching. Analogously, the re-
construction approach needs to be extended accordingly. In previous works, we
considered two possible types of additional activation rules.
On the one hand, in [8,11,12] the concept of priority relations among the
transitions of a network was introduced in order to allow the modelization of
deterministic systems (see Section 2 for more details). This leads to the notion
of X 0 -deterministic Petri nets, which show a prescribed behavior on the experi-
mentally observed subset X 0 of states: the reconstructed Petri nets (P, T, A, w)
do not only contain enough transitions to reach the experimentally observed
successors xj+1 from xj , but exactly this transition will be selected among all
enabled ones in xj which is necessary to reach xj+1 .
On the other hand, in [1,2] the concept of control-arcs was used to represent
catalytic or inhibitory dependencies. Here, an enabled transition t ∈ T coupled
with a read-arc (resp. an inhibitory-arc) to a place p ∈ P can switch only if a
token (resp. no token) is present in p (see Section 2). This leads to the recon-
struction of extended Petri nets which are catalytic conformal with X 0 .
For consistently integrating both concepts, priority relations and control-arcs,
into the modeling framework, the difficulty is that both are concurrent concepts
to force or prevent the switching of enabled transitions. In [13], the notion of
X 0 -deterministic extended Petri nets is introduced as the desired output of an
integrative reconstruction method. The contribution of this paper is to present
the steps of such an approach, based on previous reconstruction methods for
special cases [1,2,3,4,8] , and to show how these known steps have to be modified
and combined to generate the desired integrative models (see Section 3).
2 Petri nets and extensions
A standard or simple Petri net P = (P, T, A, w) is a weighted directed bipar-
tite graph with two kinds of nodes, places and transitions. The places p ∈ P
represent the system components (e.g. proteins, enzymes, genes, receptors or
their conformational states) and the transitions t ∈ T stand for their interac-
tions (e.g., chemical reactions, activations or causal dependencies). The arcs in
Proc. BioPPN 2013, a satellite event of PETRI NETS 2013
Reconstructing X 0 -deterministic extended Petri nets 47
A ⊂ (P ×T )∪(T ×P ) link places and transitions, and the arc weights w : A → N
reflect stoichiometric coefficients of the corresponding reactions.
Each place p ∈ P can be marked with an integral number xp of tokens, and
any marking defines a state x ∈ N|P | 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 ∈ 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 := {x ∈ N|P | | xp ≤ cap(p)}. A transition
t ∈ T is enabled in a state x ∈ X of a capacitated Petri net if
E1 xp ≥ w(p, t) for all p with (p, t) ∈ A, and,
E2 xp + w(t, p) ≤ cap(p) for all p with (t, p) ∈ A
and we define T (x) := {t ∈ T : t satisfies E1, E2 in x}.
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 control-arcs by AC = AR ∪ AI , and the set of all arcs by
A = A ∪ AR ∪ AI .
In a capacitated extended Petri net, switching of transitions is additionally
controlled by read- and inhibitor-arcs; a transition t satisfying E1 and E2 can
switch only if also the following conditions hold:
E3 xp ≥ w(p, t) for all p with (p, t) ∈ AR , and,
E4 xp < w(p, t) for all p with (p, t) ∈ AI .
In an extended Petri net, a transition is enabled in a state x ∈ X if it satisfies
E1, . . . , E4 (otherwise, it is disabled ). The switch of a transition t enabled in x
leads to a successor state succX (x) = x0 ∈ X whose marking is obtained by
xp − w(p, t), for all p with (p, t) ∈ A,
x0p := xp + w(t, p), for all p with (t, p) ∈ A,
xp , otherwise.
In general, there can be more than one transition satisfying E1, . . . , E4 in
a state x ∈ X and we define TA (x) := {t ∈ T : t satisfies E1, . . . , E4 in x}.
The decision which transition switches is typically taken randomly (and the dy-
namic behavior is analyzed in terms of reachability, starting from a certain initial
state). This is not appropriate for modeling biological systems which show a de-
terministic behavior, e.g., where 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 x to a specific successor state succX (x). For this purpose,
priorities between the transitions of the network can be used to determine which
of the transitions in TA (x) has to be taken. Note that these priorities typically
reflect the rate of the corresponding reactions where the fastest reaction has
highest priority. In Marwan et al. [8] it is proposed to model such priorities with
the help of partial orders on the set T of transitions of the network P. Here, a
partial order O on T is a relation ≤ between pairs of elements of T respecting
Proc. BioPPN 2013, a satellite event of PETRI NETS 2013
48 Favre, Wagler
– reflexivity (i.e., t ≤ t holds for all t ∈ T ),
– transitivity (i.e., from t ≤ t0 and t0 ≤ t00 follows t ≤ t00 for all t, t0 , t00 ∈ T ),
– anti-symmetry (i.e., t ≤ t0 and t0 ≤ t implies t = t0 ).
We call (P, O) an (extended) Petri net with priorities, if P = (P, T, A, w) is an
(extended) Petri net and O a priority relation on T .
Note that priorities can prevent enabled transitions from switching: for a
state x ∈ X , only a transition t ∈ TA (x) is allowed to switch or can switch if
E5 there is no other transition t0 ∈ TA (x) with (t ≤ t0 ) ∈ O.
The set of all transitions that are allowed to switch in x is denoted by
TA,O (x) := {t ∈ T : t satisfies E1, . . . , E5 in x}.
To enforce a deterministic behavior, TA,O (x) must contain at most one element
for each x ∈ X to enforce that x has a unique successor succX (x), see [11] for
more details. Extended Petri nets with priorities satisfying this property are said
to be X -deterministic. For our purpose, we consider a relaxed condition, namely
that TA,O (x) contains at most one element for each experimentally observed
state x ∈ X 0 , but TA,O (x) may contain several elements for non-observed states
x ∈ X \ X 0 . We call such Petri nets X 0 -deterministic.
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. Our
goal is to reconstruct X 0 -deterministic extended Petri nets from given experi-
mental data X 0 .
3 Reconstructing X 0 -deterministic extended Petri nets
In this section, we describe the input, the main ideas, and the generated output
of our integrative reconstruction approach.
3.1 Input
A set of components P (later represented by the set of places) is chosen which is
expected to be crucial for the studied phenomenon. All known P -invariants 1 of
the system (e.g., different conformational stages of a cell, a receptor, a protein)
shall be collected in a set IP .
To perform an experiment, one first triggeres the system in some state x0
(by external stimuli like the change of nutrient concentrations or the exposition
to some pathogens), to generate an initial state x1 . Then the system’s response
to the stimulation is observed and the resulting state changes are measured
1
Laxly said, a P-invariant is a set P 0 ⊆ P of places (components) where the sum of
the number of all tokens on all the places in P 0 is constant. P-invariants are not
computed by the algorithm but must be known a priori by a biologist.
Proc. BioPPN 2013, a satellite event of PETRI NETS 2013
Reconstructing X 0 -deterministic extended Petri nets 49
for all components at certain time points. This yields a sequence of (discrete
or discretized) states xj ∈ Z|P | reflecting the time-dependent response of the
system to the stimulation in x1 , which typically terminates in a terminal state
xk where no further changes are observed. The corresponding experiment is
X 0 (x1 , xk ) = (x0 ; x1 , . . . , xk ).
0
Several experiments starting from different initial states in a set Xini ⊆ X 0,
reporting the observed state changes for all components p ∈ P at certain time
0
points, and ending at different terminal states in a set Xterm ⊆ X 0 describe the
studied phenomenon, and yield experimental time-series data of the form
X 0 = {X 0 (x1 , xk ) : x1 ∈ Xini
0
, xk ∈ Xterm
0
}.
Thus, the input of the reconstruction approach is given by (P, IP , X 0 ).
Example 1. As running example, we will consider experimental biological data
from the light-induced sporulation of Physarum polycephalum. The developmen-
tal decision of starving P. polycephalum plasmodia to exit the vegetative plas-
modial stage and to enter the sporulation pathway is controlled by environmental
factors like visible light [10]. One of the photoreceptors involved in the control
of sporulation Spo is a phytochrome-like photoreversible photoreceptor protein
which occurs in two stages PF R and PR . If the dark-adapted form PF R absorbs
far-red light F R, the receptor is converted into its red-absorbing form PR , which
causes sporulation [6]. If PR is exposed to red light R, it is photoconverted back
to the initial stage PF R , which prevents sporulation. Note that the changes be-
tween the stages PF R and PR can be experimentally observed due to a change
of color. The experimental setting consists of
P = {F R, R, PF R , PR , Spo} X 0 (x1 , x3 ) = (x0 ; x1 , x2 , x3 ) 0
Xini = {x1 , x4 }
IP = {PF R , PR } X 0 (x4 , x0 ) = (x2 ; x4 , x0 ) 0
Xterm = {x3 , x0 }
as input for the algorithm, we represent all observed states schematically in Fig 1.
1
x
1
0
x 0 1 2 3
x FR d1 x x
xF R 0 0 0 0
xR 0 0 0 d2 0
xPF R 1 0 0
0
xPR 0 1 1
1
xSpo 0 d4 R 0 1
0
1
0
x4
Fig. 1. A scheme illustrating the experimental time-series data described in Exp. 1
concerning the light-induced sporulation of Physarum polycephalum, where the entries
of the state vectors are interpreted as shown on the left (dashed arrows represent
stimulations, solid arrows responses).
Proc. BioPPN 2013, a satellite event of PETRI NETS 2013
50 Favre, Wagler
In the best case, two consecutively measured states xj , xj+1 ∈ 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 .
For a successful reconstruction approach, the data X 0 need to satisfy two
properties: reproducibility and monotonicity. The data X 0 are reproducible if for
each xj ∈ X 0 there is a unique observed successor state succX 0 (xj ) = xj+1 ∈ X 0 .
Moreover, the data X 0 are monotone if for each pair (xj , xj+1 ) ∈ X 0 , the possible
intermediate states xj = y 1 , y 2 , ..., y m+1 = xj+1 satisfy
yp1 ≤ yp2 ≤ . . . ≤ ypm ≤ ypm+1 for all p ∈ P with xjp ≤ xj+1
p and
yp1 ≥ yp2 ≥ . . . ≥ ypm ≥ ypm+1 for all p ∈ P with xjp ≥ xj+1
p .
Whereas reproducibility is obviously necessary, it was shown in [3] that mono-
tonicity 2 has to be required too. Due to monotonicity, a capacity cap(p) can be
determined from X 0 for each p ∈ P by cap(p) = max{xp : x ∈ X 0 }, but is not
required for the reconstruction.
3.2 Output
A capacitated extended Petri net with priorities (P, cap, O) with P = (P, T, A, w)
fits the given data X 0 when it is able to perform every observed state change
from xj ∈ X 0 to succX 0 (xj ) = xj+1 ∈ X 0 . This can be interpreted as follows.
With P, an incidence matrix M (P) ∈ Z|P |×|T | is associated, where each row
corresponds to a place p ∈ P of the network, and each column M (P)·t to the
update vector r t of a transition t ∈ T :
−w(p, t) if (p, t) ∈ A,
t
rp = M (P)pt := +w(t, p) if (t, p) ∈ A,
0 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 (P)·t of M (P) for all t ∈ T 0 :
X
xj + M (P)·t = xj+1 .
t∈T 0
Hence, T has to contain enough transitions to perform all experimentally ob-
served switching sequences. The underlying standard network P = (P, T, A, w) is
2
This is equivalent to say that system states in X 0 have been measured to appropriate
time points such that the values of their components do not oscillate between two
measured states or, equivalently, that all essential responses are indeed reported in
the experiments.
Proc. BioPPN 2013, a satellite event of PETRI NETS 2013
Reconstructing X 0 -deterministic extended Petri nets 51
conformal with X 0 if, for any two consecutive states xj , succX 0 (xj ) = xj+1 ∈ X 0 ,
the linear equation system
xj+1 − xj = M (P)λ
has an integral solution λ ∈ N|T | such that λ is the incidence vector of a
sequence (t1 , ..., tm ) of transition switches, i.e., there are intermediate states
xj = y 1 , y 2 , ..., y m+1 = xj+1 with y l + M (P)·tl = y l+1 for 1 ≤ l ≤ m.
The extended Petri net P = (P, T, A, w) is catalytic conformal with X 0 if
t ∈ TA (y l ) for each intermediate state y l , and the extended Petri net with
l
priorities (P, O) is X 0 -deterministic if {tl } = TA,O (y l ) holds for all y l .
The desired output of the reconstruction approach consists of the set of all
X 0 -deterministic extended Petri nets (P, cap, O) (all having the same set P of
places and the same capacities cap deduced from X 0 ).
3.3 Representation of the observed responses
To solve the problem of representing the observed responses by switching se-
quences, we propose the following approach, based on previous works in [4,8].
Extraction of difference vectors. As initial step, extract the observed changes of
states from the experimental data. For that, define the set
D := dj = xj+1 − xj : xj+1 = succX 0 (xj ) ∈ X 0 .
Example 2. From our running example in Fig. 1 we obtain D = {d1 , d2 , d4 }
with d1 = x2 − x1 = (−1, 0, −1, 1, 0)T , d2 = x3 − x2 = (0, 0, 0, 0, 1)T and
d4 = x0 − x4 = (0, −1, 1, −1, 0)T .
Generating the complete list of all X 0 -deterministic extended Petri nets P =
(P, T, A, w) includes finding the corresponding standard networks and their in-
cidence matrices M ∈ Z|P |×|T | .
The first step is to describe the set of potential update vectors which might
constitute the columns of M .
Representation of difference vectors. Recall that two consecutively measured
states xj , xj+1 ∈ X 0 are not necessarily consecutive system states, i.e., xj+1
may be obtained from xj by a switching sequence of some length, where the
intermediate states are not reported in X 0 . Due to monotonicity, the values of
the elements cannot oscillate in the intermediate states between xj and xj+1 .
Moreover,
P for any P -invariant P 0 ∈ IP , all suitable update vectors have to
j
satisfy p∈P 0 rp = 0. Hence, it suffices to represent any d ∈ D using only
vectors from the following set
0 ≤ rp ≤ djp if djp > 0
djp ≤ rp ≤ 0 if djp < 0
j |P |
Box(d ) = r ∈ Z : \ {0}.
P rp = 0 if djp = 0
0
p∈P 0 rp = 0 ∀P ∈ IP
Proc. BioPPN 2013, a satellite event of PETRI NETS 2013
52 Favre, Wagler
Remark 1. In previous approaches [4], none of the reconstructed (standard) net-
works must contain a transition enabled at any of the observed terminal states
xk ∈ Xterm
0
; hence all such vectors in Box(dj ) could be removed. This is not
the case for extended Petri nets as desired output of the reconstruction, since
the corresponding transitions can be disabled due to control-arcs. Here, we only
exclude the zero vector 0 as trivial update vector.
Next, we determine for any dj ∈ D, the set Λ(dj ) of all integral solutions of the
equation system X
dj = λt r t , λt ∈ Z+ .
r t ∈ Box(dj )
By construction, Box(dj ) and Λ(dj ) are always non-empty since dj itself is
always a solution due to the required reproducibility of the input data X 0 (which
particularly includes dj 6= 0 for all dj ∈ D). For each λ ∈ Λ(dj ), construct the
(multi-)set
R(dj , λ) = {rt ∈ Box(dj ) : λt 6= 0}
of update vectors used for this solution λ.
Example 3. For D from Exp. 2, the update vectors for a decomposition are
Box(d1 ) = {d1 , r 1 , r 2 }, Box(d2 ) = {d2 } and Box(d4 ) = {d4 , r 3 , r 4 } with
vectors r 1 = (−1, 0, 0, 0, 0)T , r 2 = (0, 0, −1, 1, 0)T , r 3 = (0, −1, 0, 0, 0)T and
r 4 = (0, 0, 1, −1, 0)T . Hence, the possible decomposition of the responses are
d1 = d1 = r 1 + r 2 , d2 = d2 and d4 = d4 = r 3 + r 4 and the resulting sets are
R(d1 , λ1 ) = {d1 }, R(d1 , λ2 ) = {r 1 , r 2 },
R(d2 , λ) = {d2 },
R(d4 , λ1 ) = {d4 }, R(d4 , λ2 ) = {r 3 , r 4 }.
3.4 Priority conflicts.
To compose all possible standard networks, we have to select exactly one solution
λ ∈ Λ(dj ) for each dj ∈ D and to take the union of the corresponding sets
R(dj , λ) in order to yield the columns M·t = r t of an incidence matrix M of
a conformal network. To ensure that the generated conformal networks can be
made X 0 -deterministic, we proceed as follows.
Sequences and their conflicts. Every permutation π = (r t1 , . . . , r tm ) of the el-
ements of a set R(dj , λ) gives rise to a sequence of intermediate states xj =
y 1 , y 2 , ..., y m , y m+1 = xj+1 with
σπ,λ (xj , dj ) = (y 1 , r t1 ), (y 2 , r t2 ), . . . , (y m , r tm ) .
By construction, every such sequence σ respects monotonicity and induces a
priority relation Oσ , since it implies which transition ti is supposed to have
highest priority (and thus switches) for every intermediate state y i .
Proc. BioPPN 2013, a satellite event of PETRI NETS 2013
Reconstructing X 0 -deterministic extended Petri nets 53
To impose valid priority relations O among all transitions of the reconstructed
networks, we have to take priority conflicts between priority relations Oσ induced
by different sequences σ into account.
Two sequences σ and σ 0 are in priority conflict if there are update vectors
0
r 6= r t and intermediate states y, y 0 such that t, t0 ∈ T (y) ∩ T (y 0 ) and (y, r t ) ∈
t
0
σ but (y 0 , r t ) ∈ σ 0 (since this implies t > t0 in Oσ but t0 > t in Oσ0 ).
We have a weak priority conflict (WPC) if y 6= y 0 and a strong priority
conflict (SPC) if y = y 0 . Note that a WPC can be resolved by adding appropriate
control-arcs, whereas a SPC cannot be resolved that way (see section 3.5).
Note that we have a strong priority conflict between the trivial sequence
σ(xk , 0) for any terminal state xk ∈ Xterm 0
and any sequence σ containing xk
as intermediate state. Such sequences σ are not catalytic conformal due to [2].
Example 4. From the running example, we obtain the following sequences
σ1 (x1 , d1 ) = ((x1 , d1 )) σ1 (x4 , d4 ) = ((x4 , d4 ))
σ2 (x1 , d1 ) = ((x1 , r 1 ), (x0 , r 2 )) σ2 (x4 , d4 ) = ((x4 , r 3 ), (x2 , r 4 ))
σ3 (x1 , d1 ) = ((x1 , r 2 ), (x5 , r 1 )) σ3 (x4 , d4 ) = ((x4 , r 4 ), (x6 , r 3 ))
σ(x2 , d2 ) = ((x2 , d2 )) σ(x3 , 0) and σ(x0 , 0)
where x5 = (1, 0, 0, 1, 0)T and x6 = (0, 1, 1, 0, 0)T . Between these sequences, we
have SPCs and WPCs as indicated in Fig. 2.
Construction of the priority conflict graph. To reflect the weak and strong pri-
ority conflicts between all possible sequences resulting from X 0 , we construct
a priority conflict graph G = (VD ∪ Vterm , ED ∪ EW ∪ ES ) where the nodes
correspond to sequences and the edges to priority conflicts:
– VD contains for all xj ∈ X 0 \Xterm
0
and the difference vector dj = succX 0 (xi )−
x , for all λ ∈ Λ(d ) and all permutations π of R(dj , λ) the sequence
i j
σπ,λ (xj , dj ).
– Vterm contains for all xk ∈ Xterm
0
the trivial sequence σ(xk , 0).
– ED contains all edges between two sequences σ, σ 0 stemming from the same
difference vector.
– ES reflects all strong priority conflicts between sequences σ, σ 0 stemming
from distinct difference vectors.
– EW reflects all weak priority conflicts between sequences σ, σ 0 stemming from
distinct difference vectors.
The edges in ED induce a clique partition Q of G in as many cliques 3 as there are
observed states in X 0 \ Xterm
0
resp. difference vectors in D: VD = Q1 ∪ . . . ∪ Q|D| .
Moreover, each node in Vterm corresponds to a clique of size 1, so that G is
partitioned into |X 0 | many cliques.
Example 5. The resulting priority conflict graph G of the running example is
shown in Fig. 2.
3
A clique is a subset of mutually adjacent nodes.
Proc. BioPPN 2013, a satellite event of PETRI NETS 2013
54 Favre, Wagler
Q1 Q3 Q4 Q3
σ1 (x1 , d1 ) σ(x3 , 0) σ1 (x4 , d4 )
Q2
σ2 (x1 , d1 ) σ(x2 , d2 ) σ2 (x4 , d4 )
σ3 (x1 , d1 ) σ(x0 , 0) σ3 (x4 , d4 )
Q0
Fig. 2. The conflict graph resulting from the sequences listed in Exp. 4, where bold
edges indicate SPCs, thin edges WPCs and gray boxes the clique partition.
Selection of suitable sequences. To obtain a network explaining all observations,
we have to select one sequence per difference vector dj , i.e., exactly one node
from each clique Qj ∈ Q. To encode the priority conflicts involving terminal
states, we require also to select all trivial sequences σ(xk , 0), i.e., all nodes from
Vterm . Thus, we are interested in subsets S ⊆ VD of cardinality |D| such that
|S ∩ Qj | = 1 for each Qj ∈ Q, and no SPCs occur in S ⊆ Vterm .
The set of all such solutions S ∪ Vterm can be encoded by all vectors x ∈
{0, 1}|VD ∪Vterm | satisfying
P
σ∈Qj xσ = 1 ∀Qj ∈ Q
xσ = 1 ∀σ ∈ Vterm
xσ + xσ 0 ≤ 1 ∀σσ 0 ∈ ES
xσ ∈ {0, 1} ∀σ ∈ VD ∪ Vterm .
Example 6. From G in Exp. 5, we obtain the following feasible subsets Si ∪Vterm
S1 = {σ1 (x1 , d1 ), σ(x2 , d2 ), σ1 (x4 , d4 )}, S3 = {σ1 (x1 , d1 ), σ(x2 , d2 ), σ3 (x4 , d4 )},
S2 = {σ3 (x1 , d1 ), σ(x2 , d2 ), σ1 (x4 , d4 )}, S4 = {σ3 (x1 , d1 ), σ(x2 , d2 ), σ3 (x4 , d4 )}.
Composition of conformal networks. Every selected subset S ∪Vterm corresponds
to a standard network PS = (P, TS , AS , w) which is conformal with X 0 (but not
yet necessarily X 0 -deterministic):
– we obtain the columns of the incidence matrix MS of the network by taking
the union of all sets R(dj , λ) corresponding to the sequences σ = σπ,λ (xj , dj )
selected by σ ∈ S;
– there might be weak priority conflicts σσ 0 ∈ EW for nodes σ, σ 0 ∈ S ∪ Vterm
which have to be resolved subsequently by inserting appropriate control-arcs.
Example 7. We apply the method only to the feasible set S1 ∪ Vterm from Exp. 6
(all solutions for S2 ∪ Vterm , S3 ∪ Vterm and S4 ∪ Vterm are presented in Exp. 9).
We construct the standard network presented in Fig. 3 with TS1 = {d1 , d2 , d4 }.
There is a priority conflict between σ(x2 , d2 ) and σ(x0 , 0) due to d2 , 0 ∈ T (x2 )∩
T (x0 ).
Proc. BioPPN 2013, a satellite event of PETRI NETS 2013
Reconstructing X 0 -deterministic extended Petri nets 55
PR
d1 d4
FR R
PF R
d2 Spo
Fig. 3. Standard network PS1 = (P, TS1 , AS1 , w) from solution S1 (Exp. 6)
3.5 Inserting control-arcs.
For each of the yet reconstructed standard networks PS = (P, TS , AS , w) re-
sulting from a selected subset S from the previous reconstruction step, we have
to determine appropriate control-arcs in order to resolve weak priority conflicts
corresponding to edges σσ 0 ∈ EW with σ, σ 0 ∈ S ∪ Vterm (if any), in order to
turn PS into a catalytic conformal extended Petri net PS = (P, TS , AS , w).
Recall that we have a weak priority conflict between two sequences σ and
0
σ 0 if there are update vectors r t 6= r t and intermediate states y 6= y 0 with
0
t, t ∈ T (y) ∩ T (y ) such that (y, r ) ∈ σ but (y 0 , r t ) ∈ σ 0 . This weak priority
0 0 t
conflict has to be resolved by adding appropriate control-arcs such that
– the update vector r t becomes a transition t with t ∈ TA (y) but t 6∈ TA (y 0 )
(or vice versa) if y, y 0 6∈ Xterm
0
or
t
– the update vector r becomes a transition t with t ∈ TA (y) which is disabled
by control-arcs in y 0 if y 0 ∈ Xterm
0
.
Inserting control-arcs This task can be done by using similar techniques as
proposed in [1,2]. Let P (y, y 0 ) be the set of places where y and y 0 differ, i.e.,
P (y, y 0 ) = {p ∈ P : yp 6= yp0 }. In order to disable transition t resulting from r t
at y 0 , we can include either
– a read-arc (p, t) ∈ AR with weight w(p, t) > yp0 for some p ∈ P (y, y 0 ) with
yp > yp0 or
– an inhibitor-arc (p, t) ∈ AI with weight w(p, t) < yp for some p ∈ P (y, y 0 )
with yp < yp0 .
Each of the so-determined control-arcs defines a transition t with the desired
properties (inheriting the standard arcs from r t and having either a read-arc or
an inhibitor-arc as described above).
Remark 2. In case of a SPC involving states y = y 0 , the set P (y, y 0 ) becomes
empty and it is, therefore, not possible to resolve a SPC by control-arcs.
For every reconstructed standard network PS = (P, TS , AS , w) and any sub-
set P 0 ⊆ P containing exactly one place from P (y, y 0 ) for every weak priority
conflict, we get a catalytic conformal extended Petri net PS,P 0 = (P, TS , AS,P 0 , w)
by inserting the respective control-arcs for all p ∈ P 0 .
Proc. BioPPN 2013, a satellite event of PETRI NETS 2013
56 Favre, Wagler
Example 8. We define control-arcs to resolve the WPC between σ(x2 , d2 ) and
σ(x0 , 0) for the network PS1 . We obtain
P (x2 , x0 ) = {PF R , PR } by x2 = (0, 0, 0, 1, 0)T and x0 = (0, 0, 1, 0, 0)T .
Any non-empty subset of P (x2 , x0 ) can be used to disable d2 at x0 ∈ Xterm 0
.
2 0 2
For PF R , xPF R < xPF R holds, leading to an inhibitor-arc (PF R , d ) ∈ AS1 ,P 0 ,
and for PR , x2PR > x0PR holds, leading to a read-arc (PR , d2 ) ∈ AS1 ,P 0 both with
weight 1. The two possible alternatives are presented in Fig. 4.
PR PF R
d1 d4 d4 d1
FR R R FR
PF R PR
d2 Spo d2 Spo
Fig. 4. The two catalytic conformal networks resulting from PS1 in Exp. 8
3.6 Determining priority relations
To generate the required priorities for each of the yet reconstructed extended
networks PS,P 0 = (P, TS , AS,P 0 , w), we only need to set the priorities among all
the transitions in TS according to the sequences selected for S.
Recall that every σ ∈ S stands for a sequence
σ = σπ,λ (xj , dj ) = (y 1 , r t1 ), (y 2 , r t2 ), . . . , (y m , r tm )
which induces a priority relation Oσ indicating that the transition ti resulting
from r ti is supposed to have highest priority at y i . That is, Oσ is defined by
n o
Oσ = ti > t : t ∈ TAS,P 0 (y i ) \ ti , 1 ≤ i ≤ m .
By construction, there are no priority conflicts in the extended network PS,P 0
between Oσ and Oσ0 for any σ, σ 0 ∈ S, thus we obtain the studied partial order
[
OS,P 0 = Oσ .
σ∈S
This implies finally that every extended network PS,P 0 = (P, TS , AS,P 0 , w) to-
gether with the partial order OS,P 0 constitutes an X 0 -deterministic extended
Petri net fitting the given data X 0 .
Proc. BioPPN 2013, a satellite event of PETRI NETS 2013
Reconstructing X 0 -deterministic extended Petri nets 57
Example 9. For the running example, it is left to determine the priority relations.
For the extended Petri nets PS1 ,P 0 , we can easily verify that TAS1 ,P 0 (x) contains
exactly one transition for all x ∈ X 0 , so no priorities are implied and OS1 ,P 0 = ∅
follows. For the Petri nets coming from the other sets S2 , S3 , S4 , all possible
minimal X 0 -deterministic extended Petri nets are depicted in Fig. 5, 6 and 7.
PR PF R
r1 FR r2 d4 d4 r2 FR r1
R R
PF R PR
d2 Spo d2 Spo
Fig. 5. From S2 , two catalytic conformal networks PS2 result, both with priority rela-
tions O2 = {(r 2 > r 1 )}.
PR PF R
d1 r4 r4 d1
FR FR
PF R PR
r3 R R r3
Spo Spo
d2 d2
PR PF R
d1 r4 R r3 r3 R r4 d1
FR FR
PF R PR
d2 Spo d2 Spo
Fig. 6. From S3 , four minimal catalytic conformal networks PS3 result, all with priority
relations O3 = {(r 4 > r 3 )}.
Proc. BioPPN 2013, a satellite event of PETRI NETS 2013
58 Favre, Wagler
PR PF R
r1 FR r2 r4 r4 r2 FR r1
PF R PR
r 3 R R r3
Spo Spo
d2 d2
PR PF R
r1 FR r2 r4 R r3 r3 R r4 r2 FR r1
PF R PR
d2 Spo d2 Spo
Fig. 7. From S4 , four minimal catalytic conformal networks PS4 result, all with priority
relations O4 = {(r 2 > r 1 ), (r 4 > r 3 )}.
4 Concluding remarks
To summarize, we present in this paper the steps of an integrative reconstruc-
tion method to generate all possible X 0 -deterministic extended Petri nets from
monotone and reproducible experimental time-series data X 0 .
This approach is based on previous works for special cases: the reconstruction
of standard networks [4], standard networks with priorities [8] and extended Petri
nets [1,2]. Here, we modify and generalize the previous methods by
– adjusting the representation of the observed difference vectors dj to the
case of extended networks with priorities (where dj might be enabled at a
0
terminal state in Xterm ),
– refining the idea from [8] to construct a priority conflict graph by distinguish-
ing weak and strong priority conflicts (where only strong conflicts affect the
selection),
– generalizing the method from [1,2] such that weak priority conflicts can be
resolved by inserting control-arcs (where arbitrary arcs weights can occur).
Note that a preprocessing (to test the experimental data X 0 for reproducibil-
ity and, if necessary, to handle infeasible situations) can be handled similar as in
[4] and a postprocessing (to keep only ”minimal” solutions in the sense that all
other X 0 -deterministic extended Petri nets fitting the data contain the returned
ones) is presented in [13].
In total, this integrative approach is promising for the reconstruction of net-
works fully fitting the experimentally observed phenomena.
Our further goal is to make the new approach accessible by a suitable imple-
mentation, e.g., using Answer Set Programming as in the case of the reconstruc-
Proc. BioPPN 2013, a satellite event of PETRI NETS 2013
Reconstructing X 0 -deterministic extended Petri nets 59
tion of standard networks with priorities [7] and to apply it to new biological
experimental data.
References
1. M. Durzinsky, W. Marwan, and A. K. Wagler. Reconstruction of extended Petri
nets from time series data and its application to signal transduction and to gene
regulatory networks. BMC Systems Biology, 5, 2011.
2. M. Durzinsky, W. Marwan, and A. K. Wagler. Reconstruction of extended Petri
nets from time-series data by using logical control functions. Journal of Mathe-
matical Biology, 66:203–223, 2013.
3. M. Durzinsky, A. K. Wagler, and R. Weismantel. A combinatorial approach to
reconstruct Petri nets from experimental data. In Monika Heiner and Adelinde M.
Uhrmacher, editors, CMSB, volume 5307 of Lecture Notes in Computer Science,
pages 328–346. Springer, 2008.
4. M. Durzinsky, A. K. Wagler, and R. Weismantel. An algorithmic framework for
network reconstruction. Journal of Theoretical Computer Science, 412(26):2800–
2815, 2011.
5. I. Koch and M. Heiner. Petri nets. In B. H. Junker, F. Schreiber, editors, Biological
Network Analysis, Wiley Book Series on Bioinformatics, pages 139–179, 2007.
6. T. Lamparter and W. Marwan. Spectroscopic detection of a phytochrome-like pho-
toreceptor in the myxomycete physarum polycephalum and the kinetic mechanism
for the photocontrol of sporulation. Photochem Photobiol, 73:697–702, 2001.
7. M. Durzinsky M. Ostrowski, T. Schaub and W. Marwan. Automatic network
reconstruction using ASP. Th. and Practice of Logic Progr., 11:749–766, 2011.
8. W. Marwan, A. K. Wagler, and R. Weismantel. A mathematical approach to
solve the network reconstruction problem. Math. Methods of Operations Research,
67(1):117–132, 2008.
9. J. W. Pinney, R. D. Westhead, and G. A. McConkey. Petri net representations in
systems biology. Biochem. Soc. Tarns., 31:1513–1515, 2003.
10. C. Starostzik and W. Marwan. Functional mapping of the branched signal trans-
duction pathway that controls sporulation in Physarum polycephalum. Photochem.
Photobiol., 62:930–933, 1995.
11. L. M. Torres and A. K. Wagler. Encoding the dynamics of deterministic systems.
Math. Methods of Operations Research, 73:281–300, 2011.
12. A. K. Wagler. Prediction of network structure, In: Modeling and System Biology, I.
Koch, F. Schreiber, W. Reisig (eds.) Computational Biology 16. Springer London,
pages 309–338 2010.
13. A. K. Wagler and J.-T. Wegener. On minimality and equivalence of Petri nets.
Proceedings of Concurrency, Specification and Programming CS&P’2012 Work-
shop, 2:382–393, 2012.
Proc. BioPPN 2013, a satellite event of PETRI NETS 2013