Difference between revisions of "Team:KU Leuven/Modeling/Hybrid"
Line 619: | Line 619: | ||
<p> | <p> | ||
<b>Nearest-neightbor Algorithm</b><br/> | <b>Nearest-neightbor Algorithm</b><br/> | ||
− | The cell-cell interactions have already been fully described in the paragraphs above. However, solving the equation of motion of an agent in its current form requires the computation of the force due to every other agent. If we take N to be the number of agents, that means $N*(N-1)$ amount of force computations are needed in total and therefore the computation time grows as $O(N²)$. To put this in perspective, if we simulate a thousand agents, the amount of interactions adds up to around one million. This puts a heavy computational load on the model which can be reduced greatly by using a smarter algorithm. The crucial observation here is that the force goes to zero when the distance between two cells is larger than $2\cdot | + | The cell-cell interactions have already been fully described in the paragraphs above. However, solving the equation of motion of an agent in its current form requires the computation of the force due to every other agent. If we take N to be the number of agents, that means $N*(N-1)$ amount of force computations are needed in total and therefore the computation time grows as $O(N²)$. To put this in perspective, if we simulate a thousand agents, the amount of interactions adds up to around one million. This puts a heavy computational load on the model which can be reduced greatly by using a smarter algorithm. The crucial observation here is that the force goes to zero when the distance between two cells is larger than $2\cdot r_{cutoff}$. An agent therefore only interacts with its nearest neighbors, meaning that the naive implementation wastes a lot of time computing interactions which have no effect anyways. Moreover, as the simulation progresses, an agent’s neighbors do not vary greatly from one timestep to another. A more efficient approach then consists of periodically searching for the nearest neighbors within a fixed radius, storing them in a list for every agent and updating their coordinates for all intermediate timesteps. |
Since the agents are programmed to repel each other when they approach each other too closely, they will evolve to a rather uniform distribution. The most appropriate fixed-radius nearest neighbor search algorithm in that case is the cell technique. In this algorithm, the agents are structured by placing a rectangular grid of cells over the domain and assigning every agent to a cell (fig9). Determining which cell an agent belongs to is easily done by rounding down the x and y-coordinates to the nearest multiple of the grid spacing. If the grid spacing is chosen so that interactions do not reach further than adjacent cells, every agent only needs to look for neighbors in 9 cells (its own cells plus 8 adjacent cells) instead of the entire domain. | Since the agents are programmed to repel each other when they approach each other too closely, they will evolve to a rather uniform distribution. The most appropriate fixed-radius nearest neighbor search algorithm in that case is the cell technique. In this algorithm, the agents are structured by placing a rectangular grid of cells over the domain and assigning every agent to a cell (fig9). Determining which cell an agent belongs to is easily done by rounding down the x and y-coordinates to the nearest multiple of the grid spacing. If the grid spacing is chosen so that interactions do not reach further than adjacent cells, every agent only needs to look for neighbors in 9 cells (its own cells plus 8 adjacent cells) instead of the entire domain. |
Revision as of 00:05, 19 September 2015
The hybrid model
The hybrid model represents an intermediate level of detail in between the colony level model and the internal model. Bacteria are treated as individual agents that behave according to the Keller-Segel type discretized stochastic differential equations, while chemical species are modeled using partial differential equations.
Model Description
Implementation
1-D Hybrid Model
The video box above shows one dimensional simulation results for the hybrid model. A constant speed and random step simulation has been computed. We observe that the bacteria form a traveling wave in both cases, which is essential for pattern formation. These results are also similar to what we get from the continuous model, which confirms our results.
2-D Hybrid Model
The videos above show simulation videos computed at the Flemish supercomputing center, for three different initial conditions similar to the ones we used for the colony level model. The first and second condition start from 9 mixed or 5 colonies of both cell types, arranged in a block or star shape. These first two gradually separate in a manner similar to what we would we also saw in the colony level model. The result for random initial data is fundamentally different. As the agent based approach allows for better implementation of adhesion large cell type A bands form. The AHL and Leucine produced by the type A bacteria causes the B type cells to move away leading to a pattern which we could not produce using PDEs alone, this beautifully illustrates the added value of hybrid modeling.
Incorporation of internal model
Up until now, we have largely ignored the inner life of the bacteria. This inner life consists of transcriptional networks and protein kinetics. Instead we assumed that AHL and leucine production is directly proportional to the density of type A cells. This only works in theory, since bacteria will be affected by their surroundings and the way their dynamics react to it. For example bacteria surrounded by a large concentration of AHL, will have more CheZ and will react more on the presence of Leucine. Also bacteria have different histories and will have different levels of transcription factors and different levels of proteins in their plasma. The proteins are not directly degraded and will still be present in the cytoplasm of the bacteria long after the network has been deactivated. From this, it is clear that 2 bacteria, although surrounded by the same AHL and leucine concentrations, can show different behavior and reaction kinetics.
This results in a heterogeneity of the bacterial population that has not yet been accounted for. To make up for this anomaly, we decided to add an internal model to every agent. This way we will get more realistic simulations. Every agent will get their own levels of CheZ, LuxR, LuxI and so on and will have individual reactions on their surroundings. We hope that this way we can get closer to the behavior of real bacteria.
References
[1] | Benjamin Franz and Radek Erban. Hybrid modelling of individual movement and collective behaviour. Lecture Notes in Mathematics, 2071:129-157, 2013. [ .pdf ] |
[2] | Zaiyi Guo, Peter M A Sloot, and Joc Cing Tay. A hybrid agent-based approach for modeling microbiological systems. Journal of Theoretical Biology, 255(2):163-175, 2008. [ DOI ] |
[3] | E F Keller and L A Segel. Traveling bands of chemotactic bacteria: a theoretical analysis. Journal of theoretical biology, 30(2):235-248, 1971. [ DOI ] |
[4] | E. M. Purcell. Life at low Reynolds number, 1977. [ DOI ] |
[5] | Angela Stevens. The Derivation of Chemotaxis Equations as Limit Dynamics of Moderately Interacting Stochastic Many-Particle Systems, 2000. [ DOI ] |
Equations
Contact
Address: Celestijnenlaan 200G room 00.08 - 3001 Heverlee
Telephone: +32(0)16 32 73 19
Email: igem@chem.kuleuven.be