Dependent shrink for Petri net models of signaling pathways

Abstract

Retention-free Petri net has been used in modeling of signaling pathways, which is a timed Petri net such that total input and total output token ows are equivalent at any place. Previously we have investigated the dependency of transitions in retention-free Petri net. In this paper, we introduce a modeling method for signaling pathway by using Petri net, giving properties of retention-freeness by considering arc weight. Based on the obtained properties, we propose an algorithm to nd shrinkable transitions and to shrink them into a single transition. This algorithm eventually provides a set of transitions whose ring frequencies are dependent. As an example, we apply the algorithm to IL-3 signaling pathway Petri net model to show the usefulness of our proposed algorithm.

Keywords

• signaling pathway
• Petri net
• retention-free Petri net
• dependent shrink

-

Li et al. [ 1 ] have proposed a qualitative modeling method by paying attention to the molecular interactions and mechanisms using discrete Petri nets. Furthermore, Miwa et al. [ 2 ] modeled it with timed Petri net, which is an extended Petri net on the concept of time, proposing a method to have ring frequency conditional expressions based on its structure information. At the same time, they introduced \retention-free" Petri net for de ning smooth signal ows in signaling pathways.

In Petri net model of signaling pathway, ring frequency of each transition should be measured by biological experiments. However, such biological data of reactions are very few. As a method to cope with this problem, Murakami et al. [ 3 ] proposed an approach to check the retention-freeness of a given Petri net based on ring frequencies of transitions of this Petri net. According to this method, Matsumoto et al. [ 4 ] formally described the concept of dependent shrink after giving formal de nitions of dependent subnet. Dependent shrink is a concept to express a dependent subnet which is shrunk into a single transition.

Place

Transition

Directed arc

The advantage of this concept is that all the ring frequencies of transitions in the subnet can be computationally obtained from the ring frequency of that shrunk transition. Namely, by only getting the reaction speed of a reaction that corresponds to that shrunk transition, all other reaction speeds in dependent subnet can be estimated by the proposed procedure in this paper.

In this paper we propose an algorithm to do equivalent transformation for retention-free Petri nets. Concretely, we rst classify dependent shrink pattern according to the patterns of input and output transitions of a place and then perform the dependent shrink operations of the patterns. Finally, we reconstruct the Petri net based on the dependent shrink result. 2

Basic De nitions and Properties

