Hybrid systems methods for biochemical networks Adam Halasz Outline Hybrid systems, reachability Piecewise affine approximations of biochemical systems Example I: Glucose-lactose Example II: Tetracyclin resistance Biomolecular networks as hybrid systems Networks of chemical and molecular processes

State space can be huge (O(103) variables for one cell) Lots of truly discrete behavior: State = {values of all concentrations} Rates of each process are continuous functions of the state

Several layers of processes, different timescales Genes on/off Discrete variables Lots of apparent discrete behavior Nontrivial continuous dynamics produces multistability, bifurcations Abstractions commonly used and/or required for simplification Biomolecular dynamical systems Central

dogma of molecular biology DNA encodes genes; it replicates Genes are transcribed into mRNA mRNA is translated into proteins Proteins may: act as enzymes that catalyze metabolic reactions act as transcription factors

Metabolic reactions big network that converts incoming nutrients into useful substances and by-products reactions proceed much faster when the right enzymes are available The Central Dogma DNA replicates during cell division Transcription performed by RNA polymerase

Requires a promoter site Several genes bundled to one promoter = operon In higher organisms, mRNA is spliced Translation performed by Ribosomes Protein synthesis needs raw material Genes to proteins Proteins are synthesized as chains of elementary proteins, amino-acids They fold, giving rise to complicated 3d structures

Several molecules may be assembled into more complicated machines, such as RNAP, ribosomes, etc. Metabolic network Very complex Structured Stoichiometry is more easily identified than rate laws Many networks available in databases, e.g. Kegg Reactions linked to individual genes Lots of feedback

Metabolic network has a lot of control Feedback between Metabolites Genes and proteins Continuous adjustment to external conditions Signaling networks Control is through rate laws, but also through stochastic mechanisms

Hybrid systems much of the underlying dynamics is continuous, but.. complexity and lack of detailed kinetic information require the use of hybrid abstractions Hybrid systems Two topics to be addressed: 1. How to build a good hybrid abstraction 2. How to analyze a network that

includes hybrid abstractions Using hybrid systems abstractions to build hybrid systems abstractions The lac operon is a bistable genetic switch Multiple positive feedback bistable Input: external lactose State: x={M,B,A,L,P} x f (x) mRNA

-gal perm repressor AlloLactose Lactose External Lactose Using hybrid systems abstractions to build hybrid systems abstractions May be abstracted to an automaton:

Input: external lactose State: {I} Le Llow e HIGH I=1 LOW I=0 Le Lhigh e high Llow

f (...); L g (...) e e The characteristic still depends on the underlying kinetic parameters! Reachability The full lac model can be simulated to investigate induction, but that can be expensive

The question of whether induction is possible may be framed as a reachability problem Many other situations with discrete outcomes are amenable to reachability Initial Question 1: which ones end up in a viable final state? Final Irreversible damage Question 2: which ones survive?

Kinetics 1 Dynamic models have a special d A structure! k r C k f A B Example A B C dt d B k r C k f A B dt d C k f A B k r C dt

More generally, x f l (x) f l ( x) iN i1 l c x x i1 ,,iN 1 N i1 ,i N {0 ,1}

Kinetics 1 (continued) y y e gy1 f hy1 x x a cy1 b dy1 x y e gy1 f hy1 x y1 x x a bx cy dxy y e fx gy hxy The vector field is a unique (affine) function

of the vectors at the end points Kinetics 1 (continued) x f (x) The vector field is a unique function of the vectors at the vertices [Belta, Habets, Kumar 2002] Hybrid System Rectangular partitions Affine dynamics

Transcription rate Transcription rate Kinetics (2) Concentration of repressor Concentration of allolactose Piecewise affine approximation Vmax [ S ] r ([ S ]) K m [S ]

Vmax [ S ] [S ] 2K m r ([ S ]) 2 K m Vmax [ S ] 2 K m Simplest approximation with two affine pieces Can use any number, to achieve any desired precision Piecewise is hybrid Vmax [ S ] [S ] 2K m r ([ S ]) 2 K m Vmax

[ S ] 2 K m [ S ] 2 K m [ P ] Vmax [S ] 2K m [ P ] Vmax [S ] 2K m Piecewise approximation has different equations in each interval Transitions occur as the variable switches intervals

