Team:LCG-UNAM-Mexico/Description:CA

From 2009.igem.org

Cellular Automaton



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 its own state and the states of its neighbors at time t-1. Link a WIKIPEDIA.

The evolution in time depends on the rules that you define. Wolfram REFERENCE proposed a classification for the rules, but 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 discover complex behavior by defining simple rules in a CA REFERENCE 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.

LCG automata1.png LCG automata2.png
Figure1. Right: E. Coli microscopy. Left: Our CA implementation, 120x120. Each cell in the CA has a fixed length unit of 2micrometers.

Our CA is in 2 dimensions X and Y, this because 3-dimensions dynamics would not change significantly the behaviour of this particular system and because of limitations in computational resources.

We decided to use the CA because of the spatial dynamics involved in the alarm system. With the CA we can, in parallel, simulate bacteria growth, phage diffusion, infection, AHL diffusion, bacteria movement, bacteria lysis.

Here you can see the video of the simulation LINK a VIDEO.


Design and Implementation

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 n2¬. 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.



Locations of visitors to this page