Petri nets have become an effective formalism to model biological systems. However, attempts to simulate biological systems by low-level Petri nets are restricted to relatively small models, and they tend to grow quickly for modeling complex systems, which makes it more difficult to manage and understand the nets. Motivated by this, we propose a colored Petri net-based framework for modeling, simulating, and analyzing complex biological systems. We give the definitions of biochemically interpreted colored qualitative Petri nets (QP N C ) and colored stochastic Petri nets (SP N C ) and describe their functionalities and features implemented in the Petri net tool Snoopy. We use two examples, the cooperative ligand binding and the repressilator, to demonstrate how to construct and simulate QP N C and SP N C models, respectively.
With the rapid growth of data being generated in the biological field, it has become necessary to organize the data into coherent models that describe system behavior, which are subsequently used for simulation, analysis or prediction. A large variety of modeling approaches has already been applied to modeling a wide array of biological systems (see [HK09] for a review). Among them, Petri nets are especially suitable for representing and modeling the concurrent, asynchronous, and dynamic behavior of biological systems, which were first introduced to the qualitative analysis of the biochemical reaction systems by Reddy et al. [RML93]. Motivated by the qualitative analysis of Petri nets, many applications of Petri nets (e.g. stochastic Petri nets, timed Petri nets, continuous Petri nets, and hybrid Petri nets, etc.) have been developed for modeling and simulating biological systems [GH06]. Since biological processes are inherently stochastic, stochastic Petri nets have recently become a modeling paradigm for capturing their complex dynamics, which can help to understand the behavior of complex biological systems by integrating detailed biochemical data and providing quantitative analysis results, see e.g. [JP98], [NOG+05], [PRA05].
Petri nets provide a formal and clear representation of biological systems based on their firm mathematical foundation for the analysis of biochemical properties. However, low-level Petri nets do not scale. So attempts to simulate biological systems by low-level Petri nets have been mainly restricted so far to relatively small models. They tend to grow quickly for modeling complex systems, which makes it more difficult to manage and understand the nets, thus increasing the risk of modeling errors [Mur07]. Two known modeling concepts improving the situation are hierarchy and color. Hierarchical structuring has been discussed a lot, see e.g. [MWW09], while the color has gained little attention so far. Thus, we investigate how to apply colored Petri nets to modeling and analyzing biological systems. To do so, we not only provide compact and readable representations of complex biological systems, but also do not lose the analysis capabilities of low-level Petri nets, which can still be supported by automatic unfolding. Moreover, another attractive advantage of colored Petri nets for a biological modeler is that they provide the possibility to easily increase the size of a model consisting of many similar subnets just by adding colors.
In this paper, we propose a colored Petri net-based framework for modeling, simulating, and analyzing biological systems. We are developing tools to support this new framework. Two prototypes for colored qualitative Petri nets (QP N C ) and colored stochastic Petri nets (SP N C ) have been implemented in Snoopy, a tool for modeling and animating/simulating hierarchical graph-based formalisms [Sno10]. We will describe these two prototypes and some applications.
This paper is organized as follows. Section 2 outlines the colored Petri netbased framework for modeling, simulating and analyzing biological systems and gives the definitions of QP N C and SP N C . Section 3 discusses the functionalities and features for QP N C and SP N C , which have been implemented in Snoopy. Section 4 shows how to construct basic colored Petri net components, and gives two examples to demonstrate QP N C and SP N C , respectively. Section 5 summarizes related work. Finally, conclusions and outlook are given. 2
In this section, we propose a colored Petri net-based framework for modeling, and simulating/analyzing biological systems, illustrated in Fig. 1, which extends the Petri net-based framework for modeling, and simulating/analyzing biological systems introduced in [GHL07], i.e., the new proposed framework is in fact the colored version of the existing framework. Both of these frameworks unify the qualitative, stochastic and continuous Petri net paradigms, but the colored version provides more compact and readable representations of complex biological systems.
The new framework relates three modeling paradigms: QP N C , SP N C , and colored continuous Petri nets (CP N C ), just like the Petri net-based framework that relates qualitative Petri nets (QP N ), stochastic Petri nets (SP N ) and continuous Petri nets (CPN). QP N C is an abstraction of SP N C and CP N C , while SP N C and CP N C are mutually related by approximation. The user can refer to [GHL07] to take a closer look at the detailed relationship between these three paradigms. In the following, we will describe QP N C and SP N C in detail, but not CP N C as we have not investigated CP N C yet. We assume basic knowledge of the standard notions of qualitative place/transition Petri nets, see e.g. [Mur89], [HGD08]. In the following, we will briefly describe QP N , and then give the definition of QP N C .
QP N is the basic Petri net class, which consists of places, transitions, and arcs. QP N does not associate a time with transitions or the sojourn of tokens at places, and thus is time-free [GHL07]. QP N C is a colored extension of QP N .
Colored Petri nets were first proposed by Jensen [Jen81], which combine Petri nets with capabilities of programming languages to describe data types and operations, thus providing a flexible way to create compact and parameterizable models. In colored Petri nets, tokens are distinguished by the ”color”, rather than having only the ”black” one. Besides, arc expressions, an extended version of arc weights, specify which tokens can flow over the arcs, and guards that are in fact Boolean expressions define additional constraints on the enabling of the transitions [JKW07]. In the following, we give the definition of the QP N C based on the definition of colored Petri nets by Jensen [JKW07]. Here we denote by EXP the set of expressions that comply with a predefined syntax, which are used as arc expressions, guards, etc.
Definition 1. A QP N C is a tuple < P, T, F, P, C, g, f, m0 >, where: – P is a finite, non-empty set of places. – T is a finite, non-empty set of transitions. – F is a finite set of directed arcs, such that F ⊆ (P × T ) ∪ (T × P ). – P is a finite, non-empty set of types, also called color sets. – C : P → P is a color function that assigns to each place p ∈ P a color set
C(p) ∈ P. – g : T → EXP is a guard function that assigns to each transition t ∈ T a guard expression that has the Boolean type. – f : F → EXP is an arc function that assigns to each arc a ∈ F an arc expression that has a multiset type C(p)MS , where p is the place connected to the arc a, and C(p)MS is the multiset on the color set C(p). – m0 : P → EXP is an initialization function that assigns to each place p ∈ P an initialization expression that has a multiset type C(p)MS .
QP N C is a colored extension of the qualitative place/transition net extended by different kinds of arcs, e.g., inhibitor arc and read arc [HRR+08]. These kinds of arcs are not explicitly denoted in the definition above. 2.2
Colored Stochastic Petri Nets (SP N C ) In this section, we will briefly recall stochastic Petri nets (SP N ) and their extensions, and then introduce colored stochastic Petri nets (SP N C ).
SP N are an extension of qualitative place/transition Petri nets. As with a qualitative Petri net, a stochastic Petri net maintains a discrete number of tokens on its places. But contrary to the time-free case, a firing rate (waiting time) is associated with each transition, which is a random variable, defined by an exponential probability distribution. The semantics of a stochastic Petri net is described by a continuous time Markov chain (CTMC). The CTMC of a stochastic Petri net without parallel transitions is isomorphic to the reachability graph of the underlying qualitative Petri net, while the arcs between the system states are now labelled by the transition rates [HLG+09].
There are quite a number of various extensions based on the fundamental stochastic Petri net class SP N , see e.g. [MBC+95], [Ger01]. For example, generalized stochastic Petri nets (GSP N ) are stochastic Petri nets (SP N ) extended by inhibitor arcs and immediate transitions. Deterministic and stochastic Petri nets (DSP N ) are generalized stochastic Petri nets (GSP N ) extended by deterministic transitions [HLG+09].
While SP N and its extensions offer enormous modeling power, managing large-scale Petri net models is difficult due to the fact that tokens are indistinguishable. To alleviate this limitation, the SP N C is presented to uplift biochemically interpreted extended stochastic Petri nets introduced in [HLG+09] to a colored version. As in the QP N C , in the SP N C , tokens are distinguished by the ”color”, and arc expressions and guards have the same meaning. Before expressions are evaluated to values, the variables in the expressions must get assigned values, which is called binding. A binding of a transtion t ∈ T exactly corresponds to a transition instance, denoted by t(b), i.e., each binding will become an uncolored transition after unfolding. The set of all bindings for a transition t constitutes the set of all the instances of transition t, denoted by T I(t). The set of all instances for all transitions T of a net is denoted by T I(T ). In contrast, each color c ∈ C(p) for a place p ∈ P exactly corresponds to a place instance, denoted by p(c), i.e., each color will become an uncolored place after unfolding. We let P I(p) denote all the instances of a place p and P I(P ) all the instances of all places P of a net. In the following, we give the definition of SP N C based on QP N C . Definition 2. A biochemically interpreted colored stochastic Petri net SP N C is a tuple < P, T, F, P, C, g, f, v, l, m0 >, where: – < P, T, F, P, C, g, f, m0 > is a QP N C . – T is refined as the union of three disjoint transition sets, i.e. T := Tstoch ∪ Tim ∪ Ttimed with: • Tstoch, the set of stochastic transitions with exponentially distributed waiting time, • Tim, the set of immediate transitions with waiting time zero, and • Ttimed, the set of transitions with deterministic waiting time. – F is refined as the union of two disjoint arc sets, i.e., F := FN ∪ FI with: • FN ⊆ (P × T ) ∪ (T × P ) is the set of directed standard arcs, • FI ⊆ P × T is the set of directed inhibitor arcs. – v : T I(Tstoch) → H is a function that assigns a stochastic hazard function h(t(b)) to each transition instance t(b) ∈ T I(t) of each transition t ∈ Tstoch, whereby H := St(b)∈T I(T ){ht(b)|ht(b) : N|•t(b)| → R+} is the set of all stochas0 tic hazard functions, and v(t(b)) = h(t(b)) for all transitions t ∈ Tstoch. – l : T I(Ttimed) → R+ assigns a non-negative deterministic waiting time to each transition instance t(b) ∈ T I(t) of each deterministic transition t ∈ Ttimed.
Please note, the stochastic hazard function in SP N C is defined for each transition instance of each colored transition. The domain of h(t(b)) is restricted to the set of preplace instances of t(b), denoted by •t(b) with •t(b) := {p(c) ∈ P I(P )|f (p(c), t(b)) 6= 0}. For sake of simplicity, such features as read arcs and scheduled transitions are not explicitly mentioned in the definition above. For the semantics of SP N C refer to [HLG+09].
Colored Petri nets, such as QP N C and SP N C , allow to build more compact and parametric representations of biological systems by, e.g., folding similar subnets which are then distinguished by colors. Therefore, it is possible to concisely represent complex systems that would have required a huge low-level Petri net. This provides an effective way to model and simulate very complex biological systems which would have been difficult with other modeling approaches. 3
Snoopy is a generic and adaptive tool for modeling and animating/simulating hierarchical graph-based formalisms. Snoopy runs on Windows, Linux, and Mac operating systems. It is available free of charge for non-commercial use, and can be obtained from our website [Sno10]. However QP N C and SP N C are still prototypes and thus not included in the official release so far.
Snoopy provides the following functionalities for QP N C and SP N C : – Rich data types for color set definition, consisting of dot, integer, string, Boolean, enumeration, index, product and union. The user can use these data types to define distinguishable tokens. – Colored Petri net models as drawn as usual, and automatic syntax checking of declarations and expressions. – Automatic animation, and single-step animation by manually choosing a binding. Thus, the user can run animation automatically or control the animation manually. – Simulation is done on an automatically unfolded Petri net, and simulation results for colored or uncolored places/transitions are given together or separately. This functionality only applies to SP N C . – Several simulation algorithms to simulate SP N C , including the Gillespie stochastic simulation algorithm (SSA) [Gil77]. – QP N C and SP N C are exported to different net formalisms, and thus can be analyzed by different tools such as CHARLIE [Fra09] and IDD-CSL [SH09].
In addition, there are some functionalities and features that are especially helpful for modeling biological systems, which are described as follows. – Concise specification of initial markings. In a biological model, there are often large quantities of species to be modeled. So the initial markings may be set in many different ways.
• Specifying the color and its corresponding tokens as usual. • Specifying a set of colors with the same number of tokens. • Using a predicate to choose a set of colors and then specifying the number of tokens. • Using the all() function to specify a specific number of tokens for all colors. – Specifying a rate function for each instance of a colored transition. For a transition, we may define different rate functions for different transition binding instances, and we use predicates to reach this goal. – Supporting several extended arc types, such as inhibitor arc, read arc (often also called test arcs), equal arc, reset arc, and modifier arc, which are popular add-ons enhancing modeling comfort [HRR+08]. – Supporting extended transitions. Snoopy supports stochastic transitions with freestyle rate functions and rate functions of some predefined patterns as well as several deterministically timed transition types: immediate firing, deterministic firing delay, and scheduled firing (see [HLG+09] for details).
All these functionalities and features for QP N C and SP N C facilitate the modeling and simulation of biological systems. As a result, we not only can obtain a more compact and readable model for a complex biological system, but also do not lose simulation or analysis capabilities compared with low-level Petri nets. 4
In this section, we will demonstrate how to construct a colored Petri net model using Snoopy. We first show how to construct basic colored Petri net components, and then present two examples to illustrate QP N C and SP N C , respectively. 4.1
Constructing basic colored Petri net components The key step in the design of a colored Petri net is to construct basic colored Petri net units, through which we can obtain the whole colored Petri net model step by step. This process is also called folding. In the following we will introduce some folding ways to construct basic colored Petri net components, which are illustrated in Fig. 2. 7 p1 t1 p1 t1 p2 t2 p2 t2 −−> −−> p t CS p t (a) (c) x
CS [x=1](x++ (+x))++ [x=2]x −−> p t (b)
CS x++ (+x) p1 t1 p2 t2 (d) Declarations: colorset CS = int with 1,2; variable x : CS ;
Fig. 2(a) shows the folding of two isolated subnets with the same structure. For this simple case, we can define a color set containing two colors. For example, we define the color set as ”CS” with two integer colors: 1 and 2 (see Fig. 2(d)). We then assign the color set ”CS” to the place. We define the arc expression as x, where x is a variable of the type ”CS”. Thus, we get a basic colored Petri net component, illustrated on the right hand of Fig. 2(a).
In Fig. 2(b), the net to be folded is extended by two extra arcs from p2 (p1) to t1 (t2), respectively. To fold it, we use the same color set, and just modify the arc expression to x + +(+x), where the ”+” in the (+x) is the successor operator, which returns the successor of x in an ordered finite color set. If x is the last color, then it returns the first color. The ”++” is the multiset addition operator.
In Fig. 2(c), the net to be folded gets one extra arc from p2 to t1. To fold it, we use the same color set, and just modify the arc expression to [x = 1](x + +(+x)) + +[x = 2]x, meaning: if x = 1, then there are two arcs connecting p with t, while if x = 2, then there is only one arc connecting p with t.
In summary, the following rules apply when folding two similar nets to a colored Petri net. If the two subnets share the same structure, we just have to define a color set and set arc expressions without predicates. If the subnets are similar, but not the same in structure, we may need to define arc expressions with predicates or guards. However, in either case, if we want to continue to add other similar nets, what we should do is usually to add new colors, and slightly change arc expressions or guards. Using these basic colored Petri net components, we can construct the whole colored Petri net model step by step.
In the next two sections, we will give two simple examples to demonstrate the application of colored Petri nets. The first example is to demonstrate QP N C , and the second one is to demonstrate SP N C . 4.2
Cooperative ligand binding We consider an example of the binding of oxygen to the four subunits of a hemoglobin heterotetramer. The hemoglobin heterotetramer in the high and low affinity state binds to none, one, two, three or four oxygen molecules. Each of the ten states is represented by a place and oxygen feeds into the transitions that sequentially connect the respective places. The qualitative Petri net model is illustrated in Fig. 3 (taken from [MWW09]).
Using the folding ways demonstrated above we obtain for Fig. 3 a QP N C model (Fig. 4), and further a more compact QP N C model (Fig. 5). From Fig. 4, we can see that the colored Petri net model reduces the size of the corresponding low-level Petri net model. Moreover, comparing Fig. 4 with Fig. 5, we can also see that we can build colored Petri net model with different level of structural details, which is especially helpful for modeling complex biological systems. After automatic unfolding, these two colored models yield exactly the same Petri net model as given in Fig. 3, i.e., the colored models and the uncolored model are equivalent. The declarations for these two QP N C models of the cooperative ligand binding are given in Table 1.
From these two colored nets, we can also see that the folding operation does reduce the size of the net description for the prize of more complicated inscriptions. The graphic complexity is reduced, but the annotations of nodes and edges creates a new challenge. This is not unexpected since a more concise write-up must rely on more complex components. Therefore, it is necessary to build a colored Petri net model at a suitable level of structural details. Hb(O2)4Lo
Hb(O2)4Hi Hb(O2)3Lo
Hb(O2)3Hi Fig. 4. QP N C model for the cooperative binding of oxygen to hemoglobin, given as a low-level Petri net in Fig. 3. For declarations of color sets and variables, see Table 1. 4 Dot O2 [y=L]dot [y=H]dot t1 [x<>4] t2
[x<>4] [y=L]1‘(x+1,y)++ [y=H]1‘(x,y) [y=H]1‘(x+1,y)++ [y=L]1‘(x,y)
1‘(0,L) [y=L]1‘(x,y) [y=L]1‘(x,H) t4 In this section, we will demonstrate the SP N C using an example of a synthetic circuit - the repressilator, which is an engineered synthetic system encoded on a plasmid, and designed to exhibit oscillations [EL00]. The repressilator system is a regulatory cycle of three genes, for example, denoted by g a, g b and g c, where each gene represses its successor, namely, g a inhibits g b, g b inhibites g c, and g c inhibites g a. This negative regulation is realized by the repressors, p a, p b and p c, generated by the genes g a, g b and g c respectively [LB07]. gene_a gene_b gene_c generate proteine_a unblock
generate blocked_a
proteine_b block_a block_b block_c block_b block_c block_a
As our purpose is to demonstrate the SP N C , we only consider a relatively simple model of the repressilator, which was built as a stochastic π-machine in [BCP08]. Based on that model, we build a stochastic Petri net model (Fig. 6), and further a SP N C model for the repressilator (shown on the left hand of Fig. 7). This colored model when unfolded yields the same uncolored Petri net model in Fig. 6.
Table 2 gives the declarations for this SP N C model. There are three colors, a, b, and c to distinguish three similar components in Fig. 6. The predecessor operator ”-” in the arc expression −x returns the predecessor of x in an ordered finite color set. If x is the first color, then it returns the last color.
As described above, the SP N C will be automatically unfolded to a stochastic Petri net, and can be simulated with different simulation algorithms. On the right hand of Fig. 7 a snapshot of a simulation run result is given. The rate functions are given in Table 3 (coming from [PC07]). The SP N C model exhibits the same behavior compared with that in [PC07]. generate
Gene proteine 1‘all() x x x
Gene gene
3 x block −x
−x degrade x x x x unblock Gene blocked aeuV l
Stochastic Result: repressilatorex.colstochpn
Time
From Fig. 7, we can see that the SP N C model reduces the size of the original stochastic Petri net model to one third. More importantly, when other similar subnets have to be added, the model structure does not need to be modified and what has to be done is only to add extra colors.
For example, we consider the generalized repressilator with an arbitrary number n of genes in the loop that is presented in [MHE+06]. To build its SP N C model, we just need to modify the color set as n colors, and do not need to modify anything else. For example, Fig. 8 gives the conceptual graph of the generalized repressilator with n = 9 (on the left hand), and one simulation plot (on the right hand), whose rate functions are the same as in Table 3. Please note, the SP N C model for the generalized repressilator is the same as the one for the three-gene repressilator, and the only difference is that we define the color set as n colors rather than 3 colors. This demonstrates a big advantage of color Petri nets, that is, to increase the colors means to increase the size of the net. 0.1 ∗ gene 1.0 ∗ proteine 0.0001 ∗ blocked 0.001 ∗ proteine Transition Rate function generate block unblock degrade e u l a V
Stochastic Result: repressilatorex.colstochpn
Time Heiner et al. modeled metabolic pathways with high-level Petri nets using the software packages Design/CPN [Des01]. Colors discriminate metabolites, and thus they got a number of valuable insights by combining symbolic analysis and simulation for colored metabolic steady state system models [HKV01]. Genrich et al. discussed the steps to establish and tune high-level net models, and Petri Nets & Concurrency { 83 13 modeled metabolic pathways of the glycolysis and citric acid cycle with colored Petri nets using also Design/CPN. By assigning enzymatic reaction rates to the transitions, they implemented the simulation and quantitative study of networks of metabolic processes [GKV01]. Bahi-Jaber et al. investigated the application of colored stochastic Petri nets to epidemic models using a very simple model [BP03]. Although this study had no tool support, it really demonstrated the advantages of colored stochastic Petri nets. Runge described a systematic semi-automatic procedure, exploiting the place/transition net’s T-invariants to construct an equivalent bounded and live coloured net. As case study, an extended glycolysis was used [Run04]. However, he only considered modeling and qualitative analysis of biological model based on CPN tools [JKW07]. Lee et al. built a colored Petri net model for the signal transduction system stimulated by epidermal growth factor (EGF) based on CPN tools, in which they use the conservation and kinetic equations to quantitatively examine the dynamic behavior of the EGF signaling pathway [LYL+06]. Tubner et al. used the UML class diagram to understand the static structure of molecules involved in the TLR4 pathway, and then modeled and simulated the TLR4 pathway to get the behavior of the system with colored Petri nets based on CPN tools [TMK+06]. In their model, they did not consider any time information.
In summary, the existing studies usually resort to Design/CPN or its successor CPN tools to realize the modeling and analysis of biological systems. But CPN tools are not designed for modeling and analyzing biological systems. So it is not suitable in many aspects, like rate function definition and simulative analysis by stochastic simulation algorithms.
In contrast, in Snoopy we provide specific functionalities and features to support editing, simulating, and analyzing of biological models based on colored Petri nets, as shown in Section 3. 6
In this paper we have described our on-going work of a colored Petri net-based framework to model, simulate, and analyze complex biological systems. This framework consists of three parts: QP N C , SP N C , and CP N C , and only the first two parts have been described in this paper. Their definitions are given, and functionalities and features implemented in Snoopy are described, followed by two examples to demonstrate their application. The colored Petri nets allow a more concise representation of biological systems, making it possible and convenient to construct and analyze large-scale biological models.
We are working on improvements of these two paradigms: QP N C and SP N C . In the next step, we will focus on the development of analysis tools for SP N C , and we will include the CP N C in our work. We are also developing a method to automatically create colored Petri nets from non-coloured Petri nets (automatic folding). This development will provide much stronger support to construct and analyze large-scale biological models. Besides, we are working on a case study with a size of the underlying uncolored model of about 110,000 places and 135,000 transitions.
This work has been supported by the Modeling of Pain Switch (MOPS) program of Federal Ministry of Education and Research (Funding Number: 0315449H). We would like to thank Wolfgang Marwan, Christian Rohr, and Martin Schwarick for their assistance in model construction and software development. We also would like to thank the anonymous referees for many constructive comments.