Transcript Infected

Cellular Automata: Some
Applications in Detail
This is lecture 16 of Biologically Inspired Computing
Flu material from Beauchemin et al, JTB, 2005 – thanks to John Owen for bringing my attention to it.
Some additional things about CAs
A simple 2D CA to illustrate these points:
States 0 and 1:
Wraparound 2D array of 30 cells
Rules: if both neighbours are 1, become 1;
if both neighbours are 0, become 0;
otherwise, stay the same.
Synchronous update: most CAs operate this way. Each cell’s new
state for time t+1 is worked out in parallel based on the situation at t.
Start:
101001010001101000101010010001
T=1 :
T=2 :
110000000001110000010100000001
110000000001110000001000000001
Some additional things about CAs
Asynchronous update:
Sometimes applied in preference – it is arguably a more valid way
to simulate some systems. Here, at each time step, one cell is
chosen at random and updated.
Start:
T=1 :
T=2 :
T=3 :
T=4 :
T=5 :
101001010001101000101010010001
101001000001101000101010010001
101001000001101000101010010001
111001000001101000101010010001
111001000001101000101010000001
etc ...
Clearly if there are n cells, then n timesteps in an asynchronous CA
corresponds to the 1 timestep of a synchronous CA.
Boundary conditions
Rules for a cell’s state transitions are usually defined in terms of
the cell’s neighbourhood. E.g. this is the Moore neighbourhood:
But what about cells on the edge?
The common approach in 2D is to
treat the CA surface as a Toroid
This just means wraparound in
the way indicated by the
blue and green neighbourhoods
illustrated
The Flu
•
Influenza, in humans, is caused by a virus that infects the upper
respiratory tract, nose and throat, and sometimes the lungs
•
Annual epidemics affect 5—15% of the world’s population,
causing around 250,000—500,000 deaths.
•
There are three different types, A, B and C, and further division
among the types.
•
Influenza A has two subtypes, which are the most important for
humans: A(H3N2) and A(H1N1) – the H and N refer to different
molecules on the surface of the virus, and the numbers indicate
variants of these.
Images from the wikipedia article
The virus particle (virion) enters the healthy cell, which is the infected.
The virus then tricks the cell into expressing the viral proteins, so that
many copies of the virus become made in the cell. Soon the cell becomes
infectious, and eventually it just dies from overcrowding of virus copies.
Defense against it
• Our immune system normally manages to evolve a response
that recognises the H molecule, which then gets destroyed by
our white blood cells.
• But, the flu is very good at mutation and keeps coming back
with new strains, corresponding to new variations on the H
and N variants that we have not yet developed resistance to.
• When a strain emerges that has a major change in its H
molecule, this tends to cause a global pandemic – has
happened 3 times in the last century.
Modelling Influenza A
It is useful to model Flu A (or any other disease) for many reasons:
• Better understanding leads to better ways to treat and control it.
• When the model seems to work (reflect reality), we can do some research with
it that may lead to useful new treatments.
• If the model doesn’t work, then we know that our understanding of the disease
is flawed, so this guides further in vivo/in vitro research that needs to be done
towards improving our understanding (and our model).
• Modelling of most diseases is traditionally done using differential equations,
but:
CAs are now beginning to show that they produce more useful and accurate
models.
Which is good, because it means that we don’t have to leave saving-theworld to mathematicians.
Beauchemon et al’s CA/Flu model
Two types of cell in the model:
• epithelial cells (the ones that flu infects)
• immune system cells (that try to attack and destroy infected cells)
Simplifications in the model:
• the infection spreads directly from one infected cell to another (virus
particles themselves are not part of the CA model)
• 2 Dimensional CA (is this too much of a simplification?)
• Each position in the CA grid represents an epithelial cell. Immune
system cells are mobile over the grid and vary in number.
• It is updated synchronously.
•The Moore neighbourhood is used, the grid is toroidal.
States and Rules
Epithelial cells can be:
• Healthy; Infected ; Expressing ; Infectious ; Dead
Transition rules:
• An epithelial cell becomes Dead when it is older than CELL_LIFESPAN
• A Healthy epithelial cell becomes Infected with probability
INN * INFECT_RATE/8
where INN is the number of infectious cells in its neighbourhood
• An Infected cell becomes Expressing after EXPRESS_DELAY timesteps
• An Expressing cell becomes Infectious after it has been infected for
INFECT_DELAY timesteps.
• Infected, Expressing and Infectious cells become dead after being infected
for INFECT_LIFESPAN
• Expressing and Infected cells become dead after they have been recognised
by an immune cell.
• A Dead cell is replaced by a new Healthy cell with probability
#Healthy / ( #Dead x DIVISION_TIME)
The new healthy cell may immediately be Infected according to 2nd rule above.
The Immune Cells
At the start
each epithelial cell has a random age between 0 and CELL_LIFESPAN
a fraction INFECT_INIT are set to Infected, the rest are Healthy
Meanwhile, Immune cells have two states: Virgin, and Mature
• Virgin: an immune cell that has not encountered the virus before,
so it does not recognise it, and therefore does not attack it.
• Mature: an immune cell that could attack an infected cell.
At the start, BASE_IMM_CELL immune cells are placed at random
on the lattice, all Virgin
The Immune Cell Rules
• At each timestep, each immune cell moves to a random
neighbouring cell.
• An immune cell is removed when it reaches IMM_LIFESPAN
• A Virgin immune cell becomes Mature if the epithelial cell at its
site is Expressing or Infectious.
• A Mature immune cell occupying the site of an Expressing or
Infectious epithelial cell recognises it, and causes it to become Dead.
• When a recognition occurs, as above, a number RECRUITMENT
of Mature immune cells are added at random site locations after
RECRUIT_DELAY timesteps (this models the immune system
response)
• If at any timestep there are fewer than BASED_IMM_CELL Virgin
immune cells on the lattice, new ones are added at random locations
to make up the numbers.
What is known
Beauchemon et al wanted to compare their CA model with a more
complex model based on Differential Equations. Parameters and
observations gleaned from real cases offered the following data to
evaluate the models:
•The infection should peak on day 2 (after 48 hrs (timesteps))
•The fraction of dead epithelial cells should be:
• 10% at 24h, 40% at 48hr, 10% at 120hr
•Virus level should decline to `inoculation level’ on day 6.
•The number of immune cells should peak anywhere between
days 2 and 7.
Using biologically plausible parameters, the behaviour was as shown
next:
Solid line: dead
Dashed line: healthy
Dotted line: infected
Dot-dash: immune cells per healthy cell
Infection should peak on day 2
Solid line gets 2 out of 3
Virus long gone by day 6
Immune peak
seems in right
place
Conclusions/discussion
The paper goes on to see the effect of varying many of the parameters
within biologically realistic ranges. But the main things to note are:
• the model seems to have a good qualitative fit to the cell dynamics
of the natural infection.
• the fit is not perfect, but there are plausible explanations that
suggest improvements to the model. E.g. the infection dies away too
quickly, however this is because the model leaves out the initial
`nonspecific’ immune response.
• the DE model is a better fit in some respects and worse in others –
but it is a much richer model (including different types of immune
cells) – in fact the CA model has 12 parameters, and the DE model
has 60 parameters. This suggests the CA is the better approach.
Modelling brain tumour growth
Kansal et al, 2000, Journal of Theoretical Biology
Incidence of primary malignant brain tumours is 8/100,000 p.a.
3D CA, modelling brain tumour growth
Shows that Macroscopic tumour behaviour can be predicted via
microscopic parameters
Uses only 4 parameters
Makes predictions that match the biological reality
MRI scan showing a
tumour; the white area
Represents blood leakage
around the tumour
Kansal et al use the Delaunay Tesselation as their lattice – on the right
we see blackened cells representing the tumour, in a simplified 2D version
States and Rules
Not easy to glean from the
paper, but: cells are either
healthy (empty lattice site)
or tumour.
Tumour cells are either
proliferative (they divide
into additional tumour
cells) or not. When a
proliferative tumour cell
wants to divide, it fills a
healthy space with a new
tumour cell if it can find
one within delta_p of its
position. If it can’t find
one, it becomes nonproliferative.
1.5M lattice sites
Initial tumour is 1000 proliferative cells at centre of lattice
Result seems realistic
Very good fit to real data;
The lines are the CA model predictions of tumour radius and
volume against time
The plotted points are measurements from real cases of untreated tumours
Read a couple more applications
for yourself.
See the www site for the:
Influenza CA paper
Tumour CA paper
A Traffic Simulation CA paper
Historic urban growth in the San Francisco bay area CA
Not examinable reading, but recommended