25 Pages
English

Ferdinanda Camporesi1

-

Gain access to the library to view online
Learn more

Description

Niveau: Supérieur, Doctorat, Bac+8
MFPS 2010 Combining model reductions Ferdinanda Camporesi1,4 Dipartimento di Scienze dell'Informazione Universita di Bologna Bologna, Italy & Laboratoire d'informatique de l'Ecole normale superieure (INRIA/ENS/CNRS) Paris, France Jerome Feret 1,5 Laboratoire d'informatique de l'Ecole normale superieure (INRIA/ENS/CNRS) Paris, France Heinz Koeppl2,6 Tatjana Petrov3,7 School of Computer and Communication Sciences EPFL Lausanne, Switzerland Abstract Molecular biological models usually suffer from a large combinatorial explosion. Indeed, proteins form complexes and modify each others, which leads to the formation of a huge number of distinct chemical species (i.e. non-isomorphic connected components of proteins). Thus we cannot generate explicitly the quantitative semantics of these models, and even less compute their properties. Model reduction aims at reducing this complexity by providing another grain of observation. In this paper, we propose two unifying frameworks for combining model reductions: we propose a symmetric product operator for combining model reductions for stochastic semantics and we show how to abstract further existing reduced differential systems by the means of linear projections. We apply both frameworks so as to abstract further existing reduced quantitative semantics of the models that are written in Kappa, by taking into account symmetries among binding sites in proteins. Keywords: rules-based modeling, model reduction, abstract interpretation, symmetries.

  • reduced quantitative

  • fragments-based model

  • model reductions

  • can recruit

  • ond site

  • can easily

  • depends both

  • both proteins

  • semantics


Subjects

Informations

Published by
Reads 7
Language English

