Transcript (1/2 * X) + - The Circuits and Biology Lab at UMN

Writing and Compiling Code
into Biochemistry
Marc Riedel
Assistant Professor, Electrical and Computer Engineering
Graduate Faculty, Biomedical Informatics and Computational Biology
University of Minnesota
PSB ─ Kona, Hawaii, Jan. 7, 2010
Acknowledgements
Adam Shea
Brian Fett
Students
Electrical & Computer Engineering
University of Minnesota
Keshab Parhi
Distinguished McKnight
University Professor;
Edgar F. Johnson Professor;
Electrical & Computer Engineering
University of Minnesota
Who
is this guy?
Acknowledgements
• Most of the cells in his body
are not his own!
• Most of the cells in his body
are not even human!
• Most of the DNA in his body
is alien!
“Minnesota Farmer”
Who is this guy?
He’s a human-bacteria hybrid:
[like all of us]
• 100 trillion bacterial cells of
at least 500 different types
inhabit his body.
vs.
• only 1 trillion human cells of
210 different types.
“Minnesota Farmer”
Who
What’s
is in
this
hisguy?
gut?
He’s a human-bacteria hybrid:
[like all of us]
• 100 trillion bacterial cells of
at least 500 different types
inhabit his body.
vs.
• only 1 trillion human cells of
210 different types.
“Minnesota Farmer”
What’s in his gut?
“E. coli, a self-replicating object only a thousandth of a
millimeter in size, can swim 35 diameters a second, taste
simple chemicals in its environment, and decide whether life is
getting better or worse.”
– Howard C. Berg
About 3 pounds of bacteria!
We should put
these critters to
work…
“Stimulus, response! Stimulus
response! Don’t you ever think!”
Synthetic Biology
• Positioned as an engineering discipline.
– “Novel functionality through design”.
– Repositories of standardized parts.
• Driven by experimental expertise in
particular domains of biology.
– Gene-regulation, signaling, metabolism,
protein structures …
Biochemistry in a Nutshell
Nucleotides:
{ A, C , T , G}
DNA: string of n nucleotides (n ≈ 109)
... ACCGTTGAATGACG...
Amino acid: coded by a sequence of 3 nucleotides.
{ A, C , T , G }3  {a1 , , a20 }
Proteins: produced from a sequence of m amino
acids (m ≈ 103) called a “gene”.
{a1 , , a20 } m  protein
Playing by the Rules
Biochemical Reactions: how types of molecules combine.
2a +
+
b
c
Biochemical Reactions
+
proteins count
cell
9
8
6
5
7
9
Discrete chemical kinetics; spatial homogeneity.
Biochemical Reactions
Relative rates or (reaction propensities):
slow
+
medium
+
fast
+
Discrete chemical kinetics; spatial homogeneity.
[computational]
Biochemical
Biochemistry
[computation]
x
Protein-Protein
Chemistry
y
z
quantity
quantities
Multiplication
pseudo-code
biochemical code
Exponentiation
pseudo-code
biochemical code
Raising-to-a-Power
pseudo-code
biochemical code
Rate Independent
Biochemical Computation
[nearly]
Biochemical rules are inherently parallel.
Sequentialize?
Step 1:
M1
g = f1 (r )
Mario
Step 2:
then
M2
b = f2 (g)
Luigi
slow
Module
Locking
slow
+
Sequentialize
computation
with only two rates:
“fast” and “slow”.
slow
slow
+
slow
+
fast
+
Example: Multiplication
Lock phases or
modules with keys.
Keys are generated
by keysmiths; but
indicators consume
keysmiths.
Key Generation
Two-phase protocol to ensure
only one type of key is present.
Design Automation for Integrated Circuits
Behavioral Specification
(e.g., DSP function)
Register
Level
Design
Structural Description
(e.g., memory and functional units)
Logic
Synthesis
Circuit-Level Description
(e.g., NAND2 and D flip-flops)
SPICE
waveforms
Design Automation for Integrated
Biochemistry
Circuits
Behavioral Specification
(e.g., DSP function)
Register
Level
Design
Structural Description
(e.g., memory and functional units)
Logic
Biochemical
Synthesis
Verilog
Elements of
Register-based
Brian’s
Automated Modular
Biochemical
computation
Biochemical Instantiator
Biochemical Netlist
(e.g., Proteins, Enzymes)
SPICE
STA
Engine
SSA
waveforms
“Stochastic Transient Analysis of Biochemical Systems”
Example: FIR Filter
Two-Tap Moving-Average Filter:
X
1/α=
1/β=
Y
Example: FIR Filter
Two-Tap Moving-Average Filter:
module MA(X, Y);
input X;
output Y;
reg Xn;
always
begin
Y = (1/2 * X) +
(1/2 * Xn);
Xn = X;
end
endmodule
Example: FIR Filter
module MA(X, Y);
input X;
output Y;
reg Xn;
always
begin
Y = (1/2 * X) +
(1/2 * Xn);
Xn = X;
end
endmodule
Example: FIR Filter
module MA(X, Y);
input X;
output Y;
reg Xn;
always
begin
Y = (1/2 * X) +
(1/2 * Xn);
Xn = X;
end
endmodule
Example: FIR Filter
module MA(X, Y);
input X;
output Y;
reg Xn;
always
begin
Y = (1/2 * X) +
(1/2 * Xn);
Xn = X;
end
endmodule
Example: FIR Filter
module MA(X, Y);
input X;
output Y;
reg Xn;
always
begin
Y = (1/2 * X) +
(1/2 * Xn);
Xn = X;
end
endmodule
Example: FIR Filter
module MA(X, Y);
input X;
output Y;
reg Xn;
always
begin
Y = (1/2 * X) +
(1/2 * Xn);
Xn = X;
end
endmodule
Example: FIR Filter
module MA(X, Y);
input X;
output Y;
reg Xn;
always
begin
Y = (1/2 * X) +
(1/2 * Xn);
Xn = X;
end
endmodule
Example: FIR Filter
Two-Tap Moving-Average Filter:
Chemical Design:
Filter
Example: FIR Filter
Two-Tap Moving-Average Filter:
Example: IIR Filter
Biquad versatile infinite-impulse responses filter:
Example: IIR Filter
Biquad versatile infinite-impulse responses filter:
Example: IIR Filter
Example: IIR Filter
Example: IIR Filter
Stochastic Kinetics
The probability that a given
reaction is the next to fire is
proportional to:
• Its rate.
• The quantities of its reactants.
+
k1
k2
+
+
k3
See D. Gillespie, “Stochastic Chemical Kinetics”, 2006.
It’s not a bug, it’s a feature.
Synthesizing Biological
Computation
inputs
computation
outputs
Molecular
Triggers
Biochemical
Reactions
Molecular
Products
Biological Computation at the
Populational Level
How can we control the quantity of molecular product at the
populational level?
Synthesizing Stochasticity
Engineer a probabilistic response in each cell.
product
with Prob. 0.3
trigger
product
with Prob. 0.7
Biological Computation at the
Populational Level
Obtain a fractional response.
[stochastic] Biological
Computation
X
Biochemical
Reactions
Y
fixed
 X 
Z with Pr 
 X + Y 
Discussion
Computational Chemical Design
vis-a-vis
Technology-Independent Logic Synthesis
• Synthesize a design for a precise, robust, programmable
probability distribution on outcomes – for arbitrary types
and reactions.
Experimental Design
vis-a-vis
Technology Mapping in Circuit Design
• Implement design by selecting specific types and
reactions – say from “toolkit”.
DNA Strand Displacement
X1
X2 + X3
Erik Winfree’s group at Caltech: “DNA as a Universal
Substrate for Chemical Kinetics.”
Discussion
Where are we?
• Methods and CAD tools for generating nearly rate
independent biochemical netlists for: nearly any
memoryless function (e.g., curve-fitting).
• Methods for generating any register-to-register
computation (e.g., DSP functions).
Where are we headed?
• A technology-independent biochemical CPU.
Support
MARCO (SRC/DoD)
Contract 2003-NT-1107
CAREER Award
0845650
Blue Gene Development
Group. Rochester, MN
Biomedical Informatics &
Computational Biology
UMN / Mayo Clinic / IBM
Playing by the Rules
Stochastic Chemical Kinetics
The probability that a given
reaction is the next to fire is
proportional to:
• Its rate.
• The number of ways that the
reactants can combine.
R1
R2
R3
k1
2A + B  3 C
k2
B + 2C 
3A
k3
A + C  2B
See Dan Gillespie,
• “Exact Stochastic Simulation of Coupled Chemical Reactions,”1977.
• “Stochastic Chemical Kinetics,” 2006.
S1 = [5, 5, 5] 0
R1 R2
R3
Stochastic Simulation
Algorithm (SSA)
Ri
ki
ni ,1 X i ,1 + ni , 2 X i , 2 +  
Choose the next reaction
according to:
i
Pr( Ri ) =
 j
j
where
 X 1  X 2 

 i = k i  
 n1  n2 
S1 = [5, 5, 5] 0
R1 R2
R3
Stochastic Simulation
Algorithm (SSA)
Ri
ki
ni ,1 X i ,1 + ni , 2 X i , 2 +  
Choose the time of the next
reaction according to:
Pr(t  t0 ) = 
t0
 =0
 je
j





j

 j 


d
S1 = [5, 5, 5] 0
Stochastic Simulation
Algorithm (SSA)
Choose R3 and t = 3 seconds.
R1 R2
R3
S2 = [4, 7, 4] 3
Choose R1 and t = 1 seconds.
S3 = [2, 6, 7] 4
Choose R3 and t = 2 seconds.
S4 = [1, 8, 6] 6
Choose R2 and t = 1 seconds.
S1 = [5, 5, 5] 0
Stochastic Simulation
Algorithm (SSA)
Choose R3 and t = 3 seconds.
S2 = [4, 7, 4] 37
Choose R1 and t = 1 seconds.
S3 = [2, 6, 7] 4
Choose R3 and t = 2 seconds.
S4 = [1, 8, 6] 6
Choose R2 and t = 1 seconds.