Cellular Automata in Computational Biology

Johannes Textor
Department of Tumor Immunology
Nijmegen, The Netherlands

Content

Cellular automata (CAs) are very important tools for computational biology. The CAs we use in practice are often more complex than basic CAs:

• Probabilistic instead of deterministic update;
• Asynchronous instead of synchronous update;
• Global instead of purely local information.

This lecture explains these extensions and gives practical examples.

A very simple infection model:

• The grid represents a 2D landscape.
• Pixels can be infected (red) or healthy (white).
• Update rule: white pixels adjacent to red pixels become red.

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?

Probabilistic Cellular Automata

deterministic

stochastic

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

A Probabilistic Model of Infection Spread

The SIR model: individuals can be

• Susceptible
(= healthy, but at risk of infection)
• Infected
• Resistant
(= healthy, and immune to infection)

Question
How would you convert the SIR model into a cellular automaton?

The SIR Model as a Cellular Automaton

Grid and states:

• Each pixel is an individual.
• States: susceptible, infected, resistant.

Rules:

• Susceptible individuals are infected with a probability depending on #infected neighbors.
• Infected individual become resistant at a fixed chance pcure (recovery rate). This process is independent of the neighbourhood.

Exercises

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

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.

Asynchronous Grid Update in Potts Models

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:

The Cellular Potts Model

Pixels with the same state $\tau$ form a cell.
We introduce a volume term

$${\cal H} = J \sum_{(i,j)} \delta ( s_i, s_j ) + \color{red}{\sum_{\tau}\lambda_\tau ( |\{i \mid \sigma_i=\tau\}|-v_\tau )^2}$$

We obtain cells containing different numbers of pixels.

Cells move only randomly (Brownian motion).

Graner & Glazier, Phys Rev Lett 1992

The Perimeter Constraint

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.

Summary Cellular Potts Model (CPM)

Pixels belong to cells, which
move by copying pixels:

Copy success chance (Pcopy) is higher when it helps the cell:

 Stay together: Maintain its size: Maintain its membrane: ↘ ↓ ↘

Migration: The Act Model

maxact

Cells move if we add positive feedback on protrusive activity
($\approx$ actin polymerization)1:

Parameters:
λact ≈ protrusive force
1Niculescu et al. PLoS Computational Biology, 2015.

Summary

• CAs are widely used to build simulation models in computational biology.
• For realistic applications, it is often necessary to modify/relax the basic CA rules.
Try it yourself
Go to computational-immunology.org/cpm/, and experiment with the Cellular Potts Model.