MFPS 2010
Combining model reductions
1;4Ferdinanda Camporesi
Dipartimento di Scienze dell’Informazione
Universit a di Bologna
Bologna, Italy
&
Laboratoire d’informatique de l’Ecole normale superieure
(INRIA/ENS/CNRS)
Paris, France
1;5Jer^ ome Feret
Laboratoire d’informatique de l’Ecole normale superieure
(INRIA/ENS/CNRS)
Paris, France
2;6 3;7Heinz Koeppl Tatjana Petrov
School of Computer and Communication Sciences
EPFL
Lausanne, Switzerland
Abstract
Molecular biological models usually su er from a large combinatorial explosion. Indeed, proteins
form complexes and modify each others, which leads to the formation of a huge number of distinct
chemical species (i.e. non-isomorphic connected components of proteins). Thus we cannot generate
explicitly the quantitative semantics of these models, and even less compute their properties. Model
reduction aims at reducing this complexity by providing another grain of observation. In this paper,
we propose two unifying frameworks for combining model reductions: we propose a symmetric
product operator for combining model reductions for stochastic semantics and we show how to
abstract further existing reduced di erential systems by the means of linear projections. We apply
both frameworks so as to abstract further existing reduced quantitative semantics of the models
that are written in Kappa, by taking into account symmetries among binding sites in proteins.
Keywords: rules-based modeling, model reduction, abstract interpretation, symmetries.
This paper is electronically published in
Electronic Notes in Theoretical Computer Science
URL: www.elsevier.nl/locate/entcsCamporesi, Feret, Koeppl, and Petrov
1 Introduction
Signaling pathways describe the interactions between some proteins which
are involved in communication between and within cells. These pathways
usually su er from a combinatorial blow-up in the number of chemical species
(pairwise non-isomorphic connected components of proteins). Rules-based
modeling [9,1] o ers a convenient and compact solution for describing these
pathways (and other molecular biological systems as well). The combinatorial
complexity is avoided thanks to context-free rules, in which the set of all
potential contexts of application for an interaction does not need to be written
explicitly.
Yet, the combinatorial complexity raises again when one is interested in
the quantitative semantics of rules-based models. Stochastic semantics (based
on the use of CTMCs, or master equations) and di erential semantics cannot
be explicitly written, because the state space is a vector space the dimension
of which is the number of reachable species. Model reduction [2,5,10,7,11] con-
sists in reducing this dimension, by discovering a coarser grain of observation.
Sound and automatic model reduction can be achieved by the means of formal
methods. The framework in [10,7] for reducing di erential semantics is based
on the fact that rules cannot observe the correlation between speci c parts
of some chemical species. Thus these chemical species can easily be cut into
fragments. In [11] backward bisimulations [4] are used in order to ensure that
rules cannot enforce correlations between the state of some identi ed parts of
chemical species.
In this paper, we propose two generic constructions to combine model re-
ductions, one for stochastic semantics and one for di erential semantics. In
Sect. 2, we give a motivating example: we show that fragments-based model
reductions can be abstracted further by taking into account the fact that some
binding sites have exactly the same capabilities of interactions (we say that
these sites are symmetric). In Sect. 3, we propose a generic framework for
reducing stochastic semantics and combining these abstractions. This frame-
work is based on the use of backward bisimulations [4] in order to prove sta-
tistical invariants, and use these invariants to reduce the state space. We
propose a binary product for combining backward bisimulation-based model
1 The contribution of Ferdinanda Camporesi and Jer^ ome Feret was partially supported by
the AbstractCell ANR-Chair of Excellence.
2 Heinz Koeppl acknowledges the support from the Swiss National Science Foundation,
grant no. 200020-117975/1.
3 Tatjana Petrov acknowledges the support from SystemsX.ch, the Swiss Initiative in Sys-
tems Biology.
4 Email: campores@di.ens.fr
5 feret@di.ens.fr
6 Email: heinz.koeppl@epfl.ch
7 tatjana.petrov@epfl.ch
2Camporesi, Feret, Koeppl, and Petrov
reductions, so as to build the least model reduction which is at least as much
as abstract as each model reduction that is given as an argument of this oper-
ator. In Sect. 4, we use linear projections to abstract further model reductions
for di erential semantics. Interestingly, the algorithm that is used to generate
the reduced model can be adapted to deal with symmetric sites on the y.
Our two frameworks are highly reusable, because they do not require much
soundness assumptions about the relation between the symmetries that are
used to quotient further the coarse-grained variables and the reduced models
(much of proofs are made once for all in the non reduced model).
Then we apply our framework on the models written in Kappa: in Sect. 5,
we give the operational semantics of Kappa. In Sect. 6 we give the de nition of
symmetric sites in Kappa, we review the stochastic and di erential semantics,
and we use symmetric sites, so as to reduce further the dimension of the state
space of these semantics.
2 Case study
Let us start out with a simple motivating example. We consider two kinds of
agents P and X. Instances of P denote phosphate ions, whereas instances of
X denote copies of a given protein. We assume that each protein X has two
kinds of sites: m sitesx ,. . . ,x andn sitesy ,. . . ,y (m andn are two integer1 m 1 n
parameters of our model). Each site can recruit at most one phosphate ion P
and, then, dissociate from it. The state of a proteinX is denoted as a (ordered)
tuple of symbols among u;p . The symbolp stands for a phosphorylated site,
whereas the symbolu stands for an unphosphorylated site. For instance, with
m 2 andn 1, a proteinX having the sitesx andy and1 1
the site x unphosphorylated is denoted by X p;u;p .2
We assume that for each integer i between 1 and m the phosphorylation
of the sitex does not depend on the phosphorylation state of the other sites.i
The sitesx ;:::;x can all be phosphorylated at a same ratek. Nevertheless,1 m
we also assume that for each integer j between 1 and n, the phosphorylation
of the site y depends both on the index j of the site y and on the numberj j
of sites among x ;:::;x which are currently phosphorylated in the protein1 m
X: the rate of activation of the site y in a protein X which have exactly ij
phosphorylated sites among x ;:::;x is denoted by k . Last, we assume1 m j;i
that any phosphorylated site can be unphosphorylated at a same rate k .d
We give in Fig. 1 the set of reactions for the model with parametersm 2
m nand n 1. In the general case, there are 2 reachable con gurations for
the proteinX. Thus, whenm n gets big, we can no longer enumerate chem-
ical species (nor reactions). We can sample stochastic semantics by using
agents-based simulation algorithms [8]. But the integration of the di erential
semantics, or the computation of more complex properties about the distri-
3
urtsCamporesi, Feret, Koeppl, and Petrov
k1;0k k
P X u;u;u X u;u;pP X u;u;u X p;u;u P X u;u;u X u;p;u
kk k dd d
k1;1k k
P X u;u;p X p;u;p P X u;u;p X u;p;p P X u;p;u X u;p;p
k k kd d d
k k k1;2P X u;p;p X p;p;p P X p;u;p X p;p;p P X p;p;u X p;p;p
k kd d kd
k k k1;1P X u;p;u X p;p;u P X p;u;u X p;p;u P X p;u;u X p;u;p
k kd d kd
(a) Phosphorylation and de- (b) Phosphorylation and de- (c) Phosphorylation and de-
phosphorylation of the rst phosphorylation of the sec- phosphorylation of the third
site. ond site. site.
Fig. 1. Chemical reactions for m 2 and n 1.
bution of traces (or states) is impossible due to the combinatorial complexity.
We notice that we can use symmetries among the sites x ;:::;x so as1 m
to reduce the dimension of both the stochastic and the di erential semantics.
Indeed what is important, is not which sites x are phosphorylated in a giveni
protein, but how many are phosphorylated. We introduce an equivalence
relation over proteins X: we say that two proteins are -equivalent if, and
only if, (i) the number of phosphorylated sites among the list x ;:::;x is1 m
the same for both proteins, and (ii) the phosphorylation state of the sites yj
is the same in both proteins, for any integer j between 1 and n. Thus the set
nof reachable con gurations for the protein X, is quotiented into m 1 2 -
equivalence classes. A simpli ed set of reactions can be proposed, by choosing
a representative among each -equivalence class. Indeed, up to updating
reaction rate constants, we may assume that the sites x ;:::;x are always1 m
phosphorylated in increasing order, and dephosphorylated in decreasing order.
In Fig. 2, we give the set of so obtained simpli ed reactions (for m 2
and n 1). We can notice that whenever the sites x and x are both1 2
unphosphorylated, only the site x can be phosphorylated (with a rate twice1
as big as in the initial reaction) and that whenever the sites x and x are1 2
both phosphorylated, only the sitex can be dephosphorylated (at a rate twice2
bigger than in the initial reaction). Such a simpli ed set of reactions can be
used to compute a reduced stochastic semantics and a reduced di erential
semantics.
In this paper, we propose two formal frameworks so as to combine model
reductions for stochastic and di erential semantics, and we apply these frame-
works for combining existing model reductions [10,7,11] with a model reduc-
tion based on the detection of symmetric sites. Both reduced semantics can
be derived automatically, without explicitly computing neither the unreduced
semantics, nor any intermediate semantics. For instance, the fragments-based
model reduction that is proposed in [10,7] abstract away the correlation be-
tween the phosphorylation states of the sites y (for any integer j between 1j
m 1and n), because, this correlation is tested in no reaction. This yields n2
4
rs?s??r?????sr?s?rss????s???sr?srr?s??????s??r?ssr?s??sp??r?sq???rsssr?s???r????r?s?rrsr????????rrsrr?s??????r?rr?Camporesi, Feret, Koeppl, and Petrov
k1;0
P X u;u;u X u;u;p
k2k kdP X p;u;u X p;p;uP X u;u;u X p;u;u k1;12kk dd P X p;u;u X p;u;p
k2k kdP X p;u;p X p;p;pP X u;u;p X p;u;p
k1;22kk dd P X p;p;u X p;p;p
(a) Phosphorylation and de- kd(b) Phosphorylation and de-
phosphorylation of the rst phosphorylation of the sec- (c) Phosphorylation and de-
site. ond site. phosphorylation of the third
site.
Fig. 2. Simpli ed chemical reactions for m 2 and n 1.
fragments for the protein X. Combined with sites symmetries, we would get
only 2n m 1 classes of fragments. The fragments-based approach achieves
no reduction in the case of the stochastic semantics [11]: thus we can only
nreduce to m 1 2 classes of species (or fragments) in this case.
3 Stochastic semantics
In this section, we review the generic framework that has been proposed in [11]
for reducing the stochastic semantics of weighted labeled transition systems.
This reduction technique is based on the use of backward bisimulations [4] so as
to prove statistical invariants. We use these invariants to lump [3] some states
of the transition system together, this is a weak lumping which is sound only if
the statistical invariants are satis ed by the initial distribution of states. We
extend this framework with a commutative operator to combine abstractions.
We show that this operator is a pushout, and that abstraction composition
distributes over it.
3.1 Weighted labeled transition systems
We rst introduce the notion of weighted labeled transition system.
De nition 3.1 A weighted labeled transition system (WLTS) is a tuple
Q;L; ;w;I; where: (i) Q is a set of states, (ii) L is a set of transi-0
tion labels, (iii) Q L Q is a relation, (iv) w is a mapping between
Q L andR , (v)I Q is a nite subset of states, and (vi) : I 0; 10
is a discrete probability distribution.
Let us now consider Q;L; ;w;I; a WLTS. A state q I is called0
an initial state. Moreover, the probability that the system is in the stateq I
at time t 0 is equal to q . An element q; ;q denotes a transition0
from stateq to stateq ; the symbol is the label of the transition. We denote

