Disc e e Solu ion o Di e en ial Equa ions by P
Me abolic Algo i hm
Fede ico Fon ana, Vincenzo Manca
Uni e si y o Ve ona
Depa men o Compu e Science
s ada Le G azie, 15
37134 Ve ona, I aly
{ ede ico. on ana, incenzo.manca}@uni .i
Summa y. The ela ionships exis ing be ween MP g aphs, me abolic P sys ems, and
ODE sys ems a e in es iga ed. Fo mal esul s show ha e e y MP sys em, once de i ed
by i s MP g aph, esul s in an ODE sys em whose solu ion equals, in he limi , he solu ion
ob ained by a non-coope a i e MP sys em ha is ODE equi alen o he o iginal one.
The eedom o choice o he ODE equi alen om he o iginal MP sys em esembles he
same eedom which is le in he choice and op imiza ion o a nume ical scheme while
compu ing he solu ion o an ODE sys em.
1 In oduc ion
MP sys ems [10] econside P sys ems [12] by including a de e minis ic p ocedu e
o hei compu a ion. This p ocedu e, called me abolic algo i hm [4], aims a
cap u ing he salien chemical mechanisms ha a e esponsible o he dynamics
o a wide class o biomolecula p ocesses [1].
Fo he sake o hei comp ehension, MP sys ems can be well ep esen ed by
MP g aphs [11]. MP g aphs, in ac , yield an immedia e depic ion o he s uc u al
aspec s o a biodynamic model which is simila , meanwhile no unde -de e mined,
o ha o e ed by o he g aphical ep esen a ion such as signal ansduc ion ne -
wo ks, me abolic pa hways and so on [9].
MP sys ems ha e shown e ec i e o modeling he dynamics o se e al bio-
chemical p ocesses [5, 3, 2]. Despi e his, some conce n a ises when compa ing, o
a gi en p ocess, he quan i a i e conclusions ha a e d awn wi h MP sys ems wi h
he esul s coming ou by he nume ical simula ion, made using known me hods
[7], o mo e adi ional di e en ial equa ion-based models [8].
In his pape we analyze he ela ionships exis ing be ween MP and o dina y
di e en ial equa ion (ODE) sys ems. O iginally s a ed in a s udy o p eda o -p ey
models [6], he analysis is he e p oposed in a mo e sys ema ic o mal a angemen .
Applica ion examples a e unde de elopmen .
32 F. Fon ana, V. Manca
2 Di e en ial Equa ion Sys ems o Biochemical Reac ion
Mechanisms
A gene al au onomous sys em o di e en ial equa ions in he unc ions x1( ), . . . ,
xN( ) can be pu in he ollowing o m [8].
x0
1=g1(x1, . . . , xN),
. . . (1)
x0
N=gN(x1, . . . , xN),
whe e x0
1, . . . , x0
Na e ime de i a i es o x1, . . . , xNand g1, . . . , gNa e ime-
independen nonlinea unc ions.
Biochemical eac ion mechanisms a e usually desc ibed by sys ems ha ing a
s uc u e as in (1), in which g1, . . . , gNa e polynomials in he a iables x1, . . . , xN.
Fo ins ance, such a s uc u e is adop ed in S oichiome ic Ne wo k Analysis (SNA)
[13], whe e he sys em has he o m
x0
i=
X
j=1
νijkj
N
Y
i=1
xkij
i=
X
j=1
νijνj, i = 1, . . . , N, (2)
and x1, . . . , xNa e o be ead as concen a ions o he elemen s pa icipa ing o a
complex eac ion.
The di e en ial equa ions sys ems we deal wi h in his pape in gene al can
ha e he o m (1). Though, in mos applica ion cases we will encoun e di e en ial
equa ions as hose desc ibed by (2).
3 Me abolic P G aphs
Va ious g aphic o maliza ions o coupled chemical eac ions and biochemical
p ocesses exis in he li e a u e [13]. By ou side, we wo k wi h me abolic P
(MP) g aphs [11]. These ne wo ks allow o much lexibili y in he de ini ion o
a me abolic p ocess, u he mo e hey pu he accen on he ole o biochemical
elemen s in he eac ion, ha is, ei he o be consumed by he chemical ans o -
ma ion o o ac as p omo e s/enzymes wi hou being consumed.
We gi e, he e, a compac de ini ion o an MP g aph, and e e he eade o
he ci ed e e ences o a mo e comp ehensi e ea men .
De ini ion 1 (MP g aph). An MP g aph is a g aph made o
•sou ce nodes, deno ed as whi e- illed iangles;
•elemen nodes deno ed as whi e- illed ci cles and labeled by elemen names;
• eac ion nodes deno ed as black- illed ci cles and labeled by eac ion names;
• egula ion nodes deno ed as black- illed squa es and labeled by unc ions o ele-
men a iables (e e y a iable is associa ed o an elemen );
Solu ion o Di e en ial Equa ions by P Me abolic Algo i hm 33
(a) (c) (d)(b) (e)
Fig. 1. MP g aph connec ions.
•sink nodes deno ed as whi e- illed iangles;
•b anches connec ing sou ce, elemen , eac ion, and sink nodes, acco ding o he
ep esen a ion gi en in Figu e 1 whe e we dis inguish solid and dashed line
connec ions wi h o wi hou o ien a ion.
MP g aphs a e designed o ha e a di ec associa ion wi h he componen s ha
o m a eac ion. Mo e p ecisely, we associa e
•e e y sou ce node o a ga e;
•e e y elemen node o a eac an ;
•e e y eac ion node o a eac ion;
•e e y egula ion node o a eac ion a e;
•e e y sink node o an ou going ga e.
3.1 F om MP g aphs o me abolic P sys ems
An MP g aph ansla es in o a me abolic P (MP) sys em made o one memb ane
as soon as an ini ial s a e is gi en. The peculia i y o MP sys ems is ha hei
dynamics is go e ned by he me abolic algo i hm [4]. We add ess hem in sho ,
while e e ing he eade o [11] o a ho ough de ini ion.
De ini ion 2 (MP sys em). An MP sys em is a cons uc (T, Q, R, F, q0), whe e:
•T={Xi|i= 1, . . . , N}is he se o symbols;
•Qis he se o possible s a es; e e y s a e is a unc ion q:T→R om symbols
o eal numbe s R, whe e o e e y X∈T,q(X)is he amoun o subs ance o
ype X;
•R={ i|i= 1, . . . , L}is he se o ules, i.e., pai s o s ings made o e T;
•F={ i|i= 1, . . . , L}is he se o eac ion maps, whe e i:Q→R;
•q0, he ini ial s a e, is an elemen in Q.
F om his de ini ion i eme ges ha we impo eac ing elemen s, amoun s, e-
ac ions, and eac ion a es in o an MP sys em di ec ly. Then, he MP sys em
compu es he ne wo k dynamics acco ding o he me abolic algo i hm and up-
da es i s s a e Qa e e y ansi ion. In he ollowing we will see ha he s a e has
a di ec co espondence wi h he concen a ions xi, i = 1, . . . , N, appea ing in he
ODE (1).
The ansla ion om MP g aphs o MP sys ems is made using he ollowing
p ocedu e:
34 F. Fon ana, V. Manca
P ocedu e 3.1 (F om MP g aphs o MP ules) Visi all eac ion nodes o
he MP g aph. Fo e e y eac ion node k,k= 1, . . . , L, we do he ollowing:
•De ine he ule
k:Xk,1· · · Xk,n →Xk,n+1 · · · Xk,n+l,(3)
whe e Xk,1, . . . , Xk,n ∈T e e o elemen nodes incoming o he eac ion node
kand Xk,n+1, . . . , Xk,n+l∈T e e o elemen nodes ou going om he eac-
ion node k.
In pa icula , i only a sou ce node exis s o he eac ion node, hen we simply
ha e () o λin place o hose symbols,
Should only an ou going b anch exis o he same eac ion node, leading o a
sink node, hen he igh pa o he ule will be () o λ.
•De ine he eac ion map kby impo ing he label k om he co esponding
egula ion node.
In his way we ha e assigned o ou MP sys em a ule se ha , along wi h he
co esponding eac ion maps, gi en an ini ial s a e allows o compu e he e olu ion
o a MP sys em acco ding o he me abolic algo i hm.
3.2 F om MP o ODE sys ems
Le [11]:
•α be he le pa o he ule ;
•β be he igh pa o he ule ;
•h (X) be he numbe o occu ences o Xin α ;
•g (X) be he numbe o occu ences o Xin β ;
•Sub( ) be he se con aining he symbols appea ing in he le pa o he ule
, i.e., he subs a e o ;
•RSub(X) = { ∈R|X∈Sub( )};
•Rβ(X) = { ∈R|Xappea s in β };
•P( ) = QX∈Sub( )q(X)h (X).
A way o ansla e MP in o ODE sys ems is gi en by he ollowing
Algo i hm 3.1 (MP-ODE) Conside an MP sys em con aining Nsymbols and
L eac ions. Conside an ODE sys em made o Nequa ions. Fo e e y symbol
X∈Tde ine he ODE equa ion (x0is he de i a i e wi h espec o he ime
a iable):
x0=X
∈Rβ(X)
g (X) P( )−X
∈RSub(X)
h (X) P( ).(4)
Solu ion o Di e en ial Equa ions by P Me abolic Algo i hm 35
No e ha h (X) and g (X) a e equal o ze o when Xdoes no appea in he
le and igh pa o , espec i ely. Hence, (4) can be ew i en in he ollowing
mo e compac o m:
x0=X
∈R
{g (X)−h (X)} P( ).(5)
Fu he mo e, no e ha a symbol Xappea ing bo h in he le and he igh pa
o he ule , wi h h (X) = g (X), ansla es in o a null componen o equa ion
(5). In ac , by (3) we ge g (X)−h (X) = 0 o he componen o x0indexed by
in he summa ion in (5). I his happens o all ules, hen we ha e x0= 0 (e.g.,
Xis nei he c ea ed no consumed).
4 Non-coope a i e MP Sys ems
De ini ion 3 (Non-coope a i e MP sys em). A non-coope a i e MP sys em
is an MP sys em whose ules a e non-coope a i e, e.g., α ∈T o e e y .
I is immedia e o see ha a non-coope a i e MP sys em is associa ed wi h an MP
g aph in which no mo e han one b anch comes o e e y eac ion node.
Non-coope a i e MP sys ems p o ided wi h anspa en ules [4] ha e a e-
ma kable cha ac e is ics when he eac ion maps associa ed o such ules a e all
equal.
Le us add, in an MP sys em con aining Nsymbols, he ollowing ules and
co esponding eac ion maps, all o hem being equal o he cons an φ.
ρ1:X1→X1, φ1=φ,
.
.
..
.
.
ρN:XN→XN, φN=φ.
(6)
Theo em 1. The compu a ion o a non-coope a i e MP sys em p o ided wi h
anspa en ules ha a e all equal o he alue φcon e ges, as φ→ ∞, o he
solu ion p o ided by he ODE sys em ob ained by using MP-ODE.
P oo . Le us compu e e e y eac ion weigh W (X), ∈R,X∈Sub( ) [4]. Since,
by non-coope a ion, Sub( ) = X, he eac ion weigh s depend on only one symbol.
Fo his eason we deno e hem simply as W :
W =
φ+X
ρ∈RSub(Sub( ))
ρ
=
φ+γ
, ∈R, (7)

