=Paper=
{{Paper
|id=Vol-1373/paper6
|storemode=property
|title=Dependent shrink for Petri net models of signaling pathways
|pdfUrl=https://ceur-ws.org/Vol-1373/paper6.pdf
|volume=Vol-1373
|dblpUrl=https://dblp.org/rec/conf/apn/MizutaGM15
}}
==Dependent shrink for Petri net models of signaling pathways==
Dependent shrink for Petri net models of signaling pathways Atsushi Mizuta1 , Qi-Wei Ge2 , and Hiroshi Matsuno1 1 Graduate School of Science and Engineering, Yamaguchi University Yamaguchi 753-8512, Japan 2 Faculty of Education, Yamaguchi University Yamaguchi 753-8512, Japan {v014vc,gqw}@yamaguchi-u.ac.jp, matsuno@sci.yamaguchi-u.ac.jp Abstract. Retention-free Petri net has been used in modeling of sig- naling pathways, which is a timed Petri net such that total input and total output token flows 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 find shrinkable transitions and to shrink them into a single transition. This algorithm eventually provides a set of transitions whose firing fre- quencies 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, de- pendent shrink 1 Introduction Li et al. [1] have proposed a qualitative modeling method by paying attention to the molecular interactions and mechanisms using discrete Petri nets. Further- more, 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 firing frequency conditional expressions based on its structure information. At the same time, they introduced “retention-free” Petri net for defining smooth signal flows in signaling pathways. In Petri net model of signaling pathway, firing 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 firing 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 definitions of dependent subnet. Dependent shrink is a concept to express a dependent subnet which is shrunk into a single transition. M Heiner, AK Wagler (Eds.): BioPPN 2015, a satellite event of PETRI NETS 2015, CEUR Workshop Proceedings Vol. 1373, 2015. 86 A Mizuta, QW Ge and H Matsuno Place Transition Directed arc Fig. 1. Elements of Petri nets The advantage of this concept is that all the firing frequencies of transitions in the subnet can be computationally obtained from the firing 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 first 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 Definitions and Properties In this section, we briefly give the necessary definitions and properties of Petri nets. For detailed definitions the reader is suggested to refer to [5]. Definition 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 {t1 , t2 , · · · , t|T | } – P : a set of places {p1 , p2 , · · · , p|P | } – 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) Definition 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 = {tsour 1 , · · · , tsour a }(a ≥ 1). 3. A transition without output arc is called sink transition and the set of sink transitions is denoted by Tsink = {tsink 1 , · · · , tsink b }(b ≥ 1). 4. A transition t is called Ps − synchronous transition if there exists a set of input places Ps that for any p ∈ Ps , p• = {t} holds, and is defined by Tsync = {tsync 1 , · · · , tsync c }(c ≥ 1). Proc. BioPPN 2015, a satellite event of PETRI NETS 2015 Dependent shrink for signaling pathways 87 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 ). Fig. 2 shows source(i) and sink(ii) transition and Fig. 3 shows synchronous transitions. Note that, we use discrete Petri nets in this paper. Fig. 2. Source and sink transition p1 p3 t1 p2 p4 Fig. 3. Synchronous transition 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 Proc. BioPPN 2015, a satellite event of PETRI NETS 2015 88 A Mizuta, QW Ge and H Matsuno tokens can be regarded as a representation of the amount of chemical sub- stances. Current assignment of tokens to the places is expressed in form of a vector, namely a marking as defined above. 2. Transitions denote active elements including chemical reactions, events, ac- tions, conversions, and catalyzed reactions. A transition fires by taking off tokens from its individual input places and creating new tokens that are dis- tributed 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 rela- tions between corresponding static elements and active elements. Arc weights α and β (defined in Definition 1) describe the quantities of substances re- quired 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 excep- tionally modeled in Definition 3 below. 5. An inhibition function in biological pathways is modeled by an inhibitor arc. Definition 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 firable state, if the transition ts is fired. 2. Let tp and td denote a token provider of pi and a sink output transition of pi , respectively, where the firing of tp represents an enzyme activation reaction and the firing of td implies a small natural degradation in a biological pathway. pi holds up token(s) after firing transition tp and the weights of the arcs satisfy α(pi , td ) α(pi , ts ). Fig. 4. An enzyme place in Petri net model Proc. BioPPN 2015, a satellite event of PETRI NETS 2015 Dependent shrink for signaling pathways 89 [Firing rule of Petri net] A transition t is firable 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 firable. Definition 4. A timed Petri net T P N is defined by T P N = (P N, D), where D is a set of positive number expressing firing delay times (or delay time for short) of transitions in T . [Firing rule of timed Petri nets] (i) If the firing of a transition ti is decided, tokens required for the firing are reserved. We call these tokens as reserved tokens. (ii) When the delay time di of ti passed, ti fires 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, firing times of a transition ti per unit time is called f iring f requency fi . fi represents the maximum firing frequency of ti . The delay time di of ti is given by the reciprocal of fi . Definition 5. [2] With the firing of transition tI , token amounts flowed into place p per unit time is called “input token-flow”, and is denoted by T FtI ,p . On the other hand, with the firing of transition tO , token amounts flowed out of place p per unit time is called “output token-flow”, and is denoted by T Fp,tO . T FtI ,p and T Fp,tO (shown in Fig. 5) are defined by following equations, respectively: T FtI ,p = fI · βI (1) T Fp,tO = fO · αO , (2) where fI and fO are firing frequencies of tI and tO , respectively; βI and αO are the weights of e = (tI , p) and e = (p, tO ), respectively. Based on this definition, the following equation hold. • Proposition 1. [2] Let p be a place P • Pn {tIi |tIi ∈ p} and with input transitions m out put transitions {tOj |tOj ∈p }. Then i=1 T FtIi ,p and j=1 T Fp,tOj are the total input token-flow and the total output token-flow for place p, respectively. Furthermore, when firing frequency f take the maximum firing rate f , input token-flow T FtI ,p and output token flow T Fp,tO become the maximum, F TtI ,p and F Tp,tO , respectively. These maximum token-flows satisfy following equations. m X m X T FtIi ,p ≤ F TtIi ,p (3) i=1 i=1 n X Xn T Fp,tOj ≤ F Tp,tOj (4) j=1 j=1 Proc. BioPPN 2015, a satellite event of PETRI NETS 2015 90 A Mizuta, QW Ge and H Matsuno Fig. 5. Token flows The following requirement is trivial. Proposition 2. [2] In a timed Petri net, a total output token-flow is not more than a total input token-flow for each place p: m X n X T FtIi ,p ≥ T Fp,tOj , (5) i=1 j=1 Definition 6. [2] A timed Petri net TPN is called Retention-free Petri net (RFPN) (satisfying Proposition1) if a total input token-flow and a total output token-flow are equivalent at any place of TPN; that is, T FtIi ,p = T Fp,tOj (6) Definition 7. [3] Each unreserved token deposited to input place p is assigned to be reserved by the transition tOj that satisfies the following expression: n cj X ck { / − sj } = αj αk k=1 n ci X ck min{ / − si | i = 1, 2, · · · , n} (7) αi αk k=1 Proc. BioPPN 2015, a satellite event of PETRI NETS 2015 Dependent shrink for signaling pathways 91 When the number of reserved tokens of tOj is not less than a required token number for the firing, the firing of tOj is decided. After the delay time dOj of tOj passed, tOj fires 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 firing probability of transition tOj , which represents the proportion of the firing frequency of each transition to the total firing frequencies of the transitions in conflict. 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 c reserved so far, and thus b αjj c represents the number of firing times of transition tOj from the beginning. Expression (7) is designed to reserve the token to such a transition Pn ti that c has the largest difference between calculated firing probability αjj / k=1 αckk and given firing probability sj among all the transitions in conflict. Definition 8. [2] If output transitions of p are in conflict, the maximum firing frequency of tOj must satisfy the following expression: m s ·α Pn j j X · T FtIi ,p = fOj · αj , (8) k=1 sk · αk i=1 where αj is the weight of e = (p, tOj ) and sj is the firing probability of tOj . Pnsj ·αj represents the ratio of the token amount deposited to tOj to the total k=1 sk ·αk token-flow from p to each output transition p• . 3 Shrink of Dependent Subnet The equation (8) shows a relationship of firing frequency about input and output transitions, which are dependent each other. Based on this dependency, a set of transitions can be obtained, by which firing 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. Definition 9. [4] If firing frequency of a transition t is determined by the firing 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α . Proc. BioPPN 2015, a satellite event of PETRI NETS 2015 92 A Mizuta, QW Ge and H Matsuno Definition 10. [4] For a given set A of transitions, A-dependent transition is a set of transitions whose firing frequencies are determined by the firing frequen- cies 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 sub- stitute the set of α-dependent transition T to a single transition t. Definition 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 . Fig. 6. Markgraph Proposition 4. As shown in Fig. 7, if place p has multiple output transitions TO = {tO.1 , tO.2 , · · · , tO.k }, TO can be shrink into a single transition t0 , where Proc. BioPPN 2015, a satellite event of PETRI NETS 2015 Dependent shrink for signaling pathways 93 the weights of input arc α0 and new output arc β 0 are defined by the following formulas; sO.1 · α1 + sO.2 · α2 + · · · + sO.k · αk α0 = (9) sO.1 β10 = sO.1 · β1 β20 = sO.2 · β2 .. . 0 βk = sO.k · βk (10) Fig. 7. Conflict structure Proposition 5. As shown is Fig. 8, if place p has multiple output transitions of two types, with self-loop Tl = {tl.1 , tl.2 , · · · , tl.k } and without self-loop TO = {tO.1 , tO.2 , · · · , tO.k },Tl and TO can be shrunk into a single transition, where input arc α0 and new output arc β 0 are defined 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 (11) β10 = sO.1 · β1 β20 = sO.2 · β2 .. . 0 βk2 = sl.k2 · βk2 (12) Note that, in equation (11) α0 > 0 should be held. Proc. BioPPN 2015, a satellite event of PETRI NETS 2015 94 A Mizuta, QW Ge and H Matsuno Fig. 8. Self-loop structure 4 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 briefly 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 conflict of it. step2: Shrink of conflict 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 flag, by which dependent shrink pattern is determined. Proc. BioPPN 2015, a satellite event of PETRI NETS 2015 Dependent shrink for signaling pathways 95 Fig. 9. IL-3 phenomenon model 4.2 Dependent shrink algorithm The following algorithm is used to shrink dependent subnets into a single tran- sition in order to find transitions with interdependent firing frequency. Algorithm: Dependent shrink Input: P N0 = (T0 , P0 , E0 ) Output: Shrunk Petri net N = (T, P, E) Proc. BioPPN 2015, a satellite event of PETRI NETS 2015 96 A Mizuta, QW Ge and H Matsuno Main(P N0 ) 1◦ T ← T0 , P ← P0 , E ← E0 , N ← (T, P, E) 2◦ X ← P , Q ← φ 3◦ while (X 6= φ) Pull an element x from X(X ← X − {x}) Enqueue(Q, x) Shrink1(N, x) 4◦ Shrink2(N, Q) Shrink1(N, x) 1◦ if (|• x ∩ x• | ≥ 1) then f ←1 Arcweight(N, x, f ) 2◦ if (|x• | ≥ 2) then f ←2 Arcweight(N, x, f ) Shrink2(N, Q) 1◦ while (|Q| ≥ 1) x ← Dequeue(Q) if (|• x ∩ x• | ≥ 1) then f ←1 Enqueue(Q, x) else if (|• x| = |x• | = 1) then f ←3 else if (|• x| ≥ 2) then f ←4 Enqueue(Q, x) if (f 6= 4) then Arcweight(N, x, f ) Arcweight(N, x, f ) 1◦ if (f = 1) then ∀t0 ∈ • x ∩ x• α(x, t0 ) = α(x, t0 ) − β(t0 , x) if (α(x, t0 ) < 0) then β(t0 , x) = |α(x, t0 )| E ← E − {(x, t0 )} else if (α(x, t0 ) > 0) then E ← E − {(t0 , x)} else if (α(x, t0 ) = 0) then E ← E − {(t0 , x), (x, t0 )} ◦ 2 else if (f = 2) then T ← T ∪ {t0 } E ← E ∪ {(x, t0 )} ∪ {(u, t0 )|u ∈ • z, z ∈ x• } ∪ {(t0 , v)|v ∈ z • , z ∈ x• } Choose z 0 ∈ x• . ∀z ∈ x• − {t0 } α(x, t0 ) = α(x, t0 ) + s(z) ∗ α(x, z) Proc. BioPPN 2015, a satellite event of PETRI NETS 2015 Dependent shrink for signaling pathways 97 ∀v ∈ z • , z ∈ x• β(t0 , v) = s(z) ∗ β(z, v) ∀u ∈ • z, z ∈ x• α(u, t0 ) = s(z) ∗ α(u, z)/s(z 0 ) α(x, t ) = α(x, t0 )/s(z 0 ) 0 T ← T − {z|z ∈ x• − {t0 }} ◦ 3 else if (f = 3) then T ← T ∪ {t0 } Let zi , zo be {zi } = • x, {zo } = x• (due to |• x| = |x• | = 1). E ← E ∪ {(u, t0 )|u ∈ • zi ∪ • zo } ∪ {(t0 , v)|v ∈ zi• ∪ zo• } ∀u ∈ • zi α(u, t0 ) = α(u, zi ) ∀u ∈ zi • β(t0 , u) = β(zi , u) ∀v ∈ • zo α(v, t0 ) = β(zi , x) ∗ α(v, zo )/α(x, zo ) ∀v ∈ zo • β(t0 , v) = β(zi , x) ∗ β(zo , v)/α(x, zo ) T ← T − {zi |zi ∈ • x} − {zo |zo ∈ x• } P ← X − {x} When the above algorithm is applied, a dependent subnet, say S, is trans- formed 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 flowed out of p per unit time are the same before and after dependent shrink. Similarly, the tokens flowed into an output place per unit time are the same. 4.3 An Example for Signaling Pathway Petri Net Model 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 firing frequency of all transition in Fig.10 (a) are denpendent each other. In the intermediate shrunk net (see Fig. 10 (b)), by assuming the firing frequency of the input transition fI be 1, the weights of input and output arcs be 12 and 1, respectively, then the firing frequency of output transition fO is 12 . In this way, we can calculate all of the firing frequency of transitions in the IL-3 Petri net model from one firing frequency in this model. 5 Conclusion In this paper, after giving basic definitions of Petri net and modeling method, we introduced dependent shrink method and its properties to find dependent subnet. Further, we designed an algorithm of dependent shrink and applied it to IL-3 signaling pathway Petri net model as an example. Proc. BioPPN 2015, a satellite event of PETRI NETS 2015 98 A Mizuta, QW Ge and H Matsuno Fig. 10. Shrunk IL-3 Petri net model By applying the dependent shrink algorithm, IL-3 Petri net model is con- verted to a simple model, with which we could find the transitions which are dependent each other. This algorithm allows us to obtain firing frequencies of all transitions in a dependent subnet only by measuring reactions corresponding to the transitions by biological experiments in the simple model. Proc. BioPPN 2015, a satellite event of PETRI NETS 2015 Dependent shrink for signaling pathways 99 In this paper, we only discussed discrete Petri nets. By extending transitions to include firing 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 Fauré at Yamaguchi University for his support in proofreading the manuscript. This work was partially supported by Grant-in- Aid for Scientific 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 mod- eling and analysis of signaling pathways based on Petri net”, Journal of Bioinfor- matics 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 finding 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 off 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. Coffer, L. Koenderman, “Regulation of proliferation, differenti- ation 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) Proc. BioPPN 2015, a satellite event of PETRI NETS 2015