Transcript Summary of Some Ideas - NYU Computer Science

SIAM Meeting
10 04 2002
Cell Talk
¦
Bud Mishra
Professor of CS & Mathematics (Courant, NYU)
Professor (Cold Spring Harbor Laboratory)
10/4/2002
©Bud Mishra, 2002
Cell Talk»1
10/4/2002
©Bud Mishra, 2002
Cell Talk»2
Robert Hooke
• Robert Hooke (1635-1703) was an experimental scientist,
mathematician, architect, and astronomer. Secretary of the
Royal Society from 1677 to 1682, he is remembered for the
discovery of the proportional relationship of the extension of a
spring and the force applied to produce that extension.
• His work Micrographia of 1665 contained his microscopical
investigations, which included the first identification of
biological cells.
• Hooke became involved in a dispute with Isaac Newton over
the priority of the discovery of the inverse square law of
gravitation. Although he communicated some form of inverse
square law to Newton, modern opinion is that credit for the
law of universal gravitation must go to Newton.
• Aubrey held his ability in high regard: "He is certainly the
greatest Mechanick this day in the World."
10/4/2002
©Bud Mishra, 2002
Cell Talk»3
Newton & Hooke
• “[Huygen’s Preface] is concerning those properties of gravity
which I myself first discovered and showed to this Society and
years since, which of late Mr. Newton has done me the favour to
print and publish as his own inventions.
• “And particularly that of the oval figure of the Earth which was
read by me to this Society about 27 years since upon the
occasion of the carrying the pendulum clocks to sea and at two
other times since, though I have had the ill fortune not to be
heard, and I conceive there are some present that may very well
remember and do know that Mr. Newton did not send up that
addition to his book till some weeks after I had read and showed
the experiments and demonstration thereof in this place and had
answered the reproachful letter of Dr. Wallis from Oxford.“
10/4/2002
©Bud Mishra, 2002
Cell Talk»4
Newton & Hooke
• “If I have seen further than other men, it is
because I have stood on the shoulders of giants
and you my dear Hooke, have not." -Newton to Hooke
10/4/2002
©Bud Mishra, 2002
Cell Talk»5
Image & Logic
• The great distance between
– a glimpsed truth and
– a demonstrated truth
• Christopher Wren/Alexis Claude Clairaut
10/4/2002
©Bud Mishra, 2002
Cell Talk»6
Micrographia
Principia
10/4/2002
©Bud Mishra, 2002
Cell Talk»7
Micrographia
10/4/2002
©Bud Mishra, 2002
Cell Talk»8
“The Brain & the Fancy”
• “The truth is, the science of
Nature has already been too long
made only a work of the brain
and the fancy. It is now high time
that it should return to the
plainness and soundness of
observations on material and
obvious things.”
– Robert Hooke. (1635 - 1703),
Micrographia 1665
10/4/2002
©Bud Mishra, 2002
Cell Talk»9
Principia
10/4/2002
©Bud Mishra, 2002
Cell Talk»10
“Induction & Hypothesis”
• Rule IV. In experimental philosophy we
are to look upon propositions collected
by general induction from phenomena
as accurately or very nearly true,
notwithstanding any contrary
hypotheses that may be imagined, 'till
such time as other phenomena occur, by
which they may either be made more
accurate, or liable to exceptions…
Hypotheses non fingo.
I feign no hypotheses.
Principia Mathematica.
10/4/2002
• This rule we must follow, that the
argument of induction may not be
evaded by hypotheses.
©Bud Mishra, 2002
Cell Talk»11
Morphogenesis
10/4/2002
©Bud Mishra, 2002
Cell Talk»12
Alan Turing: 1952
•
“The Chemical Basis of Morphogenesis,” 1952,
Phil. Trans. Roy. Soc. of London, Series B:
Biological Sciences, 237:37—72.
• A reaction-diffusion model for
development.
10/4/2002
©Bud Mishra, 2002
Cell Talk»13
“A mathematical model for the growing
embryo.”
10/4/2002
• A very general program for modeling
embryogenesis: The `model’ is “a
simplification and an idealization and
consequently a falsification.”
• Morphogen: “is simply the kind of
substance concerned in this theory…” in
fact, anything that diffuses into the tissue
and “somehow persuades it to develop
along different lines from those which
would have been followed in its absence”
qualifies.
©Bud Mishra, 2002
Cell Talk»14
Diffusion equation
first
temporal
derivative:
rate
 a/ t = Da r2 a
second
spatial
derivative:
flux
a: concentration
Da: diffusion constant
10/4/2002
©Bud Mishra, 2002
Cell Talk»15
Reaction-Diffusion
a/ t = f(a,b) + Da r2 a
f(a,b) = a(b-1) –k1
 b/ t = g(a,b) + Db r2 b g(a,b) = -ab +k2
a
Turing, A.M. (1952).“The chemical basis
of morphogenesis.“ Phil. Trans. Roy. Soc.
London B 237: 37
10/4/2002
©Bud Mishra, 2002
b
reaction
diffusion
Cell Talk»16
Reaction-diffusion:
an example
A fed at rate F
d[A]/dt=F(1-[A])
A+2B ! 3B
B!P
B extracted
at rate F,
decay at rate k
d[B]/dt=-(F+k)[B]
reaction: -d[A]/dt = d[B]/dt = [A][B]2
diffusion: d[A]/dt=DA2[A]; d[B]/dt=DB2[B]
 [A]/ t = F(1-[A]) – [A][B]2 + DA2[A]
 [B]/ t = -(F+k)[B] +[A][B]2 + DB2[B]
Pearson, J. E.: Complex patterns in simple systems. Science 261, 189-192 (1993).
10/4/2002
©Bud Mishra, 2002
Cell Talk»17
Reaction-diffusion:
an example
10/4/2002
©Bud Mishra, 2002
Cell Talk»18
Genes: 1952
• Since the role of genes is
presumably catalytic, influencing
only the rate of reactions, unless
one is interested in comparison of
organisms, they “may be
eliminated from the discussion…”
10/4/2002
©Bud Mishra, 2002
Cell Talk»19
Crick & Watson :1953
10/4/2002
©Bud Mishra, 2002
Cell Talk»20
Genome
• Genome:
– Hereditary information of an organism is encoded
in its DNA and enclosed in a cell (unless it is a
virus). All the information contained in the DNA
of a single organism is its genome.
• DNA molecule can be thought of as a very long
sequence of nucleotides or bases:
S = {A, T, C, G}
10/4/2002
©Bud Mishra, 2002
Cell Talk»21
Genome in Detail
The Human Genome at
Four Levels of Detail.
Apart from reproductive
cells (gametes) and mature
red blood cells, every cell in
the human body contains
23 pairs of chromosomes,
each a packet of compressed
and entwined DNA (1, 2).
10/4/2002
©Bud Mishra, 2002
Cell Talk»22
DNA Structure.
The four nitrogenous bases of
DNA are arranged along the sugarphosphate backbone in a particular
order (the DNA sequence),
encoding all genetic instructions
for an organism. Adenine (A) pairs
with thymine (T), while cytosine
(C) pairs with guanine (G). The
two DNA strands are held together
by weak bonds between the bases.
10/4/2002
©Bud Mishra, 2002
Cell Talk»23
The Central Dogma
• The intermediate molecule carrying the information out of
the nucleus of an eukaryotic cell is RNA, a single stranded
polymer.
• RNA also controls the translation process in which amino
acids are created making up the proteins.
• The central dogma(due to Francis Crick in 1958) states that these
information flows are all unidirectional:
“The central dogma states that once `information' has passed into protein
it cannot get out again. The transfer of information from nucleic acid
to nucleic acid, or from nucleic acid to protein, may be possible, but
transfer from protein to protein, or from protein to nucleic acid is
impossible. Information means here the precise determination of
sequence, either of bases in the nucleic acid or of amino acid residues in
the protein.”
10/4/2002
©Bud Mishra, 2002
Cell Talk»24
RNA, Genes and Promoters
• A specific region of DNA that determines the synthesis of
proteins (through the transcription and translation) is called a
gene
– Originally, a gene meant something more abstract---a unit
of hereditary inheritance.
– Now a gene has been given a physical molecular existence.
• Transcription of a gene to a messenger RNA, mRNA, is keyed
by a transcriptional activator/factor, which attaches to a
promoter (a specific sequence adjacent to the gene).
• Regulatory sequences such as silencers and enhancers control
the rate of transcription
10/4/2002
©Bud Mishra, 2002
Cell Talk»25
Gene Expression
•When genes are expressed, the genetic
information (base sequence) on DNA is first
transcribed (copied) to a molecule of
messenger RNA, mRNA.
•The mRNAs leave the cell nucleus and enter
the cytoplasm, where triplets of bases (codons)
forming the genetic code specify the particular
amino acids that make up an individual
protein.
•This process, called translation, is
accomplished by ribosomes (cellular
components composed of proteins and
another class of RNA) that read the genetic
code from the mRNA, and transfer RNAs
(tRNAs) that transport amino acids to the
ribosomes for attachment to the growing
protein.
10/4/2002
©Bud Mishra, 2002
Cell Talk»26
Regulation of Gene Expns
• Motifs (short DNA sequences) that regulate transcription
– Promoter
– Terminator
• Motifs that modulate transcription
– Repressor
– Activator
– Antiterminator
Promoter
Terminator
10-35bp
10/4/2002
Transcriptional
Initiation
©Bud Mishra, 2002
Gene
Transcriptional
Termination
Cell Talk»27
“The Brain & the Fancy”
“Work on the mathematics of growth as
opposed to the statistical description and
comparison of growth, seems to me to have
developed along two equally unprofitable
lines… It is futile to conjure up in the
imagination a system of differential
equations for the purpose of accounting for
facts which are not only very complex, but
largely unknown,…What we require at the
present time is more measurement and less
theory.”
– Eric Ponder, Director, CSHL (LIBA), 1936-1941.
10/4/2002
©Bud Mishra, 2002
Cell Talk»28
“Axioms of Platitudes”
-E.B. Wilson
1. Science need not be mathematical.
2. Simply because a subject is mathematical it
need not therefore be scientific.
3. Empirical curve fitting may be without other
than classificatory significance.
4. Growth of an individual should not be
confused with the growth of an aggregate (or
average) of individuals.
5. Different aspects of the individual, or of the
average, may have different types of growth
curves.
10/4/2002
©Bud Mishra, 2002
Cell Talk»29
Genes for Segmentation
• Fertilisation followed by
cell division
• Pattern formation –
instructions for
– Body plan (Axes: A-P, D-V)
– Germ layers (ecto-, meso-,
endoderm)
• Cell movement - form –
gastrulation
• Cell differentiation
10/4/2002
©Bud Mishra, 2002
Cell Talk»30
PI: Positional Information
• Positional value
– Morphogen – a substance
– Threshold concentration
• Program for development
– Generative rather than
descriptive
• “French-Flag Model”
10/4/2002
©Bud Mishra, 2002
Cell Talk»31
bicoid
• The bicoid gene
provides an A-P
morphogen
gradient
10/4/2002
©Bud Mishra, 2002
Cell Talk»32
gap genes
• The A-P axis is divided into
broad regions by gap gene
expression
• The first zygotic genes
• Respond to maternally-derived
instructions
• Short-lived proteins, gives
bell-shaped distribution from
source
10/4/2002
©Bud Mishra, 2002
Cell Talk»33
Transcription Factors in Cascade
• Hunchback (hb) , a gap gene,
responds to the dose of bicoid
protein
• A concentration above
threshold of bicoid activates the
expression of hb
• The more bicoid transcripts, the
further back hb expression goes
10/4/2002
©Bud Mishra, 2002
Cell Talk»34
Transcription Factors in Cascade
10/4/2002
• Krüppel (Kr), a gap gene,
responds to the dose of hb
protein
• A concentration above minimum
threshold of hb activates the
expression of Kr
• A concentration above
maximum threshold of hb
inactivates the expression of Kr
©Bud Mishra, 2002
Cell Talk»35
Segmentation
• Parasegments are
delimited by
expression of pairrule genes in a
periodic pattern
• Each is expressed in a
series of 7 transverse
stripes
10/4/2002
©Bud Mishra, 2002
Cell Talk»36
Pattern Formation
– Edward Lewis, of the California
Institute of Technology
– Christiane Nuesslein-Volhard, of
Germany's Max-Planck Institute
– Eric Wieschaus, at Princeton
• Each of the three were involved
in the early research to find the
genes controlling development
of the Drosophila fruit fly.
10/4/2002
©Bud Mishra, 2002
Cell Talk»37
The Network of Interaction
EN
en
wg
WG
ptc
+
cid
CID
CN
hh
a cell
mRNA
proteins
10/4/2002
en
positive
interacions
WG
PTC
PTC
PH
PH
HH
HH
Cell-to-cell
interface
Legend:
•WG=wingless
•HH=hedgehog
•CID=cubitus iterruptus
•CN=repressor fragment
of CID
•PTC=patched
•PH=patched-hedgehog
complex
a neighbor
negative
interacions
©Bud Mishra, 2002
Cell Talk»38
Completeness:
von Dassow, Meir, Munro & Odell, 2000
• “We used computer simulations to investigate whether the
known interactions among segment polarity genes suffice to
confer the properties expected of a developmental module….
• “Using only the solid lines in [earlier figure] we found no such
parameter sets despite extensive efforts.. Thus the solid
connections cannot suffice to explain even the most basic
behavior of the segment polarity network…
• “There must be active repression of en cells anterior to wgexpressing stripe and something that spatially biases the
response of wg to Hh. There is a good evidence in Drosophila
for wg autoactivation…”
10/4/2002
©Bud Mishra, 2002
Cell Talk»39
Completeness
• “We incorporated these two remedies first
(light gray lines). With these links installed
there are many parameter sets that enable the
model to reproduce the target behavior, so
many that they can be found easily by random
sampling.”
10/4/2002
©Bud Mishra, 2002
Cell Talk»40
Model
hh t
HH t
PH t
EN Tmax hh
EN
1
hh t
KEN
0,
kPTCHH HH t PTC t , HH 0
0,
HHH
PH t
kPTCHH HH t PTC t
, PH 0
0, PTC t
0, PTC 0
HPH
6
Pmax hh hh t
, hh 0
Hhh
HH t
1
1
0.8
0.6
0.4
0.2
5
10/4/2002
©Bud Mishra, 2002
10
15
20
Cell Talk»41
25
30
Model Parameters
10/4/2002
©Bud Mishra, 2002
Cell Talk»42
Model
hh EN_
:
Tmax
Tmax hh Hhh EN^
1.0,
hh
KEN^
1.0, KEN
EN^
1.0,
.
4.0, Hhh
1.0 ;
? hh
Plot hh EN ,
hh EN_ :
Tmax hh Hhh EN
KEN EN
EN, 0, 2.5
. Tmax
1., hh
1., KEN
1.,
4., Hhh
1.
0.8
0.6
0.4
0.2
0.5
10/4/2002
1
1.5
©Bud Mishra, 2002
2
2.5
Cell Talk»43
Complete Model
10/4/2002
©Bud Mishra, 2002
Cell Talk»44
Complete Model
10/4/2002
©Bud Mishra, 2002
Cell Talk»45
S-system
10/4/2002
©Bud Mishra, 2002
Cell Talk»46
Graphical Representation
X2 Reversible Reaction
X1
X2
X1
X2
X1
X3
Divergence Branch Point:
Degradation processes of
X1 into X2 and X3 are
independent
X3
X1
X3
X1
X3
X2
10/4/2002
Convergence Branch
Point: Degradation
processes of X1 into X2
and X3 are independent
X2
©Bud Mishra, 2002
Single splitting reaction
generating two products
X2 and X3, in
stoichiometric
proportion.
Single synthetic reaction
involving two source
components X1 and X2, in
stoichiometric
proportion.
Cell Talk»47
Graphical Representation
X3
X4
X2
X1
The reaction between X1 and X2
requires coenzyme X3 which is
converted to X4
X3
X2
X1
The conversion of X1 into X2 is
modulated by X3
X3
X1
-
10/4/2002
X2
The conversion of X1 into X2 is
modulated by an inhibitor X3
©Bud Mishra, 2002
Cell Talk»48
Systems of Differential Equations
•
dXi/dt
= (instantaneous) rate of change in Xi at time t
= Function of substrate concentrations, enzymes, factors and
products:
•
dXi/dt = f(S1, S2, …, E1, E2, …, F1, F2,…, P1, P2,…)
E.g. Michaelis-Menten for substrate S & product P:
1. dS/dt = - Vmax S/(KM + S)
2. dP/dt = Vmax S/(KM + S)
10/4/2002
©Bud Mishra, 2002
Cell Talk»49
General Form
• dXi/dt = Vi+(X1, X2, …, Xn) – Vi-(X1, X2, …, Xn):
– Where Vi+(¢) term represents production (or
accumulation) rate of a particular metabolite and Vi-(¢)
represent s depletion rate of the same metabolite.
• Generalizing to n dependent variables and m
independent variables, we have:
dXi/dt =
Vi+(X1, X2, …, Xn, U1, U2, …, Um)
– Vi-(X1, X2, …, Xn, U1, U2, …, Um):
10/4/2002
©Bud Mishra, 2002
Cell Talk»50
Canonical Forms
• S-systems result in Non-linear Time-Invariant DAE
System.
• Note that: Given a system of equations with f and g
being arbitrary rational functions, we can transform
the system into a set of Differential Binomial
Equation System with Linear Constraints:
dxi/dt = a x1a1L xnan - b x1b1L xnbn
& g1 x1 + L gn xn = 0
10/4/2002
©Bud Mishra, 2002
Cell Talk»51
Transformation I
• Assume that an equation is given as
• dx/dt = p(x(t), u(t))/q(x(t), u(t))
– A rational function. p & q are polynomials
– p(x(t), u(t)) = a1 m1 + L + ak mk - b1 p1 - L - bl pl
– where m’s and p’s are power-products with arbitrary power.
a’s and b’s are positive-valued.
dx/dt = p(x(t), u(t)) y(t)-1,
dc/dt = q(x(t), u(t)) – y(t),
c = 0.
10/4/2002
©Bud Mishra, 2002
Cell Talk»52
Transformation II
• dx/dt = a1 m1 + L + ak mk - b1 p1 - L - bl pl
= (a1 m1 – w(t)/k) + L + (ak mk – w(t)/k)
– (b1 p1 - w(t)/l) - L - (bl pl - w(t)/l)
• Equivalent System
x(t) - g1(t) - L - gk(t) + gk+1(t) + L + gk+l(t) = 0
dgi/dt = ai mi – w(t)/k , 1 · i · k
dgj/dt = b1 p1 - w(t)/l , k+1 · j · k+l
10/4/2002
©Bud Mishra, 2002
Cell Talk»53
Canonical Forms
10/4/2002
©Bud Mishra, 2002
Cell Talk»54
Cascade Model: Repressilator?
x1
-
dx2/dt = a2 X6g26X1g21 - b2 X2h22
dx4/dt = a4 X2g42X3g43 - b4 X4h44
dx6/dt = a6 X4g64X5g65 - b6 X6h66
X1, X3, X5 = const
x2
x3
-
x4
x5
10/4/2002
-
x6
©Bud Mishra, 2002
Cell Talk»55
How Stable is This???
10/4/2002
©Bud Mishra, 2002
Cell Talk»56
Synergy of Tools
• Exploit the special structure of Pathways Models
and of ‘traces' to create a synergy among different
conceptual components
•ODEs (XS-systems canonical form)
•Temporal Logic
•Time Series Analysis
•Symbolic Mathematics
10/4/2002
©Bud Mishra, 2002
Cell Talk»57
S-System Automaton AS
• S-System Automata Definition:
– Combine snapshots of the IDs (“instantaneous descriptions”) of the
system to create a possible world model
– Transitions are inferred from “traces” of the system variables:
• Definition:Given an S-systems S, the S-system automaton AS
associated to S is 4-tuple AS = (S, D, S0, F), where S µ D1 £ L
£ DW is a set of states, D µ S £ S is the binary transition relation,
and S0, F ½ S are initial and final states respectively. 
• Definition: A trace of an S-system automaton AS is a sequence
s0, s1, …, sn,…, such that s0 2 S0, D(si, si+1), 8 i = 0.
10/4/2002
©Bud Mishra, 2002
Cell Talk»58
Trace Automaton
Simple one-to-one construction of the
“trace” automata AS for an S-system S
10/4/2002
©Bud Mishra, 2002
Cell Talk»59
State Collapse
• Definition: The relation Rd holds between two states
sk = X(t + k q) and sk+j = X(t + (k+j) q),
iff 8 i 2 {1, …, n+m},
| dX/dt(t + k q) - dX/dt(t + (k+j) q) | · d. 
10/4/2002
©Bud Mishra, 2002
Cell Talk»60
Collapsing Algorithm
10/4/2002
©Bud Mishra, 2002
Cell Talk»61
Collapsed Automata
The effects of the collapsing construction of the
“trace” automata AS for an S-system S
10/4/2002
©Bud Mishra, 2002
Cell Talk»62
SimPathica System
10/4/2002
©Bud Mishra, 2002
Cell Talk»63
Modal Logic Queries
10/4/2002
©Bud Mishra, 2002
Cell Talk»64
SimPathica:
Trace Analysis System
10/4/2002
©Bud Mishra, 2002
Cell Talk»65
SimPathica
10/4/2002
©Bud Mishra, 2002
Cell Talk»66
Computational
Differential Algebra
10/4/2002
©Bud Mishra, 2002
Cell Talk»67
Algebraic Approaches
10/4/2002
©Bud Mishra, 2002
Cell Talk»68
State Space Description
10/4/2002
©Bud Mishra, 2002
Cell Talk»69
Input-Output Relation
10/4/2002
©Bud Mishra, 2002
Cell Talk»70
Differential Algebra
10/4/2002
©Bud Mishra, 2002
Cell Talk»71
Related Problems
10/4/2002
©Bud Mishra, 2002
Cell Talk»72
Example System
10/4/2002
©Bud Mishra, 2002
Cell Talk»73
Input-Output Relations
10/4/2002
©Bud Mishra, 2002
Cell Talk»74
Membership Problem
10/4/2002
©Bud Mishra, 2002
Cell Talk»75
Obstacles
10/4/2002
©Bud Mishra, 2002
Cell Talk»76
Some Remarks
• Many problems of Kinetic modeling lead naturally to
formulation in Differential Algebra!
• Yet, most problems in Differential Algebra remain to
be solved satisfactorily!!
– Many of the tools developed in the algebraic setting (e.g.,
Gröbner bases, elimination theory, etc.) do not generalize.
– Complexity and solvability questions pose intriguing and
challenging problems for applied mathematicians and
computer scientists!!
10/4/2002
©Bud Mishra, 2002
Cell Talk»77
Isaac Newton
“I know not what I appear to the world,
but to myself
I seem to have been only like a boy playing
on the sea-shore,
and diverting myself in now and then
finding a smoother
pebble or a prettier shell,
whilest the great ocean of truth lay all
undiscovered
before me.”
Quoted in D Brewster, Memoirs of Newton
10/4/2002
©Bud Mishra, 2002
Cell Talk»78
The End
http://www.cs.nyu.edu/mishra
http://bioinformatics.cat.nyu.edu
Valis, Gene Grammar, NYU MAD, Cell
Simulation,…
10/4/2002
©Bud Mishra, 2002
Cell Talk»79