From 2009.igem.org

Revision as of 07:08, 16 October 2009

Contents

• Cellular Automata
• Design
• The Algorithm
• Simulations

Cellular Automata

A cellular automaton is discrete dynamical system: a grid in a n-dimensional space in which each cell has one of a finite number of states, say on and off. The state for a given cell at time t is a function of it’s own state and the states of its neighbours at time t-1.
As time advances in discrete steps, the system evolves according to universal laws. Every time the clock ticks, the cells update their states simultaneously.
Cellular Automaton can simulate continuous physical systems described by Partial Differential Equations (PDE) .

The evolution in time depends on the rules that you define, in fact you can define any rule you want and you will get amazing and funny patterns.

It has been proved that a CA can be a Universal Turing Machine, in fact different CA are used to make a wide variety of computations. You can simulate a lot of different complex systems using a CA and you can also see emergence of complex behaviour by defining simple rules in a CA ( Game Of Life) .

If we think of the cells in the grid as if they were biological cells we can simulate a population of bacteria, tissue growth, swarming etc.

Design

Comparision between E. Coli micrography and a simulation of duplication and movement in the CA.

We will use the word cell for the elements of the grid in the automaton and the word bacterium for E coli.
The state of the cells in the CA is an array of integers representing different parameters.

CA[i,j] =[s, d, l, r, i, lt, bs, np]

s = 1 if there is a bacteria in this cell 0 otherwise.
d = direction [1, 2, ... 8] (random variable)
l = persistence time REFERENCE
r = time until duplication (random variable)
i = infection state. 1 if infected 0 otherwise.
lt = time until lysis (random variable).
bs= Burst Size, amount of phages an infected bacteria will produce (random variable)
np= number of phages.


We sample indexes of the rows and columns in the grid at random and then we iterate in that order, thus we have a random sampling without replacement that require only 2n random numbers instead of <math>n^2</math>.

For each cell we verify if it has a bacterium, if so:
Check if it should duplicate, change direction or move. We also have phages in the grid so we need to check for infections on each iteration: if there are phages in a cell occupied by a bacterium this will become infected with some fixed probability. An infected cell will produce new phages, this number is sampled from the Burst Size Distribution generated by the Stochastic Kinetic Simulations.

The Algorithm

This pseudo code is a simplified version of the Matlab script we implemented which is available at request.
To implement the algorithm we used two CA data structures but for simplicity we present here all the operations on a single CA object.

Comments start with     //

For each cell in the CA sampled at random*:

//Infection

       if   np>0 and runif(0,1)<infectionProb

               //bacteria becomes infected.

i = 1;     

               bs= sampleBurstSizeDistribution();

               lt = sampleLysisTimeDistribution();

                //bacterium cannot duplicate or move anymore.

               r = l = NULL;

               continue;

       //For Infected Bacteria:

       elseif i==1

               if lt==0  //Is time for lysis?.

                       //number of phages at t-1 plus those produced by

//the bacterium.

np += bs;   

s=0; //bacterium death.

               else

                       lt--;

               continue;

//Duplication.

elseif r ==0

               if checkForAvailableSpace(neighbourhood_ij) == TRUE

                       duplicate;

               sampleDuplicationTimeDistribution();

               set r for the new bacteria;

               continue;

       //Change Direction

       elseif l==0

               d=randomSample([1,2,..,8]);

               r=r-1;   l =persistence_time;

       //Movement.        

       else                

//check if the space the bacterium is moving towards //is empty.

               (New_i  New_j) = checkForSpace(i.j,d)

               r--; l--;

               //move bacterium

CA[New_i, New_j ]= CA[i ,j];

//Bacterium left an empty space in the CA.

CA[i,j]= [ 0 ];

end

• Recent changes
• What links here
• Related changes
• Special pages
• My preferences

• Printable version
• Permanent link
• Privacy policy
• Disclaimers