Introduction

Cellular automata consist of a regular array of cells, termed a grid, of arbitrary dimension. Any cell can be in two or more distinguishable states. Given an initial configuration of these states the grid evolves without any further intervention, hence the term automaton, with every new configuration based solely on the previous configuration and a set of fixed rules. Often the evolution of cellular automata progresses in a discrete way, in this case every new configuration is called a ‘generation’, nevertheless continuous cellular automata do indeed exist (fig 1.1). Since the 1940’s when the concept of a cellular automaton first arose as a purely mathematical problem [1]

, these systems have found new implementations in a broad range of disciplines. In physics, chemistry and biology cellular automata are widely used in simulations involving emerging complex behavior and self-organization, while from the viewpoint of computer science the fact that some cellular automata display what is called turing completeness is of considerable interest [2]

S. Wolfram. Universality and complexity in cellular automata. Physica D 10:1-35, 1984.

. Also in cryptography cellular automata are considered to be useful because of their uni-directional evolutionary character [3]

S. Sen, C. Shaw, D.R. Chowdhuri, N. Ganguly, and P.P. Chaudhuri. Cellular Automata Based Cryptosystem (CAC), ICICS ‘02. Proceedings of the 4th International Conference on Information and Communications Security, 303--314. Springer-Verlag, London, UK 2002.

.

Additionally these systems are thought to be present in nature as being, for example, the mechanism leading to texture formation on animal skin. Computer models of cellular automata in the continuum approximation are able to reproduce patterns similar to these textures, which in nature emerge from the continuous interaction between pigment cells [4]

. From a synthetic biology point of view, this connection between a formal, algorithmical mathematical model and similar expression observed in living cells poses the interesting question of whether this behavior can be syntheticallly implemented within living cells, thereby making them generate controllable patterns.

The approach that synthetic biology propagates, designing modular genetic components and combining these to comprise more complex genetic systems, is particularly fit to tackle a problem of this kind since in the workings of cellular automata we can roughly distinguish the following abillities that cells should posess: to switch between a discrete number of states, to communicate information about their state to their neighbors and to interpret and act upon information received from their neighbors. Within the synthetic biology framework these functionalities can be independently designed and subsequently combined to display total system behavior.

The particular cellular automaton which we aim to design is ‘Conway’s Game of Life’, one of the best known and most extensively studied cellular automata. It was proposed by mathematician John Conway [6]

in 1970 as a simplification of previous research by von Neumann [1]. In Conway’s Game of Life cells exist and interact on a two-dimensional grid. Two states are distinguished, in the game’s language these states are termed ‘alive’ or ‘dead’, and cells can switch between these two states depending on their number of live neighbors: if either more than three or less than three of a cells neighbors are alive, that cell switches to the dead state. If exactly three of a cells neighbors are alive, that cell switches to the live state. We use a slight, but not uncommon, simplification of the original ruleset, where having two alive neighbors would imply that a cell remains in its current state. The terminology stems from the idea that, defined as above, the game can be used to simulate ‘real life’ processes where living entities tend to die in overcrowded regions whereas also they are not able to survive on their own.

Figure 1.1: the Gosper’s Glider Gun, an example of a discrete automaton.

To design living cells that display this behavior we will use the natural ability found in cells to communicate their presence to cells in their proximity and likewise sense the presence of other cells by means of quorum sensing mechanisms. Quorum sensing is used by bacteria to coordinate behaviors based on the density of their population. Bacteria that are capable of quorum sensing constantly produce certain signal molecules called autoinducers. Based on the concentration of these signal molecules bacteria respond, and regulate a number of different processes. Quorum sensing can occur within a single bacterial species, as well as between different species. An example of quorum sensing regulated bacterial behavior is the formation of biofilm [7]

. Another example is the production of signal molecule by Vibrio fischeri to adjust the production of luciferase, a light emitting protein, by cells present in close proximity. There are different types of quorum sensing systems which have their own signal molecules. One class of signal molecules is that of the acyl-homoserine lactone autoinducers. This class of signal molecules is used by different species of bacteria like V. fischeri, and P. aeruginosa. Each species uses a slightly different acyl-HSL, and there is a strong homology in the proteins involved in the quorum sensing systems of acyl-homoserine lactone producing bacteria. For instance TraR in A. tumefaciens, LasR in P. aeruginosa an LuxR in V. fischeri.

The acyl-HCL system was first described in V. fischeri [8]

. The acyl-HSL of V. fischeri is 3-hexanoyl homoserine lactone (3OC6-HSL)2. 3OC6-HSL is synthesized by the LuxI protein. 3OC6-HSL binds to the transcription regulator LuxR and dimeric LuxR with bound 3OC6-HSL then binds to DNA and activates transcription of the Lux operon, which result in the production of luciferase. In this project the quorum sensing genes luxI and luxR will be used to make so called ‘sender’ and ‘receiver’ cells. This was done before by Basu et al [9]

S. Basu, R. Mehreja, S. Thiberge, M. T. Chen, and R. Weiss. Spatiotemporal control of gene expression with pulse-generating networks. PNAS USA, 101(17):6355–6360, April 2004.

. Here, luxI was put behind a constitutive promoter on a plasmid in one strain, and luxR in another. In the latter the LuxR-HSL complex activates certain genes. This is one of the applications where these quorum sensing genes can be used.

Using this signalling mechanism the cells will be defined to have an ON-state, in which they continuously send a signal to their neighbors, and an OFF state in which cells do not send at all. In order for a cell to count the number of neighboring cells in the ON-state we will develop a novel genetic detection mechanism which will be able to distinguish between three types of signals: ‘low’, ‘medium’ and ‘high’. In parallel with Conway’s Game of Life these will be assigned the meaning of respectively ‘less than three neighbors in the ON-state’, ‘three neighbors in the ON-state’ and ‘more than three neighbors in the ON-state’. In the lab we aim to engineer these genetic functionalities in order to work in E.coli cells and additionally determine a physical setup such that the E.coli cultures can live and interact in a grid-like, two dimensional environment as they do in Conway’s Game of Life.

As yet we have not succeeded in developing a fully operational system, nevertheless in this report we describe the steps we took towards being able to reproduce Conway’s Game of Life in vivo. The the Design/Interval Switch menu describes the design and workings of the detection mechanism, the interval switch. The complete genetic circuit design and the choice of genetic parts are explained in "Genetic Circuit". In "Physical Setup" we provide suggestions for a suitable physical setup in which to incorporate the cells. In "Single-Cell model" and "Spatial Model" computer modeling work is presented and expectations of the system’s behavior are discussed both on the single cell level as well as involving cellular interactions on a grid (spatial model). And finally, in "Results" we provide the results we obtained up till now, discuss these results and provide recommendations for further work on this topic. We also see how we measure up to get some medals! Also check out our Team and the other options under "About..."