by q q the fact that the tuple q; ;q belongs to . In the following we
will assume that a label fully identi es a transition step. That is to say that

given a label L, and four states q ;q ;q ;q Q such that q q and1 2 11 2 1
5
q1p??P??q?p?Prr?ss1P?p??????srsP?s?rqss????sqp?sr?sr?s1?r????????????1r???r??p?r?p?s?rrsq?q1q1?r?1?P??????r?s?s?prCamporesi, Feret, Koeppl, and Petrov

q q , then we have q q and q q . We denote by L q L the set2 1 22 1 2

of labels for which there exists q Q such that q q . Moreover, we also
assume that the system is nitely branching, that is to say that given a state

q, the set L q is nite. The function w associates each transition q q to
its weight (or rate) w q; R 0 .
Now we de ne a continuous-time semantics for WLTS. This semantics is
de ned as a probability density distribution of the traces with k steps, for any
natural numberk N. First we give the de nition of nite traces as follows:
De nition 3.2 A nite trace is given by an initial state q I and a nite0
ksequence ;t;q L R Q of triples such that: for any integeri i i 1 i k
ii such that 1 i k, we have q q .i 1 i
;t ;t1 1 k k
Such a trace is denoted as: q q q q . Whenever i 1,0 1 k 1 k
the non negative real number t denotes the amount of time between the i-i
th transition of the system and the previous one, moreover t denotes the1
amount of time between t 0 and the rst transition. Moreover, the number
of transitions (here k) is called the size of the trace.
Now we de ne the probability density distribution of the traces of size k,
for any natural number k N. For that purpose, we introduceIR as the set
of intervals of positive real numbers.
De nition 3.3 Given a natural number k N, an initial state q I and a0
ksequence ;I;q L IR Q of tuples, the set of traces that isi i i 1 i k
de ned as follows:
;I ;I ;t ;t1 1 k k 1 1 k k
q q :::q q : q q :::q q t I ;0 1 k 1 k 0 1 k 1 k i i
is called a cylinder set of traces.
We denote byT the set of cylinder sets of traces.IR
Now we de ne the probability of a cylinder set of traces.
De nition 3.4 Letk be a natural number inN. The probability that a trace
;I ;I1 1 k k
of sizek lies in the following cylinder set of traces: q q :::q q ,0 1 k 1 k
is given by the following expression:
a q inf I a q sup Ii 1 i i 1 iw q ; e ei 1 i
q 1 i k ;00 i a qi 1
where for any state q, a q is the activity of the system at state q which is
de ned as: a q : w q; L q .

We notice that initial states are selected according to the distribution .0
Moreover, whenever the system is in the state q, the next state is selected
6
???q?pqpp?1q?P??pp|???q1Pqp?Ppzt?P?pq1?qPqqp1???1!?Pq??pp???qPupq????q?pp?q?p?1???P??????p??q???p?pPPqq??P?qqp?)?Camporesi, Feret, Koeppl, and Petrov
Fig. 3. An abstraction between two transition systems.
w q; by computing the transition labeled with L q with probability
a q
and the waiting time until a next reaction happens is chosen according to an
exponential probability distribution with the parameter that is equal to the
activity a q of the system.
3.2 Abstraction
The description of a system can be less or more ne grained, which leads to
the notion of abstraction between WLTSs:
De nition 3.5 An abstraction between two WLTSsS : Q;L; ;w;I;0
L Q Q LandS : Q;L; ;w ;I ; is a tuple S;S ; ; ; where :L0
Q QL ,