In this section, we brie y give the necessary de nitions and properties of Petri nets. For detailed de nitions the reader is suggested to refer to [ 5 ]. De nition 1. A Petri net denoted as P N = (T; P; E; ; ) that is a bipartite graph, where E = E+ [ E and { T : a set of transitions ft1; t2; ; tjT jg { P : a set of places fp1; p2; ; pjP jg { E+: a set of arcs from transitions to places e = (t; p) { E : a set of arcs from places to transitions e = (p; t) { e: is the weight of arc e = (p; t) { e: is the weight of arc e = (t; p) De nition 2. Let P N be a Petri net 1. t (t ) is the set of input (or output) places of t, and p (p ) is the set of input (or output) transitions of p. 2. A transition without input arc is called source transition and the set of source transitions are denoted by Tsour = fts1our; ; tsaourg(a 1): 3. A transition without output arc is called sink transition and the set of sink transitions is denoted by Tsink = fts1ink; ; tbsinkg(b 1): 4. A transition t is called Ps synchronous transition if there exists a set of input places Ps that for any p 2 Ps, p = ftg holds, and is de ned by Tsync = fts1ync; ; tcsyncg(c 1). 5. A place can hold a positive integer that represents a number of tokens. An assignment of tokens in places expressed in form of a vector M is called a marking, which varies during the execution of a Petri net. Given with an initial marking M0, the Petri net is called Marked Petri net and denoted by M P N = (P N; Mo). 2.1

Modeling rules

Li et al. [ 1 ] gave the following modeling rules for signaling pathways based on Petri net representation. 1. Places denote static elements including chemical compounds, conditions, states, substances, and cellular organelles participating in the biological pathways. Tokens indicate the presence of these elements. The number of tokens can be regarded as a representation of the amount of chemical substances. Current assignment of tokens to the places is expressed in form of a vector, namely a marking as de ned above. 2. Transitions denote active elements including chemical reactions, events, actions, conversions, and catalyzed reactions. A transition res by taking o tokens from its individual input places and creating new tokens that are distributed to its output places if its input places has at least as many tokens in it as arc weight from the place to the transition. 3. Directed arcs connecting the places and the transitions represent the relations between corresponding static elements and active elements. Arc weights and (de ned in De nition 1) describe the quantities of substances required before and after a reaction, respectively. Especially in case of modeling a chemical reaction, arc weights represent quantities given by stoichiometric equations of the reaction itself. Note that, weight of an arc is omitted if the weight is 1. 4. Since an enzyme itself plays a role of catalyzer in biological pathways and there occurs no consumption in biochemical reactions, an enzyme is exceptionally modeled in De nition 3 below. 5. An inhibition function in biological pathways is modeled by an inhibitor arc. De nition 3. [ 1 ] An enzyme in a biological pathway is modeled by a place, called enzyme place, as shown in Fig. 4. 1. Enzyme place pi has a self-loop with the same weight connected from and to transition ts. Once an enzyme place is occupied by a token, the token will return to the place again to keep the rable state, if the transition ts is red. 2. Let tp and td denote a token provider of pi and a sink output transition of pi, respectively, where the ring of tp represents an enzyme activation reaction and the ring of td implies a small natural degradation in a biological pathway. pi holds up token(s) after ring transition tp and the weights of the arcs satisfy (pi; td) (pi; ts). [Firing rule of Petri net] A transition t is rable if each input place pI of P N has at least e tokens, where e denotes the weight of an arc e = (pI ; t). Firing of a transition t removes e tokens from each input place pI of t and deposit e(e = (t; pO)) tokens to each output place pO of t, where e denotes the weight of an arc e = (t; pO). A source transition is always rable.

De nition 4. A timed Petri net T P N is de ned by T P N = (P N; D), where D is a set of positive number expressing ring delay times (or delay time for short) of transitions in T . [Firing rule of timed Petri nets] (i) If the ring of a transition ti is decided, tokens required for the ring are reserved. We call these tokens as reserved tokens. (ii) When the delay time di of ti passed, ti res to remove the reserved tokens from the input places of ti and put non-reserved tokens into the output places of ti. In a timed Petri net, ring times of a transition ti per unit time is called f iring f requency fi. fi represents the maximum ring frequency of ti. The delay time di of ti is given by the reciprocal of fi.

De nition 5. [ 2 ] With the ring of transition tI , token amounts owed into place p per unit time is called \input token- ow", and is denoted by T FtI ;p. On the other hand, with the ring of transition tO, token amounts owed out of place p per unit time is called \output token- ow", and is denoted by T Fp;tO . T FtI ;p and T Fp;tO (shown in Fig. 5) are de ned by following equations, respectively: T FtI ;p = fI T Fp;tO = fO

I O; where fI and fO are ring frequencies of tI and tO, respectively; I and the weights of e = (tI ; p) and e = (p; tO), respectively.

Based on this de nition, the following equation hold.

Proposition 1. [ 2 ] Let p be a place with input transitions ftIi jtIi 2 pg and out put transitions ftOj jtOj 2p g. Then Pim=1 T FtIi ;p and Pjn=1 T Fp;tOj are the total input token- ow and the total output token- ow for place p, respectively. Furthermore, when ring frequency f take the maximum ring rate f , input token- ow T FtI ;p and output token ow T Fp;tO become the maximum, F TtI ;p and F Tp;tO , respectively. These maximum token- ows satisfy following equations. m X T FtIi ;p i=1 n X T Fp;tOj j=1 m X F TtIi ;p i=1 n X F Tp;tOj j=1 (1) (2) O are (3) (4) The following requirement is trivial.

Proposition 2. [ 2 ] In a timed Petri net, a total output token- ow is not more than a total input token- ow for each place p: m X T FtIi ;p i=1 n X T Fp;tOj ; j=1

T FtIi ;p = T Fp;tOj De nition 6. [ 2 ] A timed Petri net TPN is called Retention-free Petri net (RFPN) (satisfying Proposition1) if a total input token- ow and a total output token- ow are equivalent at any place of TPN; that is, De nition 7. [ 3 ] Each unreserved token deposited to input place p is assigned to be reserved by the transition tOj that satis es the following expression: (5) (6) f minf cj = Xn j

ck k=1 k ci = Xn i k=1 ck k sj g = si j i = 1; 2; ; ng (7)

When the number of reserved tokens of tOj is not less than a required token number for the ring, the ring of tOj is decided. After the delay time dOj of tOj passed, tOj res to remove the reserved tokens from the input place of tOj and deposit unreserved tokens into the output places of tOj .

In the above expression (7), sj is the ring probability of transition tOj , which represents the proportion of the ring frequency of each transition to the total ring frequencies of the transitions in con ict. A probability sj is assigned to corresponding transition tOj , which is given as a constant in advance according to the event. A variable c is an accumulated number of tokens that tOj has been cj reserved so far, and thus b j c represents the number of ring times of transition tOj from the beginning.

Expression (7) is designed to reserve the token to such a transition ti that has the largest di erence between calculated ring probability cj = Pn ck and j k=1 k given ring probability sj among all the transitions in con ict.

De nition 8. [ 2 ] If output transitions of p are in con ict, the maximum frequency of tOj must satisfy the following expression:

sj Pn k=1 sk j m

X T FtIi ;p = fOj k i=1 j ; ring (8) where j is the weight of e = (p; tOj ) and sj is the ring probability of tOj . Pkns=j1 skj k represents the ratio of the token amount deposited to tOj to the total token- ow from p to each output transition p . 3

Shrink of Dependent Subnet

The equation (8) shows a relationship of ring frequency about input and output transitions, which are dependent each other. Based on this dependency, a set of transitions can be obtained, by which ring frequencies of all transitions in a Petri net model can be calculated. Note that the transitions in the set determined in this way correspond to the reactions whose speeds need to be measured by biological experiments. 3.1

Dependent subnet

Dependent subnet, obtained as follows, is a Petri net induced from a set of transitions which are dependent on each other.

De nition 9. [ 4 ] If ring frequency of a transition t is determined by the ring frequency of transition , this transition is called -dependent transition. The subnet induced by the set of -dependent transitions and transition is called -dependent subnet, denoted by P N . De nition 10. [ 4 ] For a given set A of transitions, A-dependent transition is a set of transitions whose ring frequencies are determined by the ring frequencies of transitions in A. The subnet induced by A-dependent transition and A is called A-dependent subnet, denoted by P NA. 3.2

Dependent shrink

For a set of -dependent transition T , dependent shrink is a procedure to substitute the set of -dependent transition T to a single transition t. De nition 11. [ 4 ] If two transitions ti and tj exist are dependent each other, these two transitions can be shrunk into a single transition.

Note that the proofs of the following propositions are omitted to save the space of this paper.

Proposition 3. As shown in Fig. 6, if a place p has one input transition tI and one output transition tO, these two transitions can be shrunk into a single transition t0, where the weight of new input arc 0 = 1, and the weight of new output arc 0 = 2 12 . Proposition 4. As shown in Fig. 7, if place p has multiple output transitions TO = ftO:1; tO:2; ; tO:kg, TO can be shrink into a single transition t0, where the weights of input arc 0 and new output arc 0 are de ned by the following formulas; 0 = sO:1 1 + sO:2 2 + + sO:k

k sO:1 10 = sO:1 Proposition 5. As shown is Fig. 8, if place p has multiple output transitions of two types, with self-loop Tl = ftl:1; tl:2; ; tl:kg and without self-loop TO = ftO:1; tO:2; ; tO:kg,Tl and TO can be shrunk into a single transition, where input arc 0 and new output arc 0 are de ned by the following formulas; 0 = (sO:1

O:1 + sO:2

O:2 + + sl:k2 l:k2) (sl:1 l:1 + sl:2 l:2 + + sl:k2

l:k2) =sO:1 10 = sO:1 (9) (10) (11) (12)

Dependent Shrink Algorithm and an Example

In this section, we propose a dependent shrink algorithm based on the dependent shrink method. Furthermore, we apply this algorithm to IL-3 signaling pathway Petri net model (shown in Fig. 10), which is transformed from IL-3 phenomenon model (shown in Fig. 9) obtained from the website [ 10 ]. Note that IL-3 is a glycoprotein and is known to be involved in the immune response [6{9]. 4.1

Outline of shrink process

The shrink process of dependent subnet can be brie y described as follows: step1: Shrink of self loop structure

A place randomly selected from a Petri net is stored in a queue after the conversion of the self-loops and the structures of con ict of it. step2: Shrink of con ict structure

If a place picked up from the queue has a self-loop or a transition of one-input and one-output, this place is shrunk. step3: Changing weight of the input arc

If shrunk Petri net has a multiple input place, it re-stores to the queue, performing the above step2 again. This procedure is repeated until the queue becomes empty.

The variables used in the algorithm are as follows: { P N0 is a given signaling pathway Petri net model constituted by T0; P0; and E0. { N is a variable that stores Petri net after dependent shrink, constituted by

T; P; andE. { Q is a queue. { X is a set of place initially set as a given place set P0. { f is a ag, by which dependent shrink pattern is determined. The following algorithm is used to shrink dependent subnets into a single transition in order to nd transitions with interdependent ring frequency. Algorithm: Dependent shrink Input: P N0 = (T0; P0; E0) Output: Shrunk Petri net N = (T; P; E)

Main(P N0)

1 T T0, P P0, E E0, N 2 X P , Q 3 while (X 6= )

Pull an element x from X(X

Enqueue(Q; x)

Shrink1(N; x)

4 Shrink2(N; Q)

Shrink1(N; x)

1 if (j x \ x j 1) then f 1

Arcweight(N; x; f )

2) then

(T; P; E)

X fxg) 8v 2 z ; z 2 x

(t0; v) = s(z) (z; v) 8u 2 z; z 2 x

(u; t0) = s(z) (u; z)=s(z0) (x; t0) = (x; t0)=s(z0)

T T fzjz 2 x ft0gg 3 else if (f = 3) then

T T [ ft0g Let zi; zo be fzig = x, fzog = x (due to j xj = jx j = 1).

E E [ f(u; t0)ju 2 zi [ zog [ f(t0; v)jv 2 zi [ zo g 8u 2 zi

(u; t0) = (u; zi) T P

When the above algorithm is applied, a dependent subnet, say S, is transformed into a single transition, say tS. Obviously S and tS possess the same input and output places. As the result, for each input place, p, the tokens owed out of p per unit time are the same before and after dependent shrink. Similarly, the tokens owed into an output place per unit time are the same. Here we give an example to show an application of our proposed algorithm. The algorithm is applied to dependent shrink for IL-3 Petri net model (see Fig.10 (a)), obtained from the website [ 10 ]. As the result, the original IL-3 Petri net model shown in Fig.10 (a) is shrunk into Fig.10 (c). This means that the ring frequency of all transition in Fig.10 (a) are denpendent each other. In the intermediate shrunk net (see Fig. 10 (b)), by assuming the ring frequency of the input transition fI be 1, the weights of input and output arcs be 21 and 1, respectively, then the ring frequency of output transition fO is 12 . In this way, we can calculate all of the ring frequency of transitions in the IL-3 Petri net model from one ring frequency in this model. 5

Conclusion

In this paper, after giving basic de nitions of Petri net and modeling method, we introduced dependent shrink method and its properties to nd dependent subnet. Further, we designed an algorithm of dependent shrink and applied it to IL-3 signaling pathway Petri net model as an example.

By applying the dependent shrink algorithm, IL-3 Petri net model is converted to a simple model, with which we could nd the transitions which are dependent each other.

This algorithm allows us to obtain ring frequencies of all transitions in a dependent subnet only by measuring reactions corresponding to the transitions by biological experiments in the simple model.

In this paper, we only discussed discrete Petri nets. By extending transitions to include ring speed, it is possible to extend our method to continuous Petri nets.

As a future work, we need to improve our algorithm so that it can indicate transitions corresponding to measurable reactions by biological experiment. Also the uniqueness of our algorithm needs to be investigated.

Acknowledgement

We would like to thank Dr. Adrien Faure at Yamaguchi University for his support in proofreading the manuscript. This work was partially supported by Grant-inAid for Scienti c Research (B) (23300110) from Japan Society for the Promotion of Science.

References

1. C. Li , S. Suzuki , Q.W. Ge , M. Nakata , H. Matsuno , S. Miyano, \ Structural modeling and analysis of signaling pathways based on Petri net" , Journal of Bioinformatics and Computational Biology , Vol. 4 , No. 5 , pp. 1119 - 1140 , 2006 .

2. Y. Miwa , Y. Murakami , Q.W. Ge , C. Li , H. Matsuno , S. Miyano, \ Delay time determination for the timed Petri net model of a signaling pathway based on its structural information" , IEICE on Fundamentals of Electronics, Communications and Computer Sciences , Vol. E93 -A, No12 , pp2717 - 2729 , 2010 (in Japanese).

3. Y. Murkami , Q.W. Ge , H. Matsuno, \ Consideration on the token retention-free in timed Petri net model based on the signaling pathway characteristics" , Technical Report of IEICE , Vol. 111 , No. 453 , MSS2011 -77, pp. 29 - 34 , 2012 (in Japanese).

4. T. Matsumoto , Q.W. Ge , H. Matsuno, \ An algorithm for nding dependent subnets in a retention-free Petri net," Technical Report of IEICE, MSS2012-50 , pp. 27 - 32 , 2013 (in Japanese).

5. J.L. Peterson , Petri net theory and the modeling of systems , Prentice Hall, 1981 .

6. K. Sugamura , K. Miyazono , K. Miyazawa , N. Tanaka , Saitokain zoushokuinshi yougo raiburari (Term Library of Cytokines and Growth factor ), Yodosha , 2005 (in Japanese).

7. W. Chen , M.O. Daines , G.K. Khurana Hershey , \ Turning o signal transducer and activator of transcription (STAT): the negative regulation of STAT signaling," The Journal of allergy and clinical immunology , 114 ( 3 ), pp. 476 - 489 , quiz 490, 2004 .

8. T. Kisseleva , S. Bhattacharya , J. Braunstein , C. W. Schindler , \ Signaling through the JAK/STAT pathway," recent advances and future challenges , Gene , 285 ( 1-2 ), pp. 1 - 24 , 2002 .

9. R.P. de Groot , P.J. Co er, L. Koenderman, \ Regulation of proliferation, di erentiation and survival by the IL-3/IL-5/GM-CSF receptor family," Cellular signalling , 10 ( 9 ), pp. 619 - 628 , 1998 .

10. Petri Net Pathways, http://genome.ib.sci.yamaguchi-u.ac.jp/pnp/(accessed April 20th)