IV121: Computer science applications in
biology
Qualitative Models in Biology
David ˇSafr´anek
March 5, 2012
What is discrete? What does discrete mean?
ˆ think of you communicating with your friends today
ˆ how many interactions have you noticed?
ˆ each one caused you a discrete event
ˆ think of flies flying in the room
ˆ what interactions they have with each other?
ˆ what interactions they have with the room walls?
ˆ each one is a discrete event
ˆ think of molecules in a solution or in a cell . . .
Is there something what is not discrete?
ˆ think of movement around you
ˆ think of you moving
ˆ think of time passing
ˆ think of current in the power supply
ˆ electron flow through or around the wire material
ˆ is it discrete or continous?
A way to understand the world...
ˆ to understand (and capture) things happening around us we
developed a modeling framework
ˆ discrete-time dynamics models
ˆ music “modeled” on CD
ˆ video clips filmed by your camera
ˆ . . .
ˆ continuous-time dynamics models
ˆ mathematical model describing the flow of electrons in an
electrical circuit
ˆ models of chemical reaction dynamics
ˆ . . .
ˆ discrete-event models
ˆ model of a coffey machine
ˆ model of an elevator
ˆ models of chemical reaction dynamics
ˆ mixed models – e.g., hybrid systems ...
A way to understand the world...
ˆ to understand (and capture) things happening around us we
developed a modeling framework
ˆ discrete-time dynamics models
ˆ music “modeled” on CD
ˆ video clips filmed by your camera
ˆ . . .
ˆ continuous-time dynamics models
ˆ mathematical model describing the flow of electrons in an
electrical circuit
ˆ models of chemical reaction dynamics
ˆ . . .
ˆ discrete-event models
ˆ model of a coffey machine
ˆ model of an elevator
ˆ models of chemical reaction dynamics
ˆ mixed models – e.g., hybrid systems ...
A way to understand the world...
B.P. Zeigler, H. Praehofer, T. Gon Kim. Theory of Modeling and Simulation: Integrating Discrete Event
and Continuous Complex Dynamic Systems. Academic Press, 2000.
A way to understand the world...
Time scales
ˆ think of a lightning causing a fire
ˆ very fast electron flow → long-lasting fire
ˆ one of the views: a discrete event (lightning) changing the
continuous world
ˆ is this a reasonable simplification?
ˆ when modeling the world we have to abstract
ˆ our abstract views (models) can make a hierarchy
ˆ a drawback of simplifications: there can be feedbacks we
silently omit ...
Time scales in a cell
Quantitative parameters Values in E.Coli
cell size 1µm3
number of protein molecules in a cell 4 · 106
size of a protein molecule 5nm
concentration of a particular protein in a cell 1nM
amount of proteins in a cell 18%
time of protein diffusion 0, 1s
time of other molecules diffusion 1msec
number of genes 4500
A way to understand the world...
Abstractions
ˆ abstraction of time
ˆ think of ticks of the clock. . .
ˆ continuous-time domain sampled into the discrete-time domain
ˆ a single discrete time-step can abstract some notion of time
ˆ one generation of bacteria population
ˆ time abstracted to day/night phases or a.m./p.m.
ˆ the lowest time observed between any two event occurrences
ˆ abstraction of quantities
ˆ large (possibly real) valued amounts abstracted by several
discrete levels (e.g., light intensity, temperature, . . . )
ˆ large valued amounts abstracted by real values (e.g.,
concentration of molecules in a cell of particular volume)
ˆ abstraction of behaviour
ˆ neglecting some aspects (e.g., competitivness in transcription
factors-to-DNA binding)
ˆ theoretical constraints (e.g., well-stirred solutions, fixed
conditions – temperature, pressure)
A way to understand the world...
Abstractions
ˆ in computer science abstraction is a formal notion:
ˆ identify what you add and what you lose by abstracting
ˆ when doing models of life we use approximative abstractions
ˆ what is lost and what is added?
ˆ note that abstractions between continuous and discrete views
can be bidirectional
A way to understand the world...
Using computers
ˆ computation by computers is purely discrete
ˆ quantities are stored in discrete memory
ˆ memory has limited size
ˆ computer-scientific abstractions are employed to automatically
(technically) reduce the computational efforts
Systems View of the World
ˆ systems models of the world (e.g., a living cell, a population)
ˆ syntax of the systems model is a network:
ˆ components (nodes) – e.g. chemical substances
ˆ interactions (edges) – e.g. chemical reactions
ˆ each component is assigned some quantity
ˆ discrete or continuous: number of particles, concentration
ˆ can be visualized by color intensity of a node
ˆ dynamics is animation of colour intensity changing on nodes
in time
ˆ driven by global rules (e.g., mass-action reactions)
Systems View of a Cell: Biological Networks
ˆ identify substances (macromolecules, ligands, proteins, genes, . . . )
ˆ identify interactions ((de)complexation, (de)phosphorylation, . . . )
Systems Biology of a Cell
Biological Networks and Pathways
ˆ what is the “right” meaning?
ˆ in order to analyse we need to formalise a bit. . .
Graphical Specification in SBGN
Systems Biology Graphical Notation
ˆ PD: biochemical interaction level (the most concrete)
ˆ ER: relations among components and interactions
ˆ AF: abstraction to mutual interaction among activities
Graphical Specification in SBGN
Systems Biology Graphical Notation
ˆ SBGN.org iniciative (from 2008)
ˆ standard notation for biological processes
ˆ http://sbgn.org
ˆ Nature Biotechnology (doi:10.1038/nbt.1558, 08/2009)
ˆ three sub-languages:
ˆ SBGN PD (Process Description)
(doi:10.1038/npre.2009.3721.1)
ˆ SBGN ER (Entity Relationship)
(doi:10.1038/npre.2009.3719.1)
ˆ SBGN AF (Activity Flow) (doi:10.1038/npre.2009.3724.1)
ˆ tool support:
ˆ SBGN PD supported by CellDesigner
ˆ SBGN-ED (http://www.sbgn-ed.org)
Kinase Cascade in CellDesigner (SBGN)
From Systems Structure to Systems Dynamics
Discrete Events View
ˆ once the systems structure is captured we want to animate . . .
ˆ each node in SBGN PD represents some quantity of a
particular species
ˆ species are assumed to be well stirred in the cell
ˆ interactions are events affecting related species (in amounts
given by stoichiometry)
ˆ abstract from time (no information when the event occurred,
events last zero time)
ˆ abstract from space (no information where the event occurred)
ˆ purely qualitative model of systems dynamics
Qualitative Model of a Reaction
AB → A + B
ˆ state configuration captures number of molecules:
#[AB], #[A], #[B]
ˆ global rule:
ˆ one molecule AB is removed from the solution
ˆ one molecule A is added to the solution
ˆ one molecule B is added to the solution
#[AB](t + 1) = #[AB](t) − 1
#[A](t + 1) = #[A](t) + 1
#[B](t + 1) = #[B](t) + 1
Example
Consider reaction: A → B
A B
5
0
Example
Consider reaction: A → B
A B
5
0
→
4
1
Example
Consider reaction: A → B
A B
5
0
→
4
1
→
3
2
Example
Consider reaction: A → B
A B
5
0
→
4
1
→
3
2
→
2
3
Example
Consider reaction: A → B
A B
5
0
→
4
1
→
3
2
→
2
3
→
1
4
Example
Consider reaction: A → B
A B
5
0
→
4
1
→
3
2
→
2
3
→
1
4
→
0
5
Example
Consider three reactions:
A → B
A + B → AB
AB → A + B
ˆ state configuration has the form #A, #B, #AB
ˆ consider, e.g., configuration 2, 2, 1
⇒ what is the next configuration?
ˆ reactions run in parallel . . .
Petri Nets – A Discrete Model of Chemichal World
Adam Carl
Petri
1926–2010
ˆ formal model for concurrent systems
ˆ used for general modeling and simulation
ˆ many simulation and analysis tools
ˆ various semantics
ˆ unambiguous system representation
2H2 + O2 → 2H2O
Petri Nets – A Discrete Model of Chemichal World
Adam Carl
Petri
1926–2010
ˆ formal model for concurrent systems
ˆ used for general modeling and simulation
ˆ many simulation and analysis tools
ˆ various semantics
ˆ unambiguous system representation
2H2 + O2 → 2H2O
Petri Nets – A Discrete Model of Chemichal World
Adam Carl
Petri
1926–2010
ˆ formal model for concurrent systems
ˆ used for general modeling and simulation
ˆ many simulation and analysis tools
ˆ various semantics
ˆ unambiguous system representation
2H2 + O2 → 2H2O
Petri Nets – A Discrete Model of Chemichal World
Adam Carl
Petri
1926–2010
ˆ formal model for concurrent systems
ˆ used for general modeling and simulation
ˆ many simulation and analysis tools
ˆ various semantics
ˆ unambiguous system representation
2H2 + O2 → 2H2O
Petri Net Representation of Biological Networks
Petri Net Representation of Biological Networks
Petri Net Representation of Biological Networks
ˆ visually infeasible but unambiguous, formal, and still graphical
Petri Net Representation of Biological Networks
Kinase Cascade in MAPK/ERK Signalling Network
Petri Net Representation of Biological Networks
Kinase Cascade in MAPK/ERK Signalling Network
Petri Net Analysis Framework
quantitative parameters ignored
quantitative parameters required
continuous model
qualitative model
stochastic model
variables
continuous
abstracted
modeled
time
discrete
approximation
abstraction abstraction
Petri Net Analysis Framework
continuous model
qualitative model
stochastic model
variables
continuous
abstracted
modeled
time
discrete
Monte Carlo simulation
Static analysis
Behavioral analysis
Simulation analysis
Steady state analysis
Numerical simulation
Simulation analysis
approximation
abstraction abstraction
Petri Net Structure
(Place/Transition) Petri net is a quadruple N = S, R, f , m(0) where
ˆ S finite set of places (substances),
ˆ T finite set of transitions (reactions),
ˆ f : ((P × T) ∪ (T × P)) → N0 set of weighted edges,
ˆ x• = {y ∈ S ∪ R | f (x, y) = 0} denotes target of x
ˆ •x = {y ∈ S ∪ R | f (y, x) = 0} denotes source of x
ˆ weight represents stoichiometric coefficients
ˆ m(0) : S → N0 is initial marking (initial condition).
Petri Net Dynamics
Each place s ∈ S is marked by a value in N0 (representing number
of molecules of the respective species):
ˆ in Petri net terminology the state configuration (configuration
of places) is called marking: m : S → N0
ˆ marking is represented as an n-dimensional vector m ∈ Nn
0
Dynamics of each transition r ∈ R is the following:
ˆ a transition r ∈ R must be enabled iff ∀s ∈ •r. m(s) ≥ f (s, r)
ˆ enabled transition can be fired, causing an update of related
places (marking m is updated to marking m ):
∀s ∈ S. m (s) = m(s) − f (r, s) − f (s, r)
Static Analysis
Matrix Representation
ˆ Petri Net can be represented by incidence matrix
M : S × R → Z defined as follows:
M(s, r) = f (r, s) − f (s, r)
ˆ equivalent to stoichiometric matrix
Note: If reversible reactions are considered, forward and backward matrices must be
distinguished.
M =




−1 1 1
−1 0 1
1 −1 −1
0 1 0




species indices: s1...E, s2...S, s3...ES, s4...P
reaction indices: r1 : E + S → ES, r2 : ES → E + S, r3 : ES → P + E
Static Analysis
Invariant Analysis – P-invariants
ˆ species vector x is called P-invariant iff
xM = 0
ˆ characteristic property of P-invariant x:
∀r ∈ R.
n
i=1
M(i, r)xi = 0
ˆ Petri Net terminology translates the P-invariant property to:
∀r ∈ R.
s∈•r
xs =
s∈r•
xs
ˆ interpretation: conserved mass
Static Analysis
Invariant Analysis – P-invariants
E + S ↔ ES → P + E
species indices: s1...E, s2...S, s3...ES, s4...P
ˆ minimal P-invariants:
ˆ (1, 0, 1, 0): mE + mES = const.
ˆ (0, 1, 1, 1): mS + mES + mP = const.
ˆ minimal P-invariants make the basis of M left-null space
ˆ non-minimal P-invariant example:
ˆ (1, 1, 2, 1): mE + mS + 2mES + mP = const.
Static Analysis
Invariant Analysis – T-invariants
ˆ species vector y is called T-invariant iff
My = 0
ˆ characteristic property of T-invariant y:
∀s ∈ S.
|R|
j=1
M(s, j)yj = 0
ˆ Petri Net terminology translates the T-invariant property to:
∀s ∈ S.
r∈•s
yr =
r∈s•
yr
ˆ interpretation: stable flux mode
Static Analysis
Invariant Analysis – T-invariants
r1
r2
r5
r6r4
r3
S
E
EP
P
ES
E + S ↔ ES ↔ EP ↔ P + E
ˆ minimal T-invariants:
ˆ (1, 1, 0, 0, 0, 0): r1; r2 (trivial – reversibility)
ˆ (0, 0, 1, 1, 0, 0): r3; r4 (trivial – reversibility)
ˆ (0, 0, 0, 0, 1, 1): r5; r6 (trivial – reversibility)
ˆ minimal T-invariants make the basis of M null space
ˆ non-minimal (and non-trivial) T-invariant example:
ˆ (1, 1, 1, 1, 1, 1): r1; r2; r3; r4; r5; r6
ˆ this T-invariant represents significant input/output behaviour
of the network (S −→ P)
Static Analysis
Initial Marking Construction
ˆ what species have to be set with non-zero concentration
initially?
ˆ follow the following rules:
ˆ each P-invariant contains at least one non-zero species
ˆ each non-trivial T-invariant is realizable
ˆ there is only minimal number of species set non-zero
ˆ in each P-invariant choose non-zero the least active species (or
monomer)
Static Analysis
Initial Marking Construction Example
r1
r2
r5
r6r4
r3
S
E
EP
P
ES
E + S ↔ ES ↔ EP ↔ P + E
indexace: s1...E, s2...S, s3...ES, s4...P, s5...EP
ˆ P-invariants: (1, 0, 1, 0, 1), (0, 1, 1, 1, 1)
ˆ T-invariants: (1, 1, 0, 0, 0, 0), (0, 0, 1, 1, 0, 0), (0, 0, 0, 0, 1, 1)
ˆ initial marking (m0) construction:
ˆ set non-zero one in {E, ES, EP} and one in {S, ES, P, EP}
ˆ choose E and S (monomers)
ˆ non-trivial T-invariant (1, 1, 1, 1, 1) is realizable in m0:
reaction sequence r1; r3; r5; r6; r4; r2
Static Analysis
Initial Marking Construction Example
r1
r2
r5
r6r4
r3
S
E
EP
P
ES
E + S ↔ ES ↔ EP ↔ P + E
indexace: s1...E, s2...S, s3...ES, s4...P, s5...EP
ˆ P-invariants: (1, 0, 1, 0, 1), (0, 1, 1, 1, 1)
ˆ T-invariants: (1, 1, 0, 0, 0, 0), (0, 0, 1, 1, 0, 0), (0, 0, 0, 0, 1, 1)
ˆ initial marking (m0) construction:
ˆ set non-zero one in {E, ES, EP} and one in {S, ES, P, EP}
ˆ choose E and S (monomers)
ˆ non-trivial T-invariant (1, 1, 1, 1, 1) is realizable in m0:
reaction sequence r1; r3; r5; r6; r4; r2
Qualitative Behavioral Properties
ˆ boundedness
ˆ no species concentration expands indefinitely
ˆ can be decided statically (P-invariant coverability)
ˆ liveness
ˆ weak form – always at least one reaction is working
– can be decided statically in some cases
ˆ strong form – every reaction is always eventually working
– can be decided statically in some cases (T-invariant
coverability)
ˆ reversibility
ˆ reversible process (each flux mode keeps realizing)
ˆ can be decided only by dynamical analysis
ˆ dynamic properties independent of time and quantity
Qualitative Behavioral Properties
Example Michaelis Menten Reversible
r1
r2
r5
r6r4
r3
S
E
EP
P
ES
ˆ bounded, strongly live, reversible
ˆ S and E is never finaly consumed (marked zero)
ˆ P finally marked non-zero
Qualitative Behavioral Properties
Example Michaelis Menten Kinetics
ˆ bounded, not live, not reversible
ˆ S finally consumed
ˆ E consumed but recovered finally
Qualitative Behavioral Properties
Example MAPK/ERK pathway
ˆ bounded, strongly live, reversible
ˆ dephosphorylations at higher cascade
level independent on phosphorylations
at lower level
Petri Net Representation
Example of complex signalling network
Tool Support
ˆ format transformation and editing
ˆ Snoopy – visual editing, SBML export/import, Petri net
variants transformation
ˆ PIPE – visual editing
ˆ static analysis
ˆ Charlie (Petri Net invariant analysis)
ˆ also can be used: Matlab/Octave (stoichiometric analysis)
ˆ qualitative behavioral analysis
ˆ Charlie (liveness, boundedness, and more ...)
ˆ MARCIE (qualitative dynamics analysis)
ˆ Petri Net simulation
ˆ Snoopy – simulation of qualitative and stochastic nets
ˆ Cell Illustrator – proffesional tool, hybrid semantics
Literature
M. Heiner & D. Gilbert. How Might Petri Nets Enhance Your
Systems Biology Toolkit. Petri Nets 2011: 17-37
M. Heiner, D. Gilbert & R. Donaldson. Petri Nets for Systems
and Synthetic Biology. SFM 2008: 215-264
Koch, I., Reisig, W. & Schreiber, F. Modeling in Systems
Biology: The Petri Net Approach. Computational Biology, Vol.
16, Springer-Verlag, 2011.
Pinney, J.W., Westhead, D.R. & McConkey, G.A. Petri Net
representations in systems biology. Biochem Soc Trans. 2003
Dec;31(Pt 6):1513-5.
Reddy, V.N., Mavrovouniotis M.L.& Liebman M.N. Petri net
representation in metabolic pathways. Proc Int Conf Intell Syst
Mol Biol 1993, 328-336.
Regulatory Networks of Cellular Processes
ˆ identify substances (proteins, genes)
ˆ identify interactions (transcriptory activation, repression – do we
know reactions behind?)
Example of a gene regulatory network
rrnP1 P2
CRP
crp
cya
CYA
cAMP•CRP
FIS
TopA
topA
GyrAB
P1­P4
P1 P2
P2P1­P’1
P
gyrABP
Signal (lack of carbon source)
DNA 
supercoiling
fis
tRNA
rRNA
protein
gene
promoter
Gene regulatory network of E. Coli
Identification of regulatory dynamics
ˆ systems measurement of transcriptome (mRNA
concentration) is imprecise and discrete!
ˆ interactions can be partially identified by analysis of
transcriptor factor binding sites (e.g., TRANSFAC)
ˆ microarray experiments can be reversed engineered
Identification of regulatory dynamics
Identification of regulatory dynamics
Boolean and Bayesian networks
crp(t + 1) = ¬crp(t) ∧ ¬cya(t)
cya(t + 1) = ¬cya(t) ∧ ¬crp(t)
fis(t + 1) = ¬crp(t) ∧ ¬cya(t)
tRNA(t + 1) = fis(t)
P(Xcrp)
P(Xcya)
P(Xfis|Xcrp, Xcya)
P(XtRNA|Xfis)
Model example – autoregulation
gene a
protein A
2
Model example – autoregulation
gene a
protein A
0 1 2 3 4
ˆ identification of discrete expression levels
Model example – autoregulation
gene a
protein A
0 1 2 3 4
ˆ spontanneous (basal) transcription: A → 4
Model example – autoregulation
gene a
protein A
0 1 2 3 4
ˆ range of regulatory activity (A ∈ {3, 4} ⇒ regulation active)
Model example – autoregulation
gene a
protein A
0 1 2 3 4
ˆ target level (A ∈ {3, 4} ⇒ A → 0)
State space – autoregulation
ˆ state transition system S, T, S0
ˆ S state set, S ≡ {0, 1, 2, 3, 4}
ˆ S0 ⊆ S initial state set
ˆ T ⊆ S × S transition function:
source state active regulation target state
0 ∅; [A → 4] 1
1 ∅; [A → 4] 2
2 ∅; [A → 4] 3
3 A →− A; [A → 0] 2
4 A →− A; [A → 0] 3
State space – autoregulation
state transition system for negative autoregulation S, T, S0 = S :
4
3
2
1
0
Combined regulation
gene a gene b
protein A protein B
Discrete characteristics of dynamics
protein A protein B
gene a gene b
0 1 20 1
ˆ identification of dicrete levels of expression
Discrete characteristics of dynamics
protein A protein B
gene a gene b
0 1 20 1
ˆ spontanneous (basal) transcription: A → 1, B → 2
Characteristics of regulation
protein A protein B
gene a gene b
0 1 20 1
ˆ range of regulatory activity B →− B (B = 2 ⇒ regulation
active)
Characteristics of regulation
protein A protein B
gene a gene b
0 1 20 1
ˆ target level B →− B (B = 2 ⇒ B → 0)
Characteristics of regulation – input function
protein A protein B
gene a gene b
0 1 20 1
ˆ range of regulatory activity B →− A (B ∈ {1, 2} ⇒ reg.
active)
Characteristics of regulation – input function
protein A protein B
gene a gene b
0 1 20 1
ˆ range of regulatory activity A →− A (A = 1 ⇒ reg. active)
Characteristics of regulation – input function
protein A protein B
gene a gene b
0 1 20 1
AND
ˆ AND-combined regulation A →− A ∧ B →− A:
A = 1 ∧ B ∈ {1, 2} ⇒ regulation active
Characteristics of regulation – input function
protein A protein B
gene a gene b
0 1 20 1
AND
ˆ target levels of combined regulation A →− A ∧ B →− A:
A = 1 ∧ B ∈ {1, 2} ⇒ A → 0
State space – synchronnous semantics
ˆ state transition system S, T, S0
ˆ S ≡ {0, 1} × {0, 1, 2}
ˆ S0 ⊆ S, we consider S0 = S
ˆ T ⊆ S × S transition function:
source state active regulation target state
[0, 0] ∅; [A → 1, B → 2] [1, 1]
[0, 1] B →−
A; [A → 0, B → 2] [0, 2]
[0, 2] B →−
B ∧ B →−
A; [A → 0, B → 0] [0, 1]
[1, 0] A →−
A; [A → 0, B → 2] [0, 1]
[1, 1] A →−
A ∧ B →−
A; [A → 0, B → 2] [0, 2]
[1, 2] A →−
A ∧ B →−
A ∧ B →−
B; [A → 0, B → 0] [0, 1]
State space – synchronnous semantics
state transition system S, T, S0 = S :
State space – asynchronnous semantics
ˆ state transition system S, T, S0
ˆ S ≡ {0, 1} × {0, 1, 2}
ˆ S0 ⊆ S, we consider S0 = S
ˆ T ⊆ S × S transition function:
source state active regulation target states
[0, 0] ∅; [A → 1, B → 2] [1, 0], [0, 1]
[0, 1] B →−
A; [A → 0, B → 2] [0, 2]
[0, 2] B →−
B ∧ B →−
A; [A → 0, B → 0] [0, 1]
[1, 0] A →−
A; [A → 0, B → 2] [0, 0], [1, 1]
[1, 1] A →−
A ∧ B →−
A; [A → 0, B → 2] [0, 1], [1, 2]
[1, 2] A →−
A ∧ B →−
A ∧ B →−
B; [A → 0, B → 0] [0, 2], [1, 1]
State space – asynchronnous semantics
state transition system S, T, S0 = S :
Properties of discrete semantics
ˆ synchronous semantics
ˆ effect of active regulations is realized in terms of a single event
ˆ strong approximation leading to deterministic state transition
system
ˆ asynchronnous semantics
ˆ effect of active regulations is realized for each gene/protein
individually in terms of single events
ˆ nondeterminism models all possible serializations (so called
interleaving)
ˆ approximation is rather conservative
Free Tool Support
ˆ Gene Interaction Network simulation (GINsim)
http://gin.univ-mrs.fr/GINsim/accueil.html
ˆ asynchronous and synchronous simulation
ˆ allows to get rough understanding of regulatory logic
ˆ allows to identify potential steady states of regulation
ˆ purely qualitative modelling and analysis
ˆ directly allow application of a large set of computer scientific
tools
ˆ graph algorithms for state space graph analysis
ˆ model checking
Literature
Thomas, R. Regulatory networks seen as asynchronous
automata : a logical description. J. Theor. Biol. 153 ,(1991)
1-23.
de Jong. Modeling and simulation of genetic regulatory
systems: A literature review. Journal of Computational Biology
(2002), 9(1):69-105
Bower, J.M. & Bolouri, H. Computational Modeling of Genetic
and Biochemical Networks. Bradford Book, 2001.
A.G. Gonzalez, A. Naldi, L. Sanchez, D.Thieffry, C. Chaouiya.
GINsim: a software suite for the qualitative modelling,
simulation and analysis of regulatory networks. Biosystems
(2006), 84(2):91-100
Top-down vs. bottom-up view
top-to-bottom modeling
systems view
bottom-to-top modelling
agent-based view
Agent-based modeling
ˆ discrete time and discrete space
ˆ strictly local interactions
ˆ dynamics driven by local rules
Agent-based modeling – history
ˆ 1940-60: studying self-reproduction (von Neumann)
ˆ found a theoretical machine that copies itself
ˆ 1970: Game of Life (Conway)
ˆ strong simplification of von Neumann machine
ˆ preserves theoretical computational power of a Turing machine
ˆ 1983: formalization of cellular automata and applications
in physics
Agent-based modeling – cellular automata
ˆ discrete space (a grid of cells)
ˆ homogenity (all cell identical)
ˆ finite discrete states of a cell
ˆ interaction strictly local – next state of a cell depends on its
nearest neighbours
ˆ discrete-time dynamics – system evolves in discrete time-steps
Game of Life
ˆ 2D grid of cells
ˆ each cell has two states: dead or live
ˆ dynamics evolves in turns
ˆ local rules for a living cell:
ˆ if less than two neighbours then die from loneliness
ˆ if more than three neighbours then die from congestion
ˆ stay alive, otherwise
ˆ local rules for a dead cell:
ˆ if just three neighbours then go alive
ˆ stay dead, otherwise
Game of Life
B.P. Zeigler, H. Praehofer, T. Gon Kim. Theory of Modeling and Simulation: Integrating Discrete Event
and Continuous Complex Dynamic Systems. Academic Press, 2000.
Game of Life
ˆ problem: is an infinite behaviour possible in the game of life?
ˆ proven true!
ˆ game of life has universal Turing power (a computer with
unlimited memory and no time contraints)
Cellular automata – Wolfram’s classification
class I dynamics always leads to a stable (non-changing) state
class II dynamics leads to simple repeating (periodical) situations
class III dynamics leads to aperiodic, chaotic behaviour
class IV complex patterns moving in the space
Examples:
http://www.youtube.com/watch?v=XcuBvj0pw-E
Cellular automata – definition
ˆ each cell i has a neighbourhood N(i)
ˆ finite set of local states Σ = {0, ..., k − 1}
ˆ state of cell i in time t is denoted σi (t) ∈ Σ
ˆ local dynamics rule Φ:
ˆ Φ : Σn
→ Σ
ˆ σi (t + 1) = Φ(σj (t), j ∈ N(i))
Cellular automata – definition
ˆ semantics is defined by a state transition system (automaton)
ˆ a configuration is determined as the current state of all cells
ˆ state update (discrete transition event) is defined by
(synchronous) application of local rule to each cell of the
source configuration
ˆ automaton is deterministic
ˆ finite grid implies finite number of configurations
Cellular automata – example
Example of a state update on a 1D grid
Cellular automata – example
Example of dynamics on a 1D grid
Cellular automata – application in biology
ˆ models in developmental biology
ˆ pattern forming simulation
ˆ modeling and simulation of population models (e.g., sheeps
and wolfs)
Cellular automata – example
Retinal Cell Development in Chicken Embryo
ˆ light cells – neural retinal cells
ˆ dark cells – pigmented retinal cells
ˆ dynamics – (a) 10 hours, (b) 40 hours, (c) 72 hours
Free Tool Support
ˆ CelLab – library for cellular automata programming
http://www.fourmilab.ch/cellab/
ˆ NetLogo – multi-agent programmable modeling environment
ˆ education platform for agent-based modelling
ˆ large library of models
ˆ many extensions (continuous and stochastic simulation)
ˆ http://ccl.northwestern.edu/netlogo/
Literature
Deutsch, A. & Dormann, S. Cellular Automaton Modeling of
Biological Pattern Formation. Modeling and Simulation in
Science, Engineering and Technology. Springer-Verlag, 2005.
Ermentroud G.B. & Edelstein-Keshet L. Cellular Automata
Approaches to Biological Modeling. J. theor. Biol. (1993),
160:97-133
M. Alber, M. Kiskowski, J. Glazier & Y. Jiang. On cellular
automaton approaches to modeling biological cells., 2002.