Robustness of Stochastic Biochemical Systems Sven Dražan
Robustness of Stochastic Biochemical
Systems
Sven Dražan
19. 3. 2013
Robustness of Stochastic Biochemical Systems Sven Dražan
Contents
• Systems + Properties + Perturbations = Robustness
• Aims
• Preliminary results
Robustness of Stochastic Biochemical Systems Sven Dražan
Biochemical system
Reproduce
k1
Hunt
k2
Die
k3
Robustness of Stochastic Biochemical Systems Sven Dražan
Biochemical system – Continuous / ODEs
S → 2 S
W + S → 2 W
W →
k1
k2
k3
0
dS/dt = k1.[S] - k2.[W].[S]
dW/dt = k2.[W].[S] - k3.[W]
S
W
Robustness of Stochastic Biochemical Systems Sven Dražan
S
Biochemical system – Stochastic / CTMC
W
0
a1 = k1.[S]
a2 = k2.[W].[S]
a3 = k3.[W]
S → 2 S
W + S → 2 W
W →
k1
k2
k3
Robustness of Stochastic Biochemical Systems Sven Dražan
Biochemical system – Stochastic / CTMC
a1 = k1.[S]
a2 = k2.[W].[S]
a3 = k3.[W]
S → 2 S
W + S → 2 W
W →
k1
k2
k3
S
W
0,4 1,4 2,4 3,4 4,4
0,3 1,3 2,3 3,3 4,3
0,2 1,2 2,2 3,2 4,2
0,1 1,1 2,1 3,1 4,1
0,0 1,0 2,0 3,0 4,0
k1
2k1
3k1
k1
2k1
3k1
k1
2k1
3k1
k1
2k1
3k1
k1
2k1
3k1
k3 2k3 3k3 4k3
k3 2k3 3k3 4k3
k3 2k3 3k3 4k3
k3 2k3 3k3 4k3
k3 2k3 3k3 4k3
2k2
3k2
4k2
4k2
6k2
8k2
6k2
9k2
12k2
k2 2k2 3k2
Robustness of Stochastic Biochemical Systems Sven Dražan
Biochemical system – Stochastic / CTMC / State space enumeration
a1 = k1.[S]
a2 = k2.[W].[S]
a3 = k3.[W]
S → 2 S
W + S → 2 W
W →
k1
k2
k3
W
20 21 22 23 24
15 16 17 18 19
10 11 12 13 14
5 6 7 8 9
0 1 2 3 4
k1
2k1
3k1
k1
2k1
3k1
k1
2k1
3k1
k1
2k1
3k1
k1
2k1
3k1
k3 2k3 3k3 4k3
k3 2k3 3k3 4k3
k3 2k3 3k3 4k3
k3 2k3 3k3 4k3
k3 2k3 3k3 4k3
2k2
3k2
4k2
4k2
6k2
8k2
6k2
9k2
12k2
k2 2k2 3k2
S
Robustness of Stochastic Biochemical Systems Sven Dražan
Biochemical system – Stochastic / CTMC / Q matrix
a1 = k1.[S]
a2 = k2.[W].[S]
a3 = k3.[W]
S → 2 S
W + S → 2 W
W →
k1
k2
k3
W
20 21 22 23 24
15 16 17 18 19
10 11 12 13 14
5 6 7 8 9
0 1 2 3 4
k1
2k1
3k1
k1
2k1
3k1
k1
2k1
3k1
k1
2k1
3k1
k1
2k1
3k1
k3 2k3 3k3 4k3
k3 2k3 3k3 4k3
k3 2k3 3k3 4k3
k3 2k3 3k3 4k3
k3 2k3 3k3 4k3
2k2
3k2
4k2
4k2
6k2
8k2
6k2
9k2
12k2
k2 2k2 3k2
S
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
0 0
1 k3 -∑
2 2k3 -∑
3 3k3 -∑
4 4k3 -∑
5 -∑ k1
6 k2 k3 -∑ k1
7 2k2 2k3 -∑ k1
8 3k2 3k3 -∑ k1
9 4k3 -∑ k1
10 -∑ 2k1
11 2k2 k3 -∑ 2k1
12 4k2 2k3 -∑ 2k1
13 6k2 3k3 -∑ 2k1
14 4k3 -∑ 2k1
15 -∑ 3k1
16 3k2 k3 -∑ 3k1
17 6k2 2k3 -∑ 3k1
18 9k2 3k3 -∑ 3k1
19 4k3 -∑ 3k1
20 0
21 4k2 k3 -∑
22 8k2 2k3 -∑
23 12k2 3k3 -∑
24 4k3 -∑
Robustness of Stochastic Biochemical Systems Sven Dražan
Properties / Continuous system
Signal Temporal Logic
φ = a | !φ | φφ | φU[a,b]φ | G[a,b]φ | F[a,b]φ
Reachability
F[0,7](x>3)
Response
G[0,3]((x<1)F[0,2](x>3))
Oscillation
G[0,5]( (x<1)  F[0,3](x>2) 
(x>2)  F[0,3](x<1) )
t
x
3
2
1
t
x
3
2
1
0 1 2 3 4 5 6 7
0 1 2 3 4 5 6 7
t
x
3
2
1
0 1 2 3 4 5 6 7 8 9
Robustness of Stochastic Biochemical Systems Sven Dražan
Properties / Stochastic system
Continuous Stochastic Logic
Φ = tt | a | !Φ | ΦΦ | P~s[φ] | S~s[φ] ~{ ,  ,  , }, s  [0,1]
φ = XΦ | ΦU[a,b]Φ 0  a  b  ℝ
F[a,b]Φ = tt U[a,b]Φ G[a,b]Φ = ! F[a,b] !Φ
Reachability
P>0.2 [F[0,7](x > 300)]
t
x
300
200
100
0 1 2 3 4 5 6 7
Robustness of Stochastic Biochemical Systems Sven Dražan
Properties / Stochastic system
t
x
300
200
100
0 1 2 3 4 5 6 7
Continuous Stochastic Logic
Φ = tt | a | !Φ | ΦΦ | P~s[φ] | S~s[φ] ~{ ,  ,  , }, s  [0,1]
φ = XΦ | ΦU[a,b]Φ 0  a  b  ℝ
F[a,b]Φ = tt U[a,b]Φ G[a,b]Φ = ! F[a,b] !Φ
Reachability
P>0.2 [F[0,7](x > 300)]
Robustness of Stochastic Biochemical Systems Sven Dražan
System
Initial conditions
S = 2, W = 3
Property
P>0.2 [F[0,7](x > 300)]
Perturbations
a1 = f(k1.[S],t)
a2 = f(k2.[W].[S],t)
a3 = f(k3.[W],t)
S → 2 S
W + S → 2 W
W →
k1
k2
k3
S
W
Robustness of Stochastic Biochemical Systems Sven Dražan
Perturbations / kinetic parameter
a1 = f(k1.[S],t)
a2 = f(k2.[W].[S],t)
a3 = f(k3.[W],t)
S → 2 S
W + S → 2 W
W →
k1
k2
k3
S
W
System
Initial conditions
S = 2, W = 3
Property
P>0.2 [F[0,7](x > 300)]
Robustness of Stochastic Biochemical Systems Sven Dražan
Perturbations / kinetic parameter
a1 = f(k1.[S],t)
a2 = f(k2.[W].[S],t)
a3 = f(k3.[W],t)
S → 2 S
W + S → 2 W
W →
k1
k2
k3
S
W
System
Initial conditions
S = 2, W = 3
Property
P>0.2 [F[0,7](x > 300)]
Robustness of Stochastic Biochemical Systems Sven Dražan
Perturbations / kinetic parameter
a1 = f(k1.[S],t)
a2 = f(k2.[W].[S],t)
a3 = f(k3.[W],t)
S → 2 S
W + S → 2 W
W →
k1
k2
k3
S
W
System
Initial conditions
S = 2, W = 3
Property
P>0.2 [F[0,7](x > 300)]
Robustness of Stochastic Biochemical Systems Sven Dražan
Perturbations / external parameter
a1 = f(k1.[S],t)
a2 = f(k2.[W].[S],t)
a3 = f(k3.[W],t)
S → 2 S
W + S → 2 W
W →
k1
k2
k3
S
W
System
Initial conditions
S = 2, W = 3
Property
P>0.2 [F[0,7](x > 300)]
Robustness of Stochastic Biochemical Systems Sven Dražan
Perturbations / external parameter
a1 = f(k1.[S],t)
a2 = f(k2.[W].[S],t)
a3 = f(k3.[W],t)
S → 2 S
W + S → 2 W
W →
k1
k2
k3
S
W
System
Initial conditions
S = 2, W = 3
Property
P>0.2 [F[0,7](x > 300)]
Robustness of Stochastic Biochemical Systems Sven Dražan
Perturbations / external parameter
a1 = f(k1.[S],t)
a2 = f(k2.[W].[S],t)
a3 = f(k3.[W],t)
S → 2 S
W + S → 2 W
W →
k1
k2
k3
S
W
System
Initial conditions
S = 2, W = 3
Property
P>0.2 [F[0,7](x > 300)]
Robustness of Stochastic Biochemical Systems Sven Dražan
Perturbations / system structure
a1 = f(k1.[S],t)
a2 = f(k2.[W].[S],t)
a3 = f(k3.[W],t)
S → 2 S
W + S → 2 W
W →
k1
k2
k3
S
W
System
Initial conditions
S = 2, W = 3
Property
P>0.2 [F[0,7](x > 300)]
Robustness of Stochastic Biochemical Systems Sven Dražan
Perturbations / system structure
a1 = f(k1.[S],t)
a2 = f(k2.[W].[S],t)
a3 = f(k3.[W],t)
S → 2 S
W + S → 2 W
W →
k1
k2
k3
S
W
System
Initial conditions
S = 2, W = 3
Property
P>0.2 [F[0,7](x > 300)]
Robustness of Stochastic Biochemical Systems Sven Dražan
Perturbations / system structure
a1 = f(k1.[S],t)
a2 = f(k2.[W].[S],t)
a3 = f(k3.[W],t)
S → 2 S
W + S → 2 W
W →
k1
k2
k3
S
W
System
Initial conditions
S = 2, W = 3
Property
P>0.2 [F[0,7](x > 300)]
Robustness of Stochastic Biochemical Systems Sven Dražan
Perturbations / initial conditions
a1 = f(k1.[S],t)
a2 = f(k2.[W].[S],t)
a3 = f(k3.[W],t)
S → 2 S
W + S → 2 W
W →
k1
k2
k3
S
W
System
Initial conditions
S = 2, W = 3
Property
P>0.2 [F[0,7](x > 300)]
Robustness of Stochastic Biochemical Systems Sven Dražan
Perturbations / initial conditions
a1 = f(k1.[S],t)
a2 = f(k2.[W].[S],t)
a3 = f(k3.[W],t)
S → 2 S
W + S → 2 W
W →
k1
k2
k3
S
W
System
Initial conditions
S = 3, W = 3
Property
P>0.2 [F[0,7](x > 300)]
Robustness of Stochastic Biochemical Systems Sven Dražan
Perturbations / initial conditions
a1 = f(k1.[S],t)
a2 = f(k2.[W].[S],t)
a3 = f(k3.[W],t)
S → 2 S
W + S → 2 W
W →
k1
k2
k3
S
W
System
Initial conditions
S[2,3] W[2,3]
Property
P>0.2 [F[0,7](x > 300)]
Robustness of Stochastic Biochemical Systems Sven Dražan
Perturbations / property
a1 = f(k1.[S],t)
a2 = f(k2.[W].[S],t)
a3 = f(k3.[W],t)
S → 2 S
W + S → 2 W
W →
k1
k2
k3
S
W
System
Initial conditions
S = 2, W = 3
Property
P>0.2 [F[0,7](x > 300)]
Robustness of Stochastic Biochemical Systems Sven Dražan
What is Robustness?
Robustness is the ability of a system to maintain its
property against internal and external perturbations.
“Kitano, 2004”
Robustness of Stochastic Biochemical Systems Sven Dražan
What is Robustness?
Robustness is the ability of a system to maintain its
property against internal and external perturbations.
“Kitano, 2004”
Robustness of Stochastic Biochemical Systems Sven Dražan
What is Robustness good for?
What is Robustness good for?
Robustness of Stochastic Biochemical Systems Sven Dražan
To get a bigger picture
Robustness of Stochastic Biochemical Systems Sven Dražan
What is Robustness good for?
Comparing systems
98.8% common DNA
Robustness of Stochastic Biochemical Systems Sven Dražan
What is Robustness good for?
Temperature
Pressure
Temperature
Pressure
= 0.0
> 0.2
> 0.4
> 0.6
> 0.8
Robustness of Stochastic Biochemical Systems Sven Dražan
What is Robustness good for?
Temperature
Pressure
= 0.0
> 0.2
> 0.4
> 0.6
> 0.8
Temperature
Pressure
Robustness of Stochastic Biochemical Systems Sven Dražan
What is Robustness good for?
Temperature
Pressure
= 0.0
> 0.2
> 0.4
> 0.6
> 0.8
Temperature
Pressure
R = 0.338 R = 0.195
Robustness of Stochastic Biochemical Systems Sven Dražan
State of the art – Robustness for Deterministic ODEs
Breach (A. Donzé and O. Maler, 2010)
COPASI (S. Hoops et. al. 2006.) BioCham (F. Fages et. al. 2004)
Robustness of Stochastic Biochemical Systems Sven Dražan
Aims
Definition of Robustness for Stochastic Systems
Efficient computational algorithms
0 1 2 3 4 5 6 7 8 9 10 11 12
0 0
1 k3 -∑
2 2k3 -∑
3 3k3 -∑
4 4k3 -∑
5 -∑ k1
6 k2 k3 -∑ k1
7 2k2 2k3 -∑ k1
8 3k2 3k3 -∑
9 4k3 -∑
10 -∑
11 2k2 k3 -∑
12 4k2 2k3 -∑
Robustness of Stochastic Biochemical Systems Sven Dražan
Preliminary results
Full CSL
Bounded time CSL
Robustness of Stochastic Biochemical Systems Sven Dražan
Preliminary results
S
W
1,3 2,3 3,3
1,2 2,2 3,2
1,1 2,1 3,1
k1
2k1
2k3 3k3
3k2
4k2
Local minimum
Local maximum
Robustness of Stochastic Biochemical Systems Sven Dražan
Preliminary results / Error control
Robustness of Stochastic Biochemical Systems Sven Dražan
Preliminary results / 1D parameter space refinement
Robustness of Stochastic Biochemical Systems Sven Dražan
Preliminary results / 1D model, 1 parameter, 0.01 error
Robustness of Stochastic Biochemical Systems Sven Dražan
Preliminary results / 1D model, 1 parameter, 0.001 error
Robustness of Stochastic Biochemical Systems Sven Dražan
Preliminary results / State space distribution in each interval
Robustness of Stochastic Biochemical Systems Sven Dražan
Preliminary results / 2D parameter space refinement
0.1
0.0825
0.0725
0.0625
0.05
degrA degrA
degrB
0.005 0.0525 0.1 0.005 0.0525 0.1
State #17 Φ := R =? [C<1000] (B = 8,7,9)
Parameter space / Robustness Parameter space / Error
Robustness of Stochastic Biochemical Systems Sven Dražan
Complexity
What affects the complexity?
• # of perturbed parameters and their disc/cont
• dimension of system (# of species)
• size of each dimension (# of particles of each species)
• temporal size of property formulae
• structural complexity of property formulae
Robustness of Stochastic Biochemical Systems Sven Dražan
Conclusion
State of Art
• Robustness = System + Property + Perturbations
• Robustness of biochemical systems is important
• Existing approaches mainly for deterministic ODEs
Aims
• Define robustness for stochastic systems
• Find efficient algorithms to compute robustness
How
• Exploit structure of biochemical CTMCs
• Parallelization on massively parallel platforms
Robustness of Stochastic Biochemical Systems Sven Dražan
Thank you for your attention
Robustness of Stochastic Biochemical Systems Sven Dražan
Previous results
• L. Brim, J. Fabriková, S. Dražan and D. Šafránek. Reachability in Biochemical Dynamical
Systems by Quantitative Discrete Approximation. In Proceedings of the 3rd
International Workshop on Computational Models for Cell Processes (COMPMOD 2011,
EPTCS, pages 97–112, 2011. My contribution is 10% of the whole. I implemented input
parsing in the prototype algorithm and participated during discussions.
• J. Barnat, L. Brim, I. Černá, S. Dražan, J. Fabriková, J. Láník, D. Šafránek and M. Hongwu.
BioDiVinE: A Framework for Parallel Analysis of Biological Models. In Proceedings of
2nd International Workshop on Computational Models for Cell Processes (COMPMOD
2009), EPTCS, pages 31–45, 2009. My contribution to the paper is 10%. I participated in
the implementation phase and evaluated the algorithm’s scaling ability on a cluster.
• J. Barnat, L. Brim, I. Černá, S. Dražan, J. Fabriková and D. Šafránek. Computational
Analysis of Large-Scale Multi-Affine ODE Models. In International Workshop on High
Performance Computational Systems Biology (HiBi 2009). IEEE Computer Society, pages
81–90, 2009. My contribution is 15% of the whole paper. I carried out the comparison of
the different heuristics and visualized the results.
Robustness of Stochastic Biochemical Systems Sven Dražan
Sources
• General definition of robustness
• Kitano H (2007) Towards a theory of biological robustness. Molecular Systems Biology 3.
• CSL – Continuous Stochastic Logic
• Aziz A, Sanwal K, Singhal V, Brayton R (1996) Verifying continuous time Markov chains. In:
Computer Aided Verification, Springer, volume 1102 of LNCS. p. 269–276. URL
http://dx.doi.org/10.1007/3-540-61474-5 75.
• Baier C, Haverkort B, Hermanns H, Katoen J (2003) Model-checking algorithms for
continuous-time Markov chains. IEEE Transactions on Software Engineering 29: 524–541.
• STL – Signal Temporal Logic
• O. Maler and D. Nickovic. Monitoring temporal properties of continuous signals. In FORMATS/FTRTFT,
p. 152–166, 2004.
• Donzé, A., & Maler, O. (2010). Robust satisfaction of temporal logic over real-valued
signals. Formal Modeling and Analysis of Timed Systems, p. 92–106. Springer.
doi:10.1007/978-3-642-15297-9_9
Robustness of Stochastic Biochemical Systems Sven Dražan
Sources
• Software
• NetLogo – http://ccl.northwestern.edu/netlogo
• Copasi - http://www.copasi.org
• Biocham - http://contraintes.inria.fr/BIOCHAM
• Breach - http://www-verimag.imag.fr/~donze/breach_page.html
• Vector field visualization
• http://kevinmehall.net/p/equationexplorer/vectorfield.html
• Wikipedia
• http://en.wikipedia.org/wiki/Lotka_Volterra_equation
• Google Images
• http://onlinelibrary.wiley.com/store/10.1111/j.1742-4658.2012.08719.x/asset/image_m/FEBS_8719_f1gam.gif
• http://ars.els-cdn.com/content/image/1-s2.0-S1096717605000522-gr3.gif
• http://wolf-happy-blog.blog.cz/profil
• http://www.publicdomainpictures.net/view-image.php?picture=ovce-a-jeji-dite&image=124
• http://www.nipcam.com/images/fire_ant_control_products_large.jpg
• http://upload.wikimedia.org/wikipedia/commons/2/24/Giant_Sequoia_Sequoiadendron_giganteum_Tyler_Tree_2000px.jpg
• http://www.surftravelcompany.com/big-wave-pics/big-wave.jpg
• http://upload.wikimedia.org/wikipedia/commons/f/f8/Terraforming_Mars_transition_horizontal.jpg
• http://limages.vr-zone.net/body/15884/47675_TeslaKeplerGK110_FNL_800_PR.jpg.jpeg
• Other
• Human vs. Chimp: http://www.sciencedirect.com/science/article/pii/S0002929707640968