Team:Tsinghua-A/solid model
TSINGHUA-AModelling--solid medium
Contents
IntroductionOur Method
Basic Assumptions
Overall Discretization
Placement Rules
Iteration Rules
References
Introduction
Spatial factors have a great impact on the results of population competition or cooperation. To understand spatial effects better, we develop our discrete probabilistic solid model.
This model is then used to simulate cell growth in real medium. Also, it is used as the core algorithm in our E-coli war game.
back to the top
This model is then used to simulate cell growth in real medium. Also, it is used as the core algorithm in our E-coli war game.
back to the top
Our Method
It seems we can use Partial Differential Equation (PDE) directly. However, it will be too complicated to execute PDE fast in program and also difficult for visualization of the changing process, not to say adapting it to our game.
Thus, we choose another method as our solid model fundamental: cellular automaton(CA).
[wikipedia] A cellular automaton consists of a regular grid of cells, each in one of a finite number of states. An initial state (time t = 0) is selected by assigning a state for each cell. A new generation is created (advancing t by 1), according to some fixed rule (generally, a mathematical function) that determines the new state of each cell in terms of the current state of the cell and the states of the cells in its neighborhood. Typically, the rule for updating the state of cells is the same for each cell and does not change over time, and is applied to the whole grid simultaneously. [1]
Using the idea of CA, first, we discretize whole space in a medium and total time we take to nourish cells; second, we set placement rules, i.e. events that will happen after a cell is put onto medium; third, we set iteration rules, i.e. events that will trigger during each iteration in simulation.
back to the top
Thus, we choose another method as our solid model fundamental: cellular automaton(CA).
[wikipedia] A cellular automaton consists of a regular grid of cells, each in one of a finite number of states. An initial state (time t = 0) is selected by assigning a state for each cell. A new generation is created (advancing t by 1), according to some fixed rule (generally, a mathematical function) that determines the new state of each cell in terms of the current state of the cell and the states of the cells in its neighborhood. Typically, the rule for updating the state of cells is the same for each cell and does not change over time, and is applied to the whole grid simultaneously. [1]
Using the idea of CA, first, we discretize whole space in a medium and total time we take to nourish cells; second, we set placement rules, i.e. events that will happen after a cell is put onto medium; third, we set iteration rules, i.e. events that will trigger during each iteration in simulation.
back to the top
Basic Assumptions
Our solid model has several basic assumptions that are indispensable.
I. A colony-to-grid representation in a 200×200 mesh grid (one grid represents a cell colony) is good enough to simulate bacterial growth in a real medium. (See Overall Discretization)
II. The time it takes for AHLs and nutrient to diffuse into surrounding grids and meet concentration balance is very short compared to the time for cells to grow into colonies. [2] (See Placement Rules)
III. We suppose decomposing rate of AHLs and utilization rate nutrition are constants, and decomposing rate is relatively high compared to growth rate of cells. [3] (See Placement Rules)
back to the top
I. A colony-to-grid representation in a 200×200 mesh grid (one grid represents a cell colony) is good enough to simulate bacterial growth in a real medium. (See Overall Discretization)
II. The time it takes for AHLs and nutrient to diffuse into surrounding grids and meet concentration balance is very short compared to the time for cells to grow into colonies. [2] (See Placement Rules)
III. We suppose decomposing rate of AHLs and utilization rate nutrition are constants, and decomposing rate is relatively high compared to growth rate of cells. [3] (See Placement Rules)
back to the top
Overall Discretization
In the first place we do spatial and time discretization. The whole medium is discretized into a 200×200 mesh grid, and valid space for living is a disk inscribed on it with a radius of 100. Using assumption I, we set each cell colony (abbreviated as ‘cell’ in following sections) into a corresponding grid to represent its presence. In software simulation, we keep three matrices of 200×200 size to record the amount of cells, nutrient and AHLs in each grid, respectively.
Meanwhile, the whole time we take to cultivate cells is discretized into 1,200 iterations. After each iteration, the number of substances in each grid changes according to certain rules (will be discussed in following sections).
back to the top
Meanwhile, the whole time we take to cultivate cells is discretized into 1,200 iterations. After each iteration, the number of substances in each grid changes according to certain rules (will be discussed in following sections).
back to the top
Placement Rules
When we place a cell onto a corresponding grid, concentrations of substances in adjacent grids also change as a result. We apply assumption II to develop a set of synchronous placement rules: (1)The event of placing a cell triggers concentration incline in surrounding grids synchronously (2)Cell’s influence keeps unchanged in subsequent iterations as long as the cell exists. (3)Removal of a cell has inverse effects.
According to assumption III, concentrations of AHL and nutrient will decline in each iteration if their generative sources are removed.
Different types of cell affecting different kinds of substances are illustrated below:
back to the top
According to assumption III, concentrations of AHL and nutrient will decline in each iteration if their generative sources are removed.
Different types of cell affecting different kinds of substances are illustrated below:
back to the top
Placing Farmers
When placed, a farmer will eject nutrient to surrounding 5×5 grids, and the amount of nutrient in each grid will increase by 1. Then the amount of nutrient will hold on until the farmer is killed. When a farmer is removed, the amount decrease by 1.
Fig.1 Farmers release nutrient (graphed in green) into surrounding grids
Placing Warriors
When placed, warriors eject AHLs to surrounding 3×3 grids, and the amount in each grid increases by 1; Then the amount of AHL molecule will hold on until the farmer is removed. When warriors being removed, the amount decreases by 1.
Fig.2 Warriors release AHLs (graphed in red) into surrounding grids
back to the top
back to the top
Iteration rules
In the i_k-th iteration, our program traverses the whole mesh grid and checks for two missions: death penalty and probabilistic growth based on states of the i_(k-1)-th iteration. We may call the grid which the program is checking ‘present grid’ for convenience.
Death Penalty
There are two and only two cases which causes cell death: nutrient in present grid is depleted; or there are enemy AHLs in present grid. It is noted that farmers cannot die of case I because they create nutrient themselves. As for case II, when AHL-I and AHL-II are in adjacent grid and the colony inside the grid is warrior, one of them will be killed (randomly).
Another mission during iteration is to simulate bacterial growth. Concentration of AHL is excluded in this section, because it only functions in Death Penalty part. Since nutrient contribute to cell growth, a natural idea is to set a probabilistic model of any empty grid, described by a linear equation:
Where (x,y) are coordinates of present grid, P_k (x,y) is the probability an adjacent cell can grow into present grid in i_k-th iteration, C_k (x,y) is concentration of nutrient in present grid in i_k-th iteration, α is a coefficient that remains unchanged during simulation. We have tried different values of α and eventually set α=0.013 to fit experimental results well.
This equation helps our program to judge whether or not an adjacent cell can grow into present grid in i_k-th iteration; after this judgement is settled, we choose randomly from surrounding grids that have cells in them, supposing we select cell A, and inherit its cell type to get clone cell B in present grid. Now we see cell A successfully ‘grow’ into present grid and has its duplicate cell B. Note that when B is generated, aforementioned placement rules will be applied according to B’s type and position.
This equation helps our program to judge whether or not an adjacent cell can grow into present grid in i_k-th iteration; after this judgement is settled, we choose randomly from surrounding grids that have cells in them, supposing we select cell A, and inherit its cell type to get clone cell B in present grid. Now we see cell A successfully ‘grow’ into present grid and has its duplicate cell B. Note that when B is generated, aforementioned placement rules will be applied according to B’s type and position.
Probabilistic growth
References
[1] https://en.wikipedia.org/wiki/Cellular_automaton
[2] Cao Y, Ryser M D, Payne S, et al. Collective space sensing coordinates pattern scaling in engineered bacteria[J]. Cell, 2016, 165(3):620.
Payne S, Li B, Cao Y, et al. Temporal control of self-organized pattern formation without morphogen gradients in bacteria.[J]. Molecular Systems Biology, 2013, 9(1):697.
back to the top
[2] Cao Y, Ryser M D, Payne S, et al. Collective space sensing coordinates pattern scaling in engineered bacteria[J]. Cell, 2016, 165(3):620.
Payne S, Li B, Cao Y, et al. Temporal control of self-organized pattern formation without morphogen gradients in bacteria.[J]. Molecular Systems Biology, 2013, 9(1):697.
back to the top
