Paris/Stochastic model

From 2007.igem.org

Revision as of 18:08, 24 October 2007

• Main Page
• Introduction
• Design Process
• Modeling
• Construction Process
• Results
• Perspectives
• Acknowledgments

In this last part of the models section, we are developing a stochastic simulation of the microscopic model. The major contribution is to handle in a stochastic context a dynamic and heterogeneous population of bacteria.

Introduction

In 1977, Gillespie has developed an exact Simulation Stochastic Algorithm (SSA) dedicated to the simulation of homogeneous chemical systems. This method was recently used in many applications for the simulation of biological systems. A good point of this approach is that it allows to handle biochemical systems where numbers of molecules are low and that cannot be well characterized by classical approach using differential equations and chemical concentrations. Nevertheless this method requires strong hypotheses about the spatial homogeneity of molecules distribution. Extensions of Gillespie's SSA have been proposed to deal with compartments.

As our system is composed of a growing and heterogeneous population of bacteria, we propose to use this extension to simulate it. In the following paragraphs, we first detail the extended SSA we use and then we present some samples generated by our implementation using the set of parameters found in the numerical analysis of the model. Note that the main contribution here is in the development of the simulation algorithm.

Extended SSA

Gillespie's SSA

From a computational point of view, the Gillespie SSA relies on a discrete events simulation of chemical reactions between individual molecules. A reaction R_μ like <math>A + B \rightarrow C</math> occurs when reactants A and B meet with enough energy to produce a molecule C. The probability that this reaction occurs during an infinitesimal time is proportional to the number of molecules A and B in the system (dependence on the concentration) and a coefficient c_μ called the stochastic constant (corresponding to the reaction kinetic) when reactants are uniformly distributed in the system (intuitively meaning that each couple of molecules has the same probability to meet). This probability allows to compute, given a system composing of molecules that can react with respect to reactions R₁ ... R_N, the probability law p(mu,tau) that the next reaction to occur is R_mu after tau units of time.

The algorithm developed by Gillespie consists in iterating the drawing of the next reaction mu to occur and the corresponding next reaction time tau using p(mu,tau) and making the system evolves. Assuming that S is chemical solution where reactions R0 ... RN can occur at a given time t, the SSA can be expressed as follows:

 SSA (S,t,R0,...,RN) = {
   compute mu and tau using p(mu,tau)
   compute S' by applying mu on S
   return  (S',t+tau)
 }

Handling Membranes

In the SSA, molecules have to be uniformly distributed in space. It cannot be straightly used to deal with systems that exhibit a complex spatial organization, as the system we are interested in. Taking space into account means modifying the probability law p(mu,tau) in order to take care of the localization of the reaction. Obviously, it cannot be computed in practice for any kind of organization, but it is possible to develop ad-hoc algorithms for specific organizations.

We propose to consider a population of bacteria as a nested membranes system, called compartments. The environment where bacteria live is represented by a compartment that contains molecules and bacteria, and a bacterium is then represented by a compartment that contains molecules. In each compartment, the contained elements are assumed to be uniformly distributed in space.

Extended Algorithm

The extension relies on the fact that compartments elements are uniformly organized, meaning the SSA can be used in each compartment. Intuitively, at each iteration of the new algorithm, the standard SSA is evaluated on each compartment of the system ; the compartment with the smallest reaction time is updated (with respect to the corresponding reaction) and the other compartment remain unchanged. This procedure is naturally recursive and can be expressed as follows:

 ExtSSA (S,t,R0,...,RN) = {
   (S',t') := SSA (S,t,R0,...,RN)
   foreach compartment M of S do
      let (M',tM) = ExtSSA (M,t,R0,...,RN) in
        if tM < t'
        then
          S' := replace M by M' in S
          t' := tM
   done
   return  (S',t')
 }

This algorithm is taken from here.

MGS Implementation

As presented here, the MGS language provides a specific rules application strategy implementing the SSA. We propose to implement the algorithm ExtSSA using MGS. The whole program is described here, with the representation of the system, the encoding of chemical reactions and a proposition of optimization for ExtSSA.

State and Structure

Dynamics

In this context, chemical reactions are specified using transformation rules.

Optimization

Scheduler => fast

Some Results