IV121: Computer science applications in biology Qualitative Models in Biology David ˇSafr´anek February 25, 2013 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) Model Types real−tim e m odels continuous−tim e stochastic m odels qualitative m odels finite autom ata continuous−tim e determ inistic m odels discrete−tim e determ inistic m odels discrete−tim e stochastic m odels D TM C ,M D P C TM C ,C M E tim ed autom ata state−transition system s O D E,D AE time quantitatively modeled time qualitatively abstracted continuousvalues discretevalues difference equations 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) • usually abstract from space (no information where the event occurred) • but see agent-based models at the end of the lecture • 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) 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 no 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) From Structure to Dynamics C: A: B: R. Thomas and R. d’Ari, CRC Press 1990. Biological feedback. 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 • unbounded 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∈N(i) σj (t)) 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.