Discrete Solution of Differential Equations by P Metabolic Algorithm

Discrete Solution of Differential Equations by P Metabolic Algorithm Federico Fontana, Vincenzo Manca University of Verona Department of Computer Science strada Le Grazie, 15 37134 Verona, Italy {federico.fontana,vincenzo.manca}@univr.it Summary. The relationships existing between MP graphs, metabolic P systems, and ODE systems are investigated. Formal results show that every MP system, once derived by its MP graph, results in an ODE system whose solution equals, in the limit, the solution obtained by a non-cooperative MP system that is ODE equivalent to the original one. The freedom of choice of the ODE equivalent from the original MP system resembles the same freedom which is left in the choice and optimization of a numerical scheme while computing the solution of an ODE system. 1 Introduction MP systems [10] reconsider P systems [12] by including a deterministic procedure for their computation. This procedure, called metabolic algorithm [4], aims at capturing the salient chemical mechanisms that are responsible of the dynamics of a wide class of biomolecular processes [1]. For the sake of their comprehension, MP systems can be well represented by MP graphs [11]. MP graphs, in fact, yield an immediate depiction of the structural aspects of a biodynamic model which is similar, meanwhile not under-determined, to that offered by other graphical representation such as signal transduction networks, metabolic pathways and so on [9]. MP systems have shown effective for modeling the dynamics of several biochemical processes [5, 3, 2]. Despite this, some concern arises when comparing, for a given process, the quantitative conclusions that are drawn with MP systems with the results coming out by the numerical simulation, made using known methods [7], of more traditional differential equation-based models [8]. In this paper we analyze the relationships existing between MP and ordinary differential equation (ODE) systems. Originally started in a study of predator-prey models [6], the analysis is here proposed in a more systematic formal arrangement. Application examples are under development. 32 F. Fontana, V. Manca 2 Differential Equation Systems of Biochemical Reaction Mechanisms A general autonomous system of differential equations in the functions x1(t), . . . , xN(t) can be put in the following form [8]. x0 1=g1(x1, . . . , xN), . . . (1) x0 N=gN(x1, . . . , xN), where x0 1, . . . , x0 Nare time derivatives of x1, . . . , xNand g1, . . . , gNare timeindependent nonlinear functions. Biochemical reaction mechanisms are usually described by systems having a structure as in (1), in which g1, . . . , gNare polynomials in the variables x1, . . . , xN. For instance, such a structure is adopted in Stoichiometric Network Analysis (SNA) [13], where the system has the form x0 i= r X j=1 νijkj N Y i=1 xkij i= r X j=1 νijνj, i = 1, . . . , N, (2) and x1, . . . , xNare to be read as concentrations of the elements participating to a complex reaction. The differential equations systems we deal with in this paper in general can have the form (1). Though, in most application cases we will encounter differential equations as those described by (2). 3 Metabolic P Graphs Various graphic formalizations of coupled chemical reactions and biochemical processes exist in the literature [13]. By our side, we work with metabolic P (MP) graphs [11]. These networks allow for much flexibility in the definition of a metabolic process, furthermore they put the accent on the role of biochemical elements in the reaction, that is, either to be consumed by the chemical transformation or to act as promoters/enzymes without being consumed. We give, here, a compact definition of an MP graph, and refer the reader to the cited references for a more comprehensive treatment. Definition 1 (MP graph). An MP graph is a graph made of •source nodes, denoted as white-filled triangles; •element nodes denoted as white-filled circles and labeled by element names; •reaction nodes denoted as black-filled circles and labeled by reaction names; •regulation nodes denoted as black-filled squares and labeled by functions of element variables (every variable is associated to an element); Solution of Differential Equations by P Metabolic Algorithm 33 (a) (c) (d)(b) (e) Fig. 1. MP graph connections. •sink nodes denoted as white-filled triangles; •branches connecting source, element, reaction, and sink nodes, according to the representation given in Figure 1 where we distinguish solid and dashed line connections with or without orientation. MP graphs are designed to have a direct association with the components that form a reaction. More precisely, we associate •every source node to a gate; •every element node to a reactant; •every reaction node to a reaction; •every regulation node to a reaction rate; •every sink node to an outgoing gate. 3.1 From MP graphs to metabolic P systems An MP graph translates into a metabolic P (MP) system made of one membrane as soon as an initial state is given. The peculiarity of MP systems is that their dynamics is governed by the metabolic algorithm [4]. We address them in short, while referring the reader to [11] for a thorough definition. Definition 2 (MP system). An MP system is a construct (T, Q, R, F, q0), where: •T={Xi|i= 1, . . . , N}is the set of symbols; •Qis the set of possible states; every state is a function q:T→Rfrom symbols to real numbers R, where for every X∈T,q(X)is the amount of substance of type X; •R={ri|i= 1, . . . , L}is the set of rules, i.e., pairs of strings made over T; •F={fi|i= 1, . . . , L}is the set of reaction maps, where fi:Q→R; •q0, the initial state, is an element in Q. From this definition it emerges that we import reacting elements, amounts, reactions, and reaction rates into an MP system directly. Then, the MP system computes the network dynamics according to the metabolic algorithm and updates its state Qat every transition. In the following we will see that the state has a direct correspondence with the concentrations xi, i = 1, . . . , N, appearing in the ODE (1). The translation from MP graphs to MP systems is made using the following procedure: 34 F. Fontana, V. Manca Procedure 3.1 (From MP graphs to MP rules) Visit all reaction nodes of the MP graph. For every reaction node rk,k= 1, . . . , L, we do the following: •Define the rule rk:Xk,1· · · Xk,n →Xk,n+1 · · · Xk,n+l,(3) where Xk,1, . . . , Xk,n ∈Trefer to element nodes incoming to the reaction node rkand Xk,n+1, . . . , Xk,n+l∈Trefer to element nodes outgoing from the reaction node rk. In particular, if only a source node exists for the reaction node, then we simply have () or λin place of those symbols, Should only an outgoing branch exist for the same reaction node, leading to a sink node, then the right part of the rule will be () or λ. •Define the reaction map fkby importing the label fkfrom the corresponding regulation node. In this way we have assigned to our MP system a rule set that, along with the corresponding reaction maps, given an initial state allows to compute the evolution of a MP system according to the metabolic algorithm. 3.2 From MP to ODE systems Let [11]: •αrbe the left part of the rule r; •βrbe the right part of the rule r; •hr(X) be the number of occurrences of Xin αr; •gr(X) be the number of occurrences of Xin βr; •Sub(r) be the set containing the symbols appearing in the left part of the rule r, i.e., the substrate of r; •RSub(X) = {r∈R|X∈Sub(r)}; •Rβ(X) = {r∈R|Xappears in βr}; •P(r) = QX∈Sub(r)q(X)hr(X). A way to translate MP into ODE systems is given by the following Algorithm 3.1 (MP-ODE) Consider an MP system containing Nsymbols and Lreactions. Consider an ODE system made of Nequations. For every symbol X∈Tdefine the ODE equation (x0is the derivative with respect to the time variable): x0=X r∈Rβ(X) gr(X)frP(r)−X r∈RSub(X) hr(X)frP(r).(4) Solution of Differential Equations by P Metabolic Algorithm 35 Note that hr(X) and gr(X) are equal to zero when Xdoes not appear in the left and right part of r, respectively. Hence, (4) can be rewritten in the following more compact form: x0=X r∈R {gr(X)−hr(X)}frP(r).(5) Furthermore, note that a symbol Xappearing both in the left and the right part of the rule r, with hr(X) = gr(X), translates into a null component of equation (5). In fact, by (3) we get gr(X)−hr(X) = 0 for the component of x0indexed by rin the summation in (5). If this happens for all rules, then we have x0= 0 (e.g., Xis neither created nor consumed). 4 Non-cooperative MP Systems Definition 3 (Non-cooperative MP system). A non-cooperative MP system is an MP system whose rules are non-cooperative, e.g., αr∈Tfor every r. It is immediate to see that a non-cooperative MP system is associated with an MP graph in which no more than one branch comes to every reaction node. Non-cooperative MP systems provided with transparent rules [4] have a remarkable characteristics when the reaction maps associated to such rules are all equal. Let us add, in an MP system containing Nsymbols, the following rules and corresponding reaction maps, all of them being equal to the constant φ. ρ1:X1→X1, φ1=φ, . . .. . . ρN:XN→XN, φN=φ. (6) Theorem 1. The computation of a non-cooperative MP system provided with transparent rules that are all equal to the value φconverges, as φ→ ∞, to the solution provided by the ODE system obtained by using MP-ODE. Proof. Let us compute every reaction weight Wr(X), r∈R,X∈Sub(r) [4]. Since, by non-cooperation, Sub(r) = X, the reaction weights depend on only one symbol. For this reason we denote them simply as Wr: Wr=fr φ+X ρ∈RSub(Sub(r)) fρ =fr φ+γr , r ∈R, (7) 36 F. Fontana, V. Manca where we have introduced the term γrfor compactness of the notation. In this way, for every X∈Tthe variation of q(X) at every system transition is equal to [11]: ∆q(X) = X r∈Rβ(X) gr(X)WrP(r)−X r∈RSub(X) hr(X)WrP(r) (8) =X r∈Rβ(X) gr(X)fr φ+γr q(Sub(r)) −X r∈RSub(X) fr φ+γr q(X), where we have used (7) and the fact that if Sub(r) contains one symbol, then P(r) = q(Sub(r)) and hr(Sub(r)) = 1. By noticing that for every r∈Rwe have Wr=fr φ+γr =1 φ fr 1 + γr/φ,(9) from (8) we can immediately compute the limit lim φ→∞ φ∆q(X) = X r∈Rβ(X) gr(X)frq(Sub(r)) −X r∈RSub(X) frq(X).(10) Now, suppose that our MP system performs a transition every Tseconds. By denoting with q(X)[t] the state at time twe can express the variation of q(X) between two subsequent transitions as ∆q(X) = q(X)[t+T]−q(X)[t].(11) Suppose also that the finer the granularity of the observation, the shorter the transition time. This relation between time and granularity implies that the portion of objects participating to a reaction becomes smaller as much as the time between subsequent transitions becomes shorter. Granularity can be managed in the MP system by tuning the value of φ. More precisely: lim T→0 q(X)[t+T]−q(X)[t] T= lim φ→∞ q(X)[t+ 1/φ]−q(X)[t] 1/φ .(12) By (11), then (12) is equal to lim T→0 ∆q(X) T= lim φ→∞ ∆q(X) 1/φ = lim φ→∞ φ∆q(X),(13) which in turn equals (10). Furthermore, (12) is also equal to lim T→0 q(X)[t+T]−q(X)[t] T=q0(X)[t] = x0(t),(14) in which the last equation comes out by recalling that the time derivative of q(X) at time tis the instantaneous variation of xat the same time in the ODE. Hence, the right member of (14) equals the right member of (10) and this completes the proof. In fact, (10) corresponds to (4) in the case of non-cooperation. Solution of Differential Equations by P Metabolic Algorithm 37 Equation (10) can be written in a more compact form that equals (5), again in the non-cooperative case: x0=X r∈R {gr(X)−hr(X)}frq(Sub(r)) .(15) 5 Non-cooperative ODE Equivalent MP Systems Definition 4. Two MP systems are ODE equivalent if their translation made using MP-ODE results in the same ODE system. Proposition 5.1 Given an MP system Π= (T, Q, R, F, q0)there exists a noncooperative MP system Π0= (T, Q, R0, F0, q0)which is ODE equivalent to Π. Proof. Define R0and F0by using the following procedure. For every r∈R: 1. choose ˜ X∈Sub(r), and set r0:˜ X→βr, fr0=fr P(r) q(˜ X); (16) 2. if other occurrences of ˜ Xexist, define r0 ˜ X:˜ X→(), fr0 ˜ X={hr(˜ X)−1}fr P(r) q(˜ X); (17) 3. for every other symbol X∈Sub(r)− { ˜ X}, define r00 X:X→(), fr00 X=hr(X)fr P(r) q(X); (18) 4. add such rules in R0; add the corresponding reaction maps in F0. Let us pose x0=x0 ++x0 −. By MP-ODE: x0 ++x0 −=X ρ∈R0 β(X) gρ(X)fρq(Sub(ρ)) −X ρ∈R0 Sub(X) fρq(X).(19) Consider the additive part x0 +(first summation) in (19). By (16) it is fr0q(Sub(r0)) = fr P(r) q(X)q(X) = frP(r).(20) By noting that βr∈r0if and only if βr∈r, then by direct substitution of the right part of (20) into the additive part in (19) we have 38 F. Fontana, V. Manca x0 +=X ρ∈R0 β(X) gρ(X)fρq(Sub(ρ)) = X r∈Rβ(X) gr(X)frP(r).(21) Now, consider the subtractive part x0 −(second summation) in (19). By the construction of R0, every r∈RSub(X) translates either into two rules r0, r0 X∈ R0 Sub(X), or into one rule r00 X∈R0 Sub(X). In the former case r0and r0 Xresult, by MP-ODE, in a component in x0 −equal to the sum of the corresponding reaction maps times the amount of Xin the system. So, by (16) and (17), this component is equal to: fr0q(X) + fr0 Xq(X) = {1 + hr(X)−1}fr P(r) q(X)q(X) = hr(X)frP(r).(22) In the latter case r00 Xresults, by (18), in a component in x0 −equal to fr00 Xq(X) = hr(X)fr P(r) q(X)q(X) = hr(X)frP(r).(23) The one-to-one correspondence between rand either r0and r0 X, or r00 X, implies that the subtractive part in (19) is equal to x0 −=X ρ∈R0 Sub(X) fρq(X) = X r∈RSub(X) hr(X)frP(r).(24) By summing (21) and (24) and comparing to (4) we obtain the ODE equivalence between Πand Π0. The non-cooperative MP system obtained using Proposition 5.1 is not uniquely determined. Although, on the one hand, by Theorem 1 we know that all possible non-cooperative MP systems obtained using Proposition 5.1 converge to the same ODE, on the other hand the way they converge depends on the choice made while deriving the non-cooperative MP system. 6 Conclusions A theoretical procedure has been devised which finds, for an MP system, the ODE that is solved. Since this result holds in the limit with an infinite precision of the computation along time, MP systems can be seen as a family of numerical schemes for the solution of a specific class of ODE systems which, in particular, account for virtually all the differential equation models of biochemical processes. The indetermination on the ODE equivalent MP systems one must derive to solve a specific differential problem resembles the same indetermination existing for most numerical schemes in which, during the solution of an ODE system, aspects such as the choice and parameterization of the scheme are driven by the problem itself, and often left to the experience of the experimenter. Solution of Differential Equations by P Metabolic Algorithm 39 References 1. P. Atkins, J. de Paula: Physical Chemistry. Oxford University Press, Oxford, UK, 7th edition, 2002. 2. L. Bianco, F. Fontana, G. Franco, V. Manca: P systems for biological dynamics. In Applications of Membrane Computing (G. Ciobanu, M. J. P´erez-Jim´enez, Gh. P˘aun, eds.), Springer, 2006, 81–126. 3. L. Bianco, F. Fontana, V. Manca: Reaction-driven membrane systems. In Advances in Natural Computation, First International Conference, ICNC 2005, Changsha, China, August 27-29, 2005, Proceedings, Part II (L. Wang, K. Chen, Y.-S. Ong, eds.), LNCS 3611, Springer, 2005, 1155–1158. 4. L. Bianco, F. Fontana, V. Manca: P systems with reaction maps. International Journal of Foundations of Computer Science, 17, 1 (2006), 27–48. 5. F. Fontana, L. Bianco, V. Manca: P systems and the modeling of biochemical oscillations. In 6th Workshop on Membrane Computing (WMC6) (R. Freund, Gh. P˘aun, G. Rozenberg, A. Salomaa, eds.), LNCS 3850, Springer, 2005, 199–208. 6. F. Fontana, V. Manca: Predator-prey dynamics in P systems ruled by metabolic algorithm. BioSystems, submitted. 7. A. Iserles: Numerical Analysis of Differential Equations. Cambridge University Press, Cambridge, MA, 1996. 8. D.S. Jones, B.D. Sleeman: Differential equations and mathematical biology. Chapman & Hall/CRC, London, UK, 2003. 9. H. Kitano: Computational systems biology. Nature, 420 (November 2002), 206–210. 10. V. Manca: Topics and problems in metabolic P systems. In the present volume. 11. V. Manca, L. Bianco: Biological networks in metabolic P systems. BioSystems, submitted. 12. Gh. P˘aun: Membrane Computing. An Introduction. Springer, Berlin, 2002. 13. J. Ross, M.O. Vlad: New approaches to complex chemical reaction mechanisms. In Design Principles for Immune Sistem & Other Distributed Autonomous Systems (L.A. Segel, I.R. Cohen, eds.), Oxford University Press, 2001, 261–278.