●
DIPARTIMENTO DI INGEGNERIA DELL'INFORMAZIONE E SCIENZE MATEMATICHE
Dr. DIANA HERMITH SIENA 20/04/2016
A Constraint-based
Modeling Approach for Biochemical Systems
MODELS AND LANGUAGES FOR
BIOINFORMATICS
Motivation
{ Understanding biology from a computational/system perspective }
A CONSTRAINT-BASED MODELING APPROACH FOR BIOCHEMICAL
SYSTEMS
A CONSTRAINT-BASED MODELING APPROACH FOR BIOCHEMICAL
SYSTEMS
Flow of Info rmatio n
Levels o
f Abstrac tion
A CONSTRAINT-BASED MODELING APPROACH FOR BIOCHEMICAL
SYSTEMS
Credit: Nicolle Rager, National Science Foundation
Cell signaling networks: the processing (flow)
of biological information
● Abstraction is a generic Abstraction technique that allows the scientist or engineer to focus
only on certain features of a system while hiding others.
A CONSTRAINT-BASED MODELING APPROACH FOR BIOCHEMICAL
SYSTEMS
A CONSTRAINT-BASED MODELING APPROACH FOR BIOCHEMICAL
SYSTEMS
● Biological systems are information processing systems.
● Information and computation theory may become a powerful lens for describing, measuring, and understanding processes in
the natural world.
A CONSTRAINT-BASED MODELING APPROACH FOR BIOCHEMICAL
SYSTEMS
Biochemical/Biological Systems
● They consist of the species and their interactions. consist of the species and their interactions
● The are inherently concurrent, i.e., several interactions inherently concurrent can usually happen independently and in parallel.
● They are inherently stochastic, i.e., the timing behavior inherently stochastic of the interactions is governed by stochastic laws.
● Partial information (incomplete information of the state Partial information of the system) arises naturally.
A CONSTRAINT-BASED MODELING APPROACH FOR BIOCHEMICAL
SYSTEMS
A CONSTRAINT-BASED MODELING APPROACH FOR BIOCHEMICAL
SYSTEMS
It is possible to describe It is possible to describe
biochemical/biological systems biochemical/biological systems,
i.e., regulatory, metabolic, and signaling / molecular pathways, as well as multicellular processes such
as immune responses, as systems as systems of interacting computations
of interacting computations operating in parallel
operating in parallel.
A CONSTRAINT-BASED MODELING APPROACH FOR BIOCHEMICAL
SYSTEMS
A computational framework applied to bio-systems is a crucial
ingredient when dealing with the description of biocomplexity and its
evolution.
A CONSTRAINT-BASED MODELING APPROACH FOR BIOCHEMICAL
SYSTEMS
Question 1.
Describe a
biochemical/biological system.
1-2
A CONSTRAINT-BASED MODELING APPROACH FOR BIOCHEMICAL
SYSTEMS
Question 2.
What is the methodology for analyzing a
biochemical/biological system?
Applications
{ Understanding biology from a computational/system perspective }
A CONSTRAINT-BASED MODELING APPROACH FOR BIOCHEMICAL
SYSTEMS
A CONSTRAINT-BASED MODELING APPROACH FOR BIOCHEMICAL
SYSTEMS
Modeling Formalisms with a focus on Molecular
Interactions (MIs) Bio-Calculus
PRISM
Reaction Systems
Modeling Formalisms with a focus on Spatial
Information (SI)
Beta-binders with Compartments BioAmbients Calculus
The Brane Calculi P Systems Modeling Formalisms with a
focus on both MIs and SI The Biochemical Abstract
Machine (BIOCHAM) Bio-PEPA
COPASI BioNetGen Pathway Logic
Petri Nets
A CONSTRAINT-BASED MODELING APPROACH FOR BIOCHEMICAL
SYSTEMS
A CONSTRAINT-BASED MODELING APPROACH FOR BIOCHEMICAL
SYSTEMS
Concurrent Constraint Programming Concurrent Constraint Programming
(CCP) (CCP)
http://cic.puj.edu.co/wiki/doku.php?id=grupos:avispa:ccp-wikipedia
● A model of concurrency in which
constraints are the elements of
information. The notion of a store
represents the state of the system.
Constraint-based Discrete Modeling
{ Understanding biology from a computational/system perspective }
A CONSTRAINT-BASED MODELING APPROACH FOR BIOCHEMICAL
SYSTEMS
A CONSTRAINT-BASED MODELING APPROACH FOR BIOCHEMICAL
SYSTEMS
A CONSTRAINT-BASED MODELING APPROACH FOR BIOCHEMICAL
SYSTEMS
Concurrent agents (i.e., processes) for modeling biological entities
The explicit notion of time for describing the evolution, i.e., the
dynamical behavior of the biological system
Constraints as a formal mechanism for representing
partial information about the state of the system
Asynchronous and non-deterministic
operators for modeling partial information about the
behavior of the system
http://cic.puj.edu.co/wiki/doku.php?id=grupos:avispa:ccp-wikipedia
A CONSTRAINT-BASED MODELING
APPROACH FOR BIOCHEMICAL SYSTEMS
BioWayS (BIOchemical pathWAY
Simulator)
A CONSTRAINT-BASED MODELING
APPROACH FOR BIOCHEMICAL SYSTEMS
● System's variables: the reacting species and their initial System's variables amount.
● System's reactions: the type of reaction that describes System's reactions:
how molecules interact.
● Propensity of reactions: the probability of each Propensity of reactions:
reaction to occur.
● Duration of reactions: the duration of each type of Duration of reactions:
interaction.
● Number of time units: the total time of the simulation Number of time units:
(time steps) for generating and simulating the system.
A CONSTRAINT-BASED MODELING APPROACH FOR BIOCHEMICAL
SYSTEMS
A CONSTRAINT-BASED MODELING APPROACH FOR BIOCHEMICAL
SYSTEMS
first messenger
transducer
second messenger
effector receptor
The signaling pathway for glycogen breakdown (glycogenolysis)
(taken from [1] and
https://files.nyu.edu/gcl1/public/).
[1] John W. Baynes and Marek H. Dominiczak. Medical Biochemistry. Mosby, 2004.
Biological Model
● In higher organisms such as mammals glycogen is stored in the liver as a reservoir of glucose.
● Once the glucagon receptor embedded in the cell membrane binds its ligand, it activates a signal transduction pathway inside the cell leading to a glycogenolysis.
● The signal transduction system for the glycogen degradation pathway is modular and is made of three type of proteins: (i) a receptor, (ii) a transducer, and (iii) an effector.
● The binding of glucagon at the cell-surface stimulates the synthesis of a second messenger inside the cell, which in turn stimulates a metabolic response.
A CONSTRAINT-BASED MODELING
APPROACH FOR BIOCHEMICAL SYSTEMS
A CONSTRAINT-BASED MODELING APPROACH FOR BIOCHEMICAL
SYSTEMS
A CONSTRAINT-BASED MODELING APPROACH FOR BIOCHEMICAL
SYSTEMS
A CONSTRAINT-BASED MODELING
APPROACH FOR BIOCHEMICAL SYSTEMS
Some observables on system's behavior
Amplification of the signal: in response to a small amount of glucagon, a large quantity of cAMP is produced.
It is promoted the degradation of glycogen into molecules of glucose 1-phosphate.
The initial stimulus is greatly amplified by the binding of the hormone glucagon to its respective receptor in a
“physical interaction” followed by a set of biochemical reactions (transduction pathway).
Our model describes the processing of biological information from the external environment to the
intracellular medium.
A CONSTRAINT-BASED MODELING APPROACH FOR BIOCHEMICAL
SYSTEMS
The complex [gp120]gp41 depends of its reactants but at the same time, the reaction that has this
complex as a reactant
cannot be executed if there is not enough quantity of this one to carry out that reaction.
Consistently with experimental data, we found that the presence of the [gp120]gp41 complex is necessary for
both the binding and fusion, the starting point in the replication process. Without this complex, the virus is
unable to infect the host cell.
National Institute of Allergy and Infectious Diseases NIAID.
HIV replication cycle: Steps in the HIV replication cycle.
Summarizing
● We have used a technique based on a temporal extension of Concurrent
Constraint Programming for modeling two biochemical systems.
● We built a tool (BioWayS) for modeling and analyzing biochemical interaction
networks.
A CONSTRAINT-BASED MODELING
APPROACH FOR BIOCHEMICAL SYSTEMS
● Because of the nature of reactive
computation in nTCC, a constraint-based discrete modeling approach, becomes
more than appropriate for taking into consideration, biological phenomena in which the processing of information from the external environment to the
intracellular medium, is given by a small stimulus that produces a large response (i.e., the initial stimulus is greatly
amplified).
A CONSTRAINT-BASED MODELING
APPROACH FOR BIOCHEMICAL SYSTEMS
● The core of our modeling approach is to represent biochemical processes as
concurrent computations. We consider that a computational model that expresses
concurrency, is in fact, the closest
approximation to capture the intrinsic nature of biochemical systems.
A CONSTRAINT-BASED MODELING
APPROACH FOR BIOCHEMICAL SYSTEMS
A CONSTRAINT-BASED MODELING APPROACH FOR BIOCHEMICAL
SYSTEMS
Question 3.
In CCP, the ________ contains all the constraints currently known about
the system. Processes
compute the ___________ and they are recorded into the store.
3-5
A CONSTRAINT-BASED MODELING APPROACH FOR BIOCHEMICAL
SYSTEMS
Question 4.
What is reactive computation?
A CONSTRAINT-BASED MODELING APPROACH FOR BIOCHEMICAL
SYSTEMS
Question 5.
Provide some examples of
constraints.
Constraint-based Stochastic Modeling
{ Understanding biology from a computational/system perspective }
A CONSTRAINT-BASED MODELING
APPROACH FOR BIOCHEMICAL SYSTEMS
Discrete–Stochastic
computational models provide faithful descriptions of stochastic
fluctuations in biological systems.
A CONSTRAINT-BASED MODELING
APPROACH FOR BIOCHEMICAL SYSTEMS
A CONSTRAINT-BASED MODELING
APPROACH FOR BIOCHEMICAL SYSTEMS
● Discrete: the system evolves moving from one discrete state
to another;
● Stochastic: the evolution of the system is driven by stochastic
algorithms computing the probability of evolving to the
following state .
A CONSTRAINT-BASED MODELING APPROACH FOR BIOCHEMICAL
SYSTEMS
Biological Model
Single-molecule enzyme experiments
It records the stochastic time trace of repetitive reactions of an individual enzyme molecule regarding the duration of the waiting time between a reaction and the following one.
Single-Molecule Michaelis−Menten Equations. S. C. Kou, Binny J. Cherayil, Wei Min, Brian P. English, and,
and X. Sunney Xie. The Journal of Physical Chemistry B, 2005 109 (41), 19068-19081.
A CONSTRAINT-BASED MODELING APPROACH FOR BIOCHEMICAL
SYSTEMS
Single-molecule enzyme experiments
Single-Molecule Michaelis−Menten Equations. S. C. Kou, Binny J. Cherayil, Wei Min, Brian P. English, and,
and X. Sunney Xie. The Journal of Physical Chemistry B, 2005 109 (41), 19068-19081.
A CONSTRAINT-BASED MODELING
APPROACH FOR BIOCHEMICAL SYSTEMS
A Gecode script solver for single-
molecule experiments on enzymes with mass action kinetics.
Gecode (http://www.gecode.org/) is an open, free, portable, accessible, and efficient environment for developing constraint-
based systems and applications.
Basically, it implements constraint solvers over integers, Booleans, sets, and floats; advanced branching heuristics and many search
engines.
A CONSTRAINT-BASED MODELING
APPROACH FOR BIOCHEMICAL SYSTEMS
The attractiveness of using CP where problems are solved declaratively has been always the same; the user states
the problem, and a search engine searches automatically
for a solution.
A CONSTRAINT-BASED MODELING APPROACH FOR BIOCHEMICAL
SYSTEMS
Gecode is a set of C++ libraries where models (i.e., Constraint Satisfaction Problems (CSPs)) are C++ programs that must be
compiled with Gecode libraries and executed to be solved. In essence, our model is implemented as the class Exp_Function, which inherits
from the class Script (i.e., Lines 6-7). Lines 1-3 are the required
libraries from Gecode. In Lines 9 and 11 are declared the variables (of
type FloatVar) and the constants (of type FloatVal) needed.
A CONSTRAINT-BASED MODELING APPROACH FOR BIOCHEMICAL
SYSTEMS
In Lines 15-39 is declared the constructor of the class. It takes
as parameters the substrate concentration (i.e., [S]) and the kinetic constants (i.e., k1, k_-1(a.k.a., k3), and k2). Besides, R_VAL is needed
to determine the number of solutions that the solver must generate.
A CONSTRAINT-BASED MODELING APPROACH FOR BIOCHEMICAL
SYSTEMS
In Lines 18-24 are initialized the variables (i.e., floating-point
variables with domains TAU[0.0,inf), R[0.0,1.0], A[0.0,inf), B(-inf,0.0], ALPHA[0.0,inf), BETA(-inf,inf), and GAMMA(-inf,inf)) and the constants,
respectively. Note that *this is called "home space" (a.k.a., Script)
where the variables, constraints, branchers, and so on, live.
A CONSTRAINT-BASED MODELING APPROACH FOR BIOCHEMICAL
SYSTEMS
In Lines 27-37 we add the constraints that should be satisfied to solve the experimental PDF. Constraints are posted with function rel. Simple
relations constraints over float variables enforce relations between
float variables and between float variables and float values.
A CONSTRAINT-BASED MODELING APPROACH FOR BIOCHEMICAL
SYSTEMS
In Lines 35-37 we stated the relation between the variable R and the other ones accordingly with the experimental PDF. It allows to both determine R given a t (i.e., F(t) = R) and to compute t given some R
(i.e., t = F^-1(R)).
A CONSTRAINT-BASED MODELING APPROACH FOR BIOCHEMICAL
SYSTEMS
In Line 39 we have the strategy for branching search (a.k.a.,
labelling). The variable TAU is chosen for labelling and the values not
greater than the mean are explored first.
A CONSTRAINT-BASED MODELING APPROACH FOR BIOCHEMICAL
SYSTEMS
Simulation of the experimental PDF for single-molecule experiments
A CONSTRAINT-BASED MODELING APPROACH FOR BIOCHEMICAL
SYSTEMS
Simulation of continuous PDF distributions such as the negative-exponential
and Erlang
A CONSTRAINT-BASED MODELING APPROACH FOR BIOCHEMICAL
SYSTEMS
Simulation of biochemical systems with more than one type of PDF
Summarizing
● The basic idea, but at the same time the most powerful application of CP
is that the user would just need to state the system constraints, and a solver will find eventually a solution
that should satisfy all the constraints.
A CONSTRAINT-BASED MODELING
APPROACH FOR BIOCHEMICAL SYSTEMS
● We built a methodology that is quite general, continuous probability
distributions can be sampled for waiting times, either experimentally
inferred or “generic” such as negative-exponential and Erlang.
A CONSTRAINT-BASED MODELING
APPROACH FOR BIOCHEMICAL SYSTEMS
● We provide a strategy that can be used for simulating a network of biochemical reactions. Each reaction
can be modeled with its particular waiting time, which is not possible
so far in GSSA.
A CONSTRAINT-BASED MODELING
APPROACH FOR BIOCHEMICAL SYSTEMS
● In GSSA is assumed a homogeneous (well- stirred) mixture of a chemical system, when indeed, biochemical systems are
normally heterogeneous systems in a
dynamical equilibrium.
A CONSTRAINT-BASED MODELING APPROACH FOR BIOCHEMICAL
SYSTEMS
Question 6.
Why are discrete-stochastic models important?
6-7
A CONSTRAINT-BASED MODELING APPROACH FOR BIOCHEMICAL
SYSTEMS
Question 7.
What is the advantage of using a
Constraint Programming approach?
Concluding Remarks
{ Understanding biology from a computational/system perspective }
A CONSTRAINT-BASED MODELING
APPROACH FOR BIOCHEMICAL SYSTEMS
➔
Are concurrent (i.e., changes in the surrounding Are concurrent environment can trigger the execution of many
parallel processes).
➔
Are computations (i.e., following specific Are computations definitions and rules).
By using constraint-based computational models for analyzing biological systems, we can promote a deeper exploration in
biology. We recall that processes in biochemical systems:
A CONSTRAINT-BASED MODELING
APPROACH FOR BIOCHEMICAL SYSTEMS
➔
Operate at many levels including the sub- Operate at many levels molecular, molecular, sub-cellular, cellular, etc.
➔
