2014-09, Ganguly, Arnab, Petrov, Tatjana, Koeppl, Heinz

We consider a continuous-time Markov chain (CTMC) whose state space is partitioned into aggregates, and each aggregate is assigned a probability measure. A sufficient condition for defining a CTMC over the aggregates is presented as a variant of weak lumpability, which also characterizes that the measure over the original process can be recovered from that of the aggregated one. We show how the applicability of de-aggregation depends on the initial distribution. The application section is devoted to illustrate how the developed theory aids in reducing CTMC models of biochemical systems particularly in connection to protein-protein interactions. We assume that the model is written by a biologist in form of site-graph-rewrite rules. Site-graph-rewrite rules compactly express that, often, only a local context of a protein (instead of a full molecular species) needs to be in a certain configuration in order to trigger a reaction event. This observation leads to suitable aggregate Markov chains with smaller state spaces, thereby providing sufficient reduction in computational complexity. This is further exemplified in two case studies: simple unbounded polymerization and early EGFR/insulin crosstalk.

2013, Feret, Jérôme, Koeppl, Heinz, Petrov, Tatjana

In this paper, we propose an abstract interpretation-based framework for reducing the state space of stochastic semantics for protein-protein interaction networks. Our approach consists in quotienting the state space of networks. Yet interestingly, we do not apply the widely-used strong lumpability criterion which imposes that two equivalent states behave similarly with respect to the quotient, but a weak version of it. More precisely, our framework detects and proves some invariants about the dynamics of the system: indeed the quotient of the state space is such that the probability of being in a given state knowing that this state is in a given equivalence class, is an invariant of the semantics. Then we introduce an individual-based stochastic semantics (where each agent is identifed by a unique identifier) for the programs of a rule-based language (namely Kappa) and we use our abstraction framework for deriving a sound population-based semantics and a sound fragments-based semantics, which give the distribution of the traces respectively for the number of instances of molecular species and for the number of instances of partially defined molecular species. These partially defined species are chosen automatically thanks to a dependency analysis which is also described in the paper.

2012-05, Feret, Jerome, Henzinger, Thomas, Koeppl, Heinz, Petrov, Tatjana

The induction of a signaling pathway is characterized by transient complex formation and mutual posttranslational modification of proteins. To faithfully capture this combinatorial process in a mathematical model is an important challenge in systems biology. Exploiting the limited context on which most binding and modification events are conditioned, attempts have been made to reduce the combinatorial complexity by quotienting the reachable set of molecular species into species aggregates while preserving the deterministic semantics of the thermodynamic limit. Recently, we proposed a quotienting that also preserves the stochastic semantics and that is complete in the sense that the semantics of individual species can be recovered from the aggregate semantics. In this paper, we prove that this quotienting yields a sufficient condition for weak lumpability (that is to say that the quotient system is still Markovian for a given set of initial distributions) and that it gives rise to a backward Markov bisimulation between the original and aggregated transition system (which means that the conditional probability of being in a given state in the original system knowing that we are in its equivalence class is an invariant of the system). We illustrate the framework on a case study of the epidermal growth factor (EGF)/insulin receptor crosstalk.

2010, Camporesi, Ferdinanda, Feret, Jérôme, Koeppl, Heinz, Petrov, Tatjana

Molecular biological models usually suffer from a large combinatorial explosion. Indeed, proteins form complexes and modify each other, which leads to the formation of a huge number of distinct chemical species. Thus we cannot generate explicitly the quantitative semantics of these models, and it is even harder to compute their properties. In this extended abstract, we summarize a framework for reducing the combinatorial complexity of models of biochemical networks. We use rules‐based languages to describe the interactions between proteins. Then we compile these models into continuous‐time Markov chains. Finally, we use backward bisimulations in order to reduce the dimension of the state space of these Markov chains. More specifically, these backward bisimulations are defined thanks to an abstraction of the control flow of information within chemical species and thanks to an algorithm which detects which protein sites have the same capabilities of interaction.

2013, Petrov, Tatjana, Koeppl, Heinz

The paper considers a model reduction technique that is well-suited for biochemical reaction systems giving rise to the assembly of a large number of different molecular species. The reduction is performed by grouping species with common properties, directly from the model specification in terms of a rule-based language. In recent works, general algorithms for the exact reductions of rule-based models were established, but the state space often remains combinatorial. We extend this line of research by introducing approximate reductions, and an error measure which allows us to quantitatively study the effect of approximate model reductions.

2012-12, Petrov, Tatjana, Feret, Jerome, Koeppl, Heinz

Many bio-molecular reactions inside the cell are characterized by complex-formation and mutual modification of a few constituent molecules that give rise to a combinatorial number of reachable complexes or species. For such cases rule-based models (or site-graph-rewrite rules), offer a compact model description, by enumerating only the necessary context of interacting molecules. Such a model specification induces symmetries in the underlying Markov chain, which we have recently exploited for model reduction, based on a backward Markovian bisimulation. Interestingly, the method showed a theoretical possibility of reconstructing the high-dimensional species-based dynamics from the aggregate state. In this paper, we present a procedure for reconstructing the high-dimensional species-based dynamics from the aggregate state, and we provide an algorithm for computing such de-aggregation functions explicitly. The algorithm involves counting the automorphisms of a connected site-graph, and has a quadratic time complexity in the number of molecules which constitute the site-graphs of interest. We provide illustrating case studies.

2011-05, Koeppl, Heinz, Petrov, Tatjana

In this paper we present a formalism based on stochastic automata to describe the stochastic dynamics of signal transduction networks that are specified by rule-sets. Our formalism gives a modular description of the underlying stochastic process, in the sense that it is a composition of smaller units, agent-views. The view of an agent is an automaton that identifies all local modification changes of that agent (internal state modifications, binding and unbinding), but also those of interacting agents, which are tested within the same rule. We show how to represent the generator matrix of the underlying Markov process of the whole rule-set as Kronecker sums of the rate matrices belonging to individual view-automata. In the absence of birth the automata are finite, since the number of different contexts in which one agent can appear in a rule-set is finite. We illustrate the framework by an example that is related to cellular signaling events.

2013, Klann, Michael, Paulevé, Loïc, Petrov, Tatjana, Koeppl, Heinz

Studying spatial effects in signal transduction, such as colocalization along scaffold molecules, comes at a cost of complexity. In this paper, we propose a coarse-grained, particle-based spatial simulator, suited for large signal transduction models. Our approach is to combine the particle-based reaction and diffusion method, and (non-spatial) rulebased modeling: the location of each molecular complex is abstracted by a spheric particle, while its internal structure in terms of a site-graph is maintained explicit. The particles diffuse inside the cellular compartment and the colliding complexes stochastically interact according to a rulebased scheme. Since rules operate over molecular motifs (instead of full complexes), the rule set compactly describes a combinatorial or even infinite number of reactions. The method is tested on a model of Mitogen Activated Protein Kinase (MAPK) cascade of yeast pheromone response signaling. Results demonstrate that the molecules of the MAPK cascade co-localize along scaffold molecules, while the scaffold binds to a plasma membrane bound upstream component, localizing the whole signaling complex to the plasma membrane. Especially we show, how rings stabilize the resulting molecular complexes and derive the effective dissociation rate constant for it.

2012-06, Petrov, Tatjana, Ganguly, Arnab, Koeppl, Heinz

In this paper, we discuss a method for decomposition, abstraction and reconstruction of the stochastic semantics of rule-based systems with conserved number of agents. Abstraction is induced by counting fragments instead of the species, which are the standard entities of information in molecular signaling. The rule-set can be decomposed to smaller rule-sets, so that the fragment-based dynamics of the whole rule-set is exactly a composition of species-based dynamics of smaller rule-sets. The reconstruction of the transient species-based dynamics is possible for certain initial distributions. We show that, if all the rules in a rule set are reversible, the reconstruction of the species-based dynamics is always possible at the stationary distribution. We use a case study of colloidal aggregation to demonstrate that the method can reduce the state space exponentially with respect to the standard, species-based description.

2011, Hafner, Marc, Petrov, Tatjana, Lu, James, Koeppl, Heinz

Despite the early success stories synthetic biology, the development of larger, more complex synthetic systems necessitates the use of appropriate design methodologies. In particular, the integration of smaller circuits in order to perform complex tasks remains one of the most important challenges faced in synthetic biology. We propose here a methodology to determine the region in the parameter space where a given dynamical model works as desired. It is based on the inverse problem of finding parameter sets that exhibit the specified behavior for a defined topology. The main issue we face is that such inverse mapping is highly expansive and suffers from instability: small changes in the specified dynamic property could lead to large deviations in the parameters for the identified models. To solve this issue, we discuss regularized maps complemented by local analysis. With a stabilized inversion map, small neighborhoods in the property space are mapped to small neighborhoods in the parameter space, thereby finding parameter vectors that are robust to the problem specification. To specify dynamic circuit properties we discuss Linear Temporal Logic (LTL). We apply these concepts to two models of the cyanobacterial circadian oscillation.