Johannes Textor
Department of Tumor Immunology
Radboudumc
Nijmegen, The Netherlands
Cellular automata (CAs) are very important tools for computational biology. The CAs we use in practice are often more complex than basic CAs:
This lecture explains these extensions and gives practical examples.
A very simple infection model:
Question | |
---|---|
How will the infection spread starting from a single pixel in the middle? Is that realistic? Can you think of some way to improve this model? |
You might argue that pixels with more infected
(red) neighbors are more likely
to become infected, so let's change our rule:
→ chance of becoming red = # red neighbors x 10%
Definition |
---|
We call a CA deterministic if the same starting configuration always leads to the same result. Otherwise, we call it probabilistic. |
. |
The SIR model: individuals can be
Question | |
---|---|
How would you convert the SIR model into a cellular automaton? |
Grid and states:
Rules:
Try it yourself |
---|
Go to computational-immunology.org/sir/, and use the SIR model. Try to find parameters where the infection becomes epidemic or fizzles out. |
The Potts model is a graph (grid) ${\cal G}=(V,E)$ with node states $\sigma_V$ and an associated energy function $$ {\cal H} = J \sum_{\{i,j\} \in E} \delta ( \sigma_i, \sigma_j ) \ . $$
${\cal H}=32J$ | ${\cal H}=20J$ |
The goal is to minimize the energy function.
Metropolis-Algorithm:
Randomly choose a source pixel and a neigbouring target.
Copy source to target state with
probability
$$P(\Delta{\cal H},T) = \begin{cases}
1 & \Delta{\cal H} < 0, \\
e^{-\Delta{\cal H}}/T & \text{else.}
\end{cases}$$
$P=1$ | $P=e^{-6J/T}$ |
T:
Pixels with the same state $\tau$ form a cell.
We introduce a volume term
We obtain cells containing different numbers of pixels.
Cells move only randomly (Brownian motion).
Graner & Glazier, Phys Rev Lett 1992
In the basic Potts model, cells tend to be round. To change this, we introduce a perimeter term
$$ {\cal H}_P = \sum_{\tau}\lambda_\tau ( |\{(i,j) \in E \mid \tau=\sigma_i\neq\sigma_j\}|-p_\tau )^2 $$We obtain cells with different shapes.
Pixels belong to cells, which
move by copying pixels:
Copy success chance (P_{copy}) is higher when it helps the cell:
Stay together: | Maintain its size: | Maintain its membrane: |
↘ | ↓ | ↘ |
Cells move if we add positive feedback
on protrusive activity
($\approx$ actin polymerization)^{1}:
Try it yourself |
---|
Go to computational-immunology.org/cpm/, and experiment with the Cellular Potts Model. |