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