Bounded Model Checking using SMT Sol e s o RKIP Inhibi ed ERK Pa hway Model
1. P elimina ies
Sa is iabili y (SAT) sol e s a e so wa e p og ams ha de e mine i a gi en Boolean o mula has
a sa is ying inpu combina ion. I a o mula has a sa is ying inpu , when he o mula is e alua ed
wi h his inpu combina ion, i esul s in ue. When his is he case, he o mula is conside ed “sa .”
SAT sol e s ha e a a ie y o applica ions, including in sys ems biology and in compu a ional
models. Howe e , adi ional SAT o mulas a e limi ed o con aining only Boolean alues,
es ic ing wha can be added o hem. Sa is iabili y modulo heo ies (SMT) sol e s build on he
ounda ion c ea ed by SAT sol e s o allow addi ional da a ypes o be used.
In he simula ion comple ed wi h SAT sol e s, he midpoin o each in e al was used o ep esen
i s chemical’s concen a ion in eac ion calcula ions, wi h he eac ion esul alue being used o
assign a new in e al o each chemical. Because SAT o mulas a e limi ed o Boolean alues, his
was one app oach o allow he ep esen a ion o hese in e als. Howe e , wi h an SMT sol e ,
hese in e als can be di ec ly in eg a ed in o he logic o he simula ion. Speci ically, one ope a ion
ha can be used in SMT o mulas bu no SAT o mulas is he inequali y, allowing he in e als o
be mo e easily exp essed as pa o he o mula.
The addi ion o inequali ies, he in e als used in he E k pa hway simula ions can be di ec ly
exp essed in SMT o mulas. In his example, he i s ou eac ions o he E k pa hway we e
modelled in Py hon using Mic oso Z3, a ype o SMT sol e . To begin, Real a iables we e
c ea ed o ep esen he ini ial and inal alues o each chemical, in each eac ion. Nex , a unc ion
de ines he s eps o build he model based on he k bound se o Bounded Model Checking (BMC),
which is de ined by he use . Each k s ep ep esen s a single eac ion. Fo each eac ion, cons ain s
a e added o he SMT o mula o es ic each chemical o i s in e als. The eac ion logic is also
de ined, wi h he inpu chemical o minimum concen a ion mul iplied by he eac ion’s a e being
used o de e mine he p oduc o he eac ion. The p oduc is e enly emo ed om he inpu
chemicals and added o he ou pu chemicals acco ding o his logic, and cons ain s ep esen ing
his a e added o he SMT o mula. The cons ain s o each eac ion a e added o he SMT o mula
in acco dance wi h he BMC k bound.
When he que ies a e execu ed, he SMT sol e checks o coun e examples disp o ing he
p ope y, up o he BMC k bound. I a coun e example is ound, he sol e e u ns “sa ” along wi h
he model showing he coun e example. I a coun e example is no iden i ied wi hin he bound, he
sol e e u ns “unsa ,” signi ying ha he p ope y holds o he gi en bound.
2. Bounded Model Checking Que ies
He e is a sample o que ies ha we e e alua ed using bounded model checking.
a) a = S500E700
Fo all ou k alues, his que y e u ns “unsa ” when execu ed. This means ha he p ope y
always holds o all po en ial pa hs in he simula ion. The ini ial in e al o a is S500E700
in his model, and he alue o a mus no hi 500 o below a any s a e o sa is y his que y.
The sys em did no ind any coun e examples whe e a exi s he S500E700 in e al.
b) a = S500E700
∧
kip = ZERO
Fo his que y, he sol e e u ns “sa ” o all ou k alues. In i s ini ial s a e, kip is wi hin
he in e al S8E16, bu because i only educes concen a ion in eac ion 1, his means ha ,
o a leas one s a e, he eac ion was no enough o b ing i s concen a ion o ZERO.
Because he sol e e u ns “sa ,” he e exis s a leas one s a e ha does no sa is y his que y.
c) a = S500E700
∧
kip = S2E4
This que y also e u ns “sa ” o all ou k s eps. This example also s a s wi h kip in i s
maximum s a e o S8E16, and like Que y 2, kip mus lose enough o i s concen a ion o be
assigned he new in e al o S2E4. This does no occu in a leas one po en ial s a e,
esul ing in “sa ” o all ou s eps. Fo his que y, he e also exis s a leas one s a e such ha
he p ope y is no sa is ied.