36 F. Fon ana, V. Manca
whe e we ha e in oduced he e m γ o compac ness o he no a ion. In his
way, o e e y X∈T he a ia ion o q(X) a e e y sys em ansi ion is equal o
[11]:
∆q(X) = X
∈Rβ(X)
g (X)W P( )−X
∈RSub(X)
h (X)W P( ) (8)
=X
∈Rβ(X)
g (X)
φ+γ
q(Sub( )) −X
∈RSub(X)
φ+γ
q(X),
whe e we ha e used (7) and he ac ha i Sub( ) con ains one symbol, hen
P( ) = q(Sub( )) and h (Sub( )) = 1.
By no icing ha o e e y ∈Rwe ha e
W =
φ+γ
=1
φ
1 + γ /φ,(9)
om (8) we can immedia ely compu e he limi
lim
φ→∞ φ∆q(X) = X
∈Rβ(X)
g (X) q(Sub( )) −X
∈RSub(X)
q(X).(10)
Now, suppose ha ou MP sys em pe o ms a ansi ion e e y Tseconds. By
deno ing wi h q(X)[ ] he s a e a ime we can exp ess he a ia ion o q(X)
be ween wo subsequen ansi ions as
∆q(X) = q(X)[ +T]−q(X)[ ].(11)
Suppose also ha he ine he g anula i y o he obse a ion, he sho e he
ansi ion ime. This ela ion be ween ime and g anula i y implies ha he po ion
o objec s pa icipa ing o a eac ion becomes smalle as much as he ime be ween
subsequen ansi ions becomes sho e .
G anula i y can be managed in he MP sys em by uning he alue o φ. Mo e
p ecisely:
lim
T→0
q(X)[ +T]−q(X)[ ]
T= lim
φ→∞
q(X)[ + 1/φ]−q(X)[ ]
1/φ .(12)
By (11), hen (12) is equal o
lim
T→0
∆q(X)
T= lim
φ→∞
∆q(X)
1/φ = lim
φ→∞ φ∆q(X),(13)
which in u n equals (10). Fu he mo e, (12) is also equal o
lim
T→0
q(X)[ +T]−q(X)[ ]
T=q0(X)[ ] = x0( ),(14)
in which he las equa ion comes ou by ecalling ha he ime de i a i e o q(X)
a ime is he ins an aneous a ia ion o xa he same ime in he ODE. Hence,
he igh membe o (14) equals he igh membe o (10) and his comple es he
p oo . In ac , (10) co esponds o (4) in he case o non-coope a ion.
Solu ion o Di e en ial Equa ions by P Me abolic Algo i hm 37
Equa ion (10) can be w i en in a mo e compac o m ha equals (5), again
in he non-coope a i e case:
x0=X
∈R
{g (X)−h (X)} q(Sub( )) .(15)
5 Non-coope a i e ODE Equi alen MP Sys ems
De ini ion 4. Two MP sys ems a e ODE equi alen i hei ansla ion made us-
ing MP-ODE esul s in he same ODE sys em.
P oposi ion 5.1 Gi en an MP sys em Π= (T, Q, R, F, q0) he e exis s a non-
coope a i e MP sys em Π0= (T, Q, R0, F0, q0)which is ODE equi alen o Π.
P oo . De ine R0and F0by using he ollowing p ocedu e.
Fo e e y ∈R:
1. choose ˜
X∈Sub( ), and se
0:˜
X→β , 0=
P( )
q(˜
X); (16)
2. i o he occu ences o ˜
Xexis , de ine
0
˜
X:˜
X→(), 0
˜
X={h (˜
X)−1}
P( )
q(˜
X); (17)
3. o e e y o he symbol X∈Sub( )− { ˜
X}, de ine
00
X:X→(), 00
X=h (X)
P( )
q(X); (18)
4. add such ules in R0; add he co esponding eac ion maps in F0.
Le us pose x0=x0
++x0
−. By MP-ODE:
x0
++x0
−=X
ρ∈R0
β(X)
gρ(X) ρq(Sub(ρ)) −X
ρ∈R0
Sub(X)
ρq(X).(19)
Conside he addi i e pa x0
+( i s summa ion) in (19). By (16) i is
0q(Sub( 0)) =
P( )
q(X)q(X) = P( ).(20)
By no ing ha β ∈ 0i and only i β ∈ , hen by di ec subs i u ion o he
igh pa o (20) in o he addi i e pa in (19) we ha e
38 F. Fon ana, V. Manca
x0
+=X
ρ∈R0
β(X)
gρ(X) ρq(Sub(ρ)) = X
∈Rβ(X)
g (X) P( ).(21)
Now, conside he sub ac i e pa x0
−(second summa ion) in (19). By he
cons uc ion o R0, e e y ∈RSub(X) ansla es ei he in o wo ules 0, 0
X∈
R0
Sub(X), o in o one ule 00
X∈R0
Sub(X). In he o me case 0and 0
X esul , by
MP-ODE, in a componen in x0
−equal o he sum o he co esponding eac ion
maps imes he amoun o Xin he sys em. So, by (16) and (17), his componen
is equal o:
0q(X) + 0
Xq(X) = {1 + h (X)−1}
P( )
q(X)q(X) = h (X) P( ).(22)
In he la e case 00
X esul s, by (18), in a componen in x0
−equal o
00
Xq(X) = h (X)
P( )
q(X)q(X) = h (X) P( ).(23)
The one- o-one co espondence be ween and ei he 0and 0
X, o 00
X, implies
ha he sub ac i e pa in (19) is equal o
x0
−=X
ρ∈R0
Sub(X)
ρq(X) = X
∈RSub(X)
h (X) P( ).(24)
By summing (21) and (24) and compa ing o (4) we ob ain he ODE equi alence
be ween Πand Π0.
The non-coope a i e MP sys em ob ained using P oposi ion 5.1 is no uniquely
de e mined. Al hough, on he one hand, by Theo em 1 we know ha all possible
non-coope a i e MP sys ems ob ained using P oposi ion 5.1 con e ge o he same
ODE, on he o he hand he way hey con e ge depends on he choice made while
de i ing he non-coope a i e MP sys em.
6 Conclusions
A heo e ical p ocedu e has been de ised which inds, o an MP sys em, he ODE
ha is sol ed. Since his esul holds in he limi wi h an in ini e p ecision o he
compu a ion along ime, MP sys ems can be seen as a amily o nume ical schemes
o he solu ion o a speci ic class o ODE sys ems which, in pa icula , accoun
o i ually all he di e en ial equa ion models o biochemical p ocesses.
The inde e mina ion on he ODE equi alen MP sys ems one mus de i e o
sol e a speci ic di e en ial p oblem esembles he same inde e mina ion exis ing o
mos nume ical schemes in which, du ing he solu ion o an ODE sys em, aspec s
such as he choice and pa ame e iza ion o he scheme a e d i en by he p oblem
i sel , and o en le o he expe ience o he expe imen e .
Solu ion o Di e en ial Equa ions by P Me abolic Algo i hm 39
Re e ences
1. P. A kins, J. de Paula: Physical Chemis y. Ox o d Uni e si y P ess, Ox o d, UK,
7 h edi ion, 2002.
2. L. Bianco, F. Fon ana, G. F anco, V. Manca: P sys ems o biological dynamics. In
Applica ions o Memb ane Compu ing (G. Ciobanu, M. J. P´e ez-Jim´enez, Gh. P˘aun,
eds.), Sp inge , 2006, 81–126.
3. L. Bianco, F. Fon ana, V. Manca: Reac ion-d i en memb ane sys ems. In Ad ances in
Na u al Compu a ion, Fi s In e na ional Con e ence, ICNC 2005, Changsha, China,
Augus 27-29, 2005, P oceedings, Pa II (L. Wang, K. Chen, Y.-S. Ong, eds.), LNCS
3611, Sp inge , 2005, 1155–1158.
4. L. Bianco, F. Fon ana, V. Manca: P sys ems wi h eac ion maps. In e na ional Jou -
nal o Founda ions o Compu e Science, 17, 1 (2006), 27–48.
5. F. Fon ana, L. Bianco, V. Manca: P sys ems and he modeling o biochemical oscil-
la ions. In 6 h Wo kshop on Memb ane Compu ing (WMC6) (R. F eund, Gh. P˘aun,
G. Rozenbe g, A. Salomaa, eds.), LNCS 3850, Sp inge , 2005, 199–208.
6. F. Fon ana, V. Manca: P eda o -p ey dynamics in P sys ems uled by me abolic
algo i hm. BioSys ems, submi ed.
7. A. Ise les: Nume ical Analysis o Di e en ial Equa ions. Camb idge Uni e si y P ess,
Camb idge, MA, 1996.
8. D.S. Jones, B.D. Sleeman: Di e en ial equa ions and ma hema ical biology. Chapman
& Hall/CRC, London, UK, 2003.
9. H. Ki ano: Compu a ional sys ems biology. Na u e, 420 (No embe 2002), 206–210.
10. V. Manca: Topics and p oblems in me abolic P sys ems. In he p esen olume.
11. V. Manca, L. Bianco: Biological ne wo ks in me abolic P sys ems. BioSys ems, sub-
mi ed.
12. Gh. P˘aun: Memb ane Compu ing. An In oduc ion. Sp inge , Be lin, 2002.
13. J. Ross, M.O. Vlad: New app oaches o complex chemical eac ion mechanisms.
In Design P inciples o Immune Sis em & O he Dis ibu ed Au onomous Sys ems
(L.A. Segel, I.R. Cohen, eds.), Ox o d Uni e si y P ess, 2001, 261–278.