S2 Several substrates that saturate [ P1 ] B[ S1 ] ; [ P2 ] C [ S1 ] T1 [ P1 ] B[ S1 ] [ P ] D[ S ] 2 [ S 2 ] T2 2 [ P1 ] A ; [ P2 ] C

[ S1 ] T1 [ S 2 ] T2 T2 [ P1 ] B[ S1 ] ; [ P2 ] D[ S 2 ] [ S1 ] T1 S1 [ S 2 ] T2 [ P1 ] A ; [ P2 ] D[ S 2 ] [ S1 ] T1 [ S 2 ] T2 T1

Piecewise approximation has different equations in each interval Transitions occur as the variable switches intervals Can continue in many dimensions Abstraction Model the biochemical network as a switched system with continuous multi-affine dynamics

Each mode has simple dynamics More insight Approximation may be refined as needed Partition may be refined independently of dynamics No additional computational difficulties Traditional simulations are easier Efficient reachability algorithms can be applied Reachability analysis Can the system reach a set of states starting from a set of initial conditions? x2sw1 Analysis x2sw 2

x3 x3sw 2 x3sw1 x2 x1sw1 x1sw 2 x1 x2sw1 Analysis x2sw 2 x3

x3sw 2 x3sw1 x2 Initial x1 Reachable x1sw1 x1sw 2 Unreachable

Hybrid System Analysis Reachability Cell A is reachable from cell B if there is at least one trajectory from B to A Cell A is not reachable from cell B if there are no trajectories from B to A Glucose-lactose system The lactose metabolism is self-nourishing: The

cell needs enzymes for: Inbound lactose transport (permease) Lactose processing (-galactosidase) Permease and -galactosidase are gene products of the lac operon Lac operon is repressed in the absence of allolactose Allolactose is produced when lactose is processed

Bistability: a low and a high lactose metabolism state induction needed to move into the high state Lac system in E.coli mRNA -gal repressor AlloLactose perm

Lactose External Lactose Lac system in E.coli Crucial switching property, sensitive to basal rate Can be framed in terms of reachability Lac system in E.coli Hybrid model constructed using a fine grained linearization of the nonlinear rate laws Predictions of the two models are very similar Hybrid model within 5% uncertainty of model parameters Glucose-lactose system

Lactose is an alternative energy source Glucose is the preferred nutrient; bacteria also grow on lactose, but only when glucose is absent There are two mechanisms that ensure this: Inducer exclusion Catabolite repression mRNA Lac repressor perm

-gal AlloLactose Lactose External Lactose Glucose inhibits the influx of lactose CAP cAMP

CAP competes with lac repressor, enhancing transcription External Glucose cAMP is produced when glucose is absent Steady states For a given Glucose (Ge) value, the steady state line is S-shaped The bistable section increases as Ge increases The upper threshold for Lactose (Le) is higher if Ge is present

Induction and reachability Expect the vicinity of zero to be confined when system is bistable unless it is induced by increasing Le, decreasing Ge, or both Suppose initially the system is at zero allolactose. Then it will have to settle on the lower sheet.. Induction and reachability Up-switching possible if (Le,Ge) outside the bistable region for some time Upward switching trajectories Final, induced state Initial state, close to zero

Induction and reachability B Follow trajectories in state space Induced trajectories leave the vicinity of the initial state A Induction and reachability B Cover the area of interest with a grid A

Induction and reachability B Induced trajectories leave the vicinity of the initial state For reachability, only need to cover the vicinity Verify those configurations that do not leave the grid A Discretization Reachability results Calculate highest Allolactose (A) reached Sweep for (Le,Ge)

Bistable regions are non-inducible, hence they reach only the lower A values Reachability results Non-inducible region should match the footprint of bi-stability Reachability results Analyzing networks of hybrid abstractions The lac switch is one piece in a potentially huge circuit, which has both discontinuous and continuous elements A true of hybrid system:

Discontinuous dynamics Different state variables Filippov states! Hierarchy of modes! Networks of hybrid

abstractions Continuous part of state space is still a set of concentrations Dynamics is still given by reaction rates Reaction rates are given by discontinuous functions of the state variables: x f (x) Networks of hybrid abstractions Partition of continuous part of state space along threshold values Boundaries treated as separate modes Discrete transition system

Model checking Networks of hybrid abstractions Can analyze complex interconnections Elucidate roles of genes Summary Molecular biology offers many instances of natural hybrid systems Very large state spaces, thousands of substances Complex networks, nonlinear equations Switching and other discontinuous behavior

Genes on/off Multistability, bifurcation Hybrid abstractions Two aspects: Constructing hybrid abstractions Analyzing networks a hybrid systems Both directions work towards automated analysis

Reading Calin Belta Boston U. Hidde de Jong INRIA Rhone-Alpes, FR/EU Claire Tomlin Berkeley Ashish Tiwari SRI, Palo Alto, CA Joao Hespanha Santa Barbara V. Kumar, O. Sokolsky, G. Pappas, A. Julius, A. Halasz U. Penn Hybrid systems, reachability

Piecewise affine approximations of biochemical systems Example I: Glucose-lactose Example II: Tetracyclin resistance Tetracycline resistance via TetA efflux Tc0 periplasm efflux diffusion Mg Tc cytoplasm

[TcMg]+ tetR O1 O2 tetA TetA TetR [TcMg]+TetR Tc0 periplasm efflux

diffusion Mg cytoplasm Tc [TcMg]+ tetR O1 O2 TetR [TcMg]+TetR tetA

TetA Tet Model Analysis Model describes a bacterial defense mechanism against attack with an antibiotic (tetracycline, Tc) Tc destroys the cells ribosomes, inflicting potentially irreversible damage to the transcription-translation apparatus. Objective is to avoid accumulation of Tc inside the cell. Our objective: to disrupt the defense mechanism. For this we first have to: 1. 2. Assess the actual model parameters Identify parameter modifications that disrupt the mechanism

Tet Model Building Model parameters not fully known Use existing information on known reactions Use consistency checks and qualitative arguments Determine parameters indirectly by comparing model predictions to experimental results

Perform experiments to verify model Tet Model Analysis Measures of the defense mechanisms effectiveness: Irreversible damage to transcription-translation apparatus: Direct investigation would require a greatly expanded model Use proxies instead

Final Tc concentration May not tell the whole story Maximum transient Tc concentration May cause irreversible damage Tet Model Analysis We wish to investigate how these efficiency measures depend on model parameters, especially those parameters that are not well known.

We may indirectly pin down their value ranges We may learn which aspects of this mechanism are the most easy to compromise by targeting with a drug Final Tc concentration Computed by a steady state calculation Maximum transient Tc Not directly calculable One way: many simulations Other method: reachability

TetModel Use Case (2005) SBML2Charon UPenn SBMLEditor Model CHARON Reachability Tools Parameter ranges Equilibrium

Point Analyzer Full Model (SBML, annotated) Hybrid System Model Builder (HSMB) UPenn Hybrid Model (SBML) Simulator UPenn

Stochastic Simulator UTenn Experimental Traces ODE Simulator UPenn Simpathica Toolset NYU Hybrid SAL SRI

Validation of hybrid system abstractions Summary Hybrid systems bridge the gap between discrete big picture models and detailed, continuous dynamics Piecewise multi-affine approximations are well suited for biochemical networks Several software tools apply efficient algorithms for: Model building Simulation Reachability

Type of problems: Mid-sized networks, focus on one mechanism Analysis of parameter and initial state ranges Prediction of qualitative outcomes Stringent response The stringent response is the set of metabolic and regulatory changes that take place in a bacterium as a consequence of a downshift in the availability of nutritional substances, especially amino-acids. Transcription is globally decreased

Promoters for stable RNA are downregulated Promoters for amino-acids are upregulated Stringent response Stringent response Model block diagram Stalled complexes tRNAc,u (p)ppGpp (p)ppGpp reactions Upregulated mRNA

Translation Downegulated mRNA Transcription Ribosome assembly proteins Ribosomes Ribosomal RNA Stringent response Hybrid model with 9 variables, 2 modes One outside control (amino-acid availability) Negative feedback, only one steady state for

given conditions Stringent response Steady-state calculations Signaling substance increases with parameter r Transcription [initiation] rate decreases Stringent response Dynamic calculations Surge of signaling substance indicates potentially lethal condition: excessive accumulation of stalled transcriptional complexes Reachability analysis can constrain the peak value