Transcript brief talk

Branching in Biological
Models of Computation
Blair Andres-Beck, Vera Bereg, Stephanie Lee,
Mike Lindmark, Wojciech Makowiecki
Branching in DNA Computation
We chose several models of DNA
computation and examined the
implementation of if…else statements and
looping
Allow easier mapping of conventional
algorithms
Design Criteria
Any change must preserve the existing
functionality of the model
Branching
– Operation selection based on current data
and instruction
Looping
– Further instructions based on test condition
– Nested loops; that is, looping that doesn’t rely
on a single marker
The Sticker Model
Presented in “A Sticker Based Model for
DNA Computation” (1996)
Two types of single stranded DNA
molecules
– memory strand
– complimentary stickers
Four operations allow universal
computation
– set, clear, separate and combine
Bit Representation
Set and Clear
Combine and Separate
Simple branching and looping in
the Sticker Model
Idea: use current mechanical
operations to do branching
(if else) and looping
Branching with existing operations
Perform a separate based on branch
condition
Act on each vial independently
– “If” statement carried out on true, “else” on
false
Recombine vials after “if” statement
Branching and Looping procedures
Looping with existing operations
Test for loop condition
– Fluorescent markers
Can be detected by the robotic assistant
Can have more than one type, allowing nested looping
Choose next instruction based on presence or
absence of fluorescence
Problems
– Slow
– Reliance on intervention outside the model
Implementation of Branching in
DNA Transcriptional Logic
Idea: use an OR gate for branching 
DNA Transcriptional Logic
How it works
– Transcription factor binds to the promoter region
– Activates the enzyme RNA Polymerase [RNAP]
– Unzips DNA and produces programmable output
Implementation of Branching
The OR gate allows the if-else statement to end and the program to continue
Definition of Branching
Branching allows for conditional if-else
statements
{
if (condition)
{output 1};
else
{output 2};
}
continuation …
Properties of the Branching
Pros
– Easy to track progress
– Does not require outside intervention
Cons
– Does not allow parallelism
– Inefficient and fairly slow
– Requires large number of promoter -transcription
factor pairs
“Smart” drug or DNA automata
combined with Sticker Model
Idea: use “if else” statements from
“Smart” drug model (with stickers
instead of drugs)
Automata
Automata
– Machine that accepts strings over specific alphabet
that are in its language
– Computation terminates on processing last string
symbol
– Accepts input if terminates in accepting state
“Smart” Drug
Automata with:
– Hardware (restriction nuclease, ligase)
– Software (dsDNA with a hairpin structure at
end)
– In vitro
“Smart” Drug
Basic Idea: transport diagnosis and drug
delivery (suppression) stages into the cell
No robotic intervention what-so-ever
Basic “if else” statements, thus can do
branching! 
“Smart” Drug
“Smart” drug and Sticker Model
Sticker model:
– Memory strand with on/off regions for bits
Drug model:
–
–
–
–
Code with a sticker as hairpin (software)
Reusable “rules” (hardware)
If (rule=true)  release sticker
Can do anti-stickers to clear off bits as well 
Thus SISD model
By varying code and subset of “rules” can
change the outcome of the computation
Pros and Cons
Less mechanical operations used
– Separation procedure might not be needed
– Could possibly get rid of them all together?
Eliminates one of the positive sides of
sticker model (no enzymes), but our
enzymes are reusable (hardware)
Have SISD, can do MIMD?
How to ensure that each code is related to
its specific data molecule?
Branching in the Sticker Model
using DNA Instructions
The Idea: Store the program with the
data, run all the programs
independently.
Basic Ideas
Encode instructions into DNA
Create a DNA program counter
Each DNA computes cycle:
– Separate strands based on next instruction
– Perform operation
– Increment PC
Changes to the Sticker Model
Instruction strand = head + instruction + …
+ data connector
Instruction = instr code + operand code
Changes to the Sticker Model
Add connector to data strand
Addition of PC strands
Changes to the Sticker Model
Introduction of halt
No explicit combine or separate operations
Use of operation selectors
Adding Looping
Looping by restarting the PC
Loop operation
– Clears off PC using complement PC strands
if (stage1) {
…
if (NOT done) {
loop;
}
…
stage1 = false;
}
Adding Branching
Add IF instruction code
Use End-If IF operation
Operation selectors with solid-bound
stickers
Trapped strands enter branching cycle
– Addition of excess PC and Step strands
(excluding PC End-If IF strands)
– Flow by End-If IF selectors
– Return trapped strands
The Strands
Advantages
Reusability of data, pc, start, step, and
selector strands
Simple programmability
– Imagine building strand from instruction
pieces
Ability to run more than one program
concurrently
– Thousands of problems at the same time
Disadvantages
Large error rate vs. long cycle time
– Must perform several separations per cycle
No ability to do error correction
Large number of unique sequences
needed
References
A Sticker Based Architecture for DNA Computation. Roweis, Sam, et. al.
7/96.
Lauria, Mario, Kaustubh Bhalerao, Muthu M. Pugalanthiran, and Bo Yuan.
“Building blocks of a biochemical CPU based on DNA transcription logic.”
3rd Workshop on Non-Silicon Computation (NSC-3), Munich, June 2004.
Molecular Beacons: A Novel DNA Probe for Nucleic Acid and Protein
Studies. W. Tan et al.
Molecular beacons attached to glass beads fluoresce upon hybridization to
target DNA. L.Brown et al.
Automata Make Antisense. Condon, Anne. Nature, vol 429, p351.
Programmable and Autonomous Computing Machine Made of
Biomolecules. Y. Benenson, T. Paz-Elizur, R. Adar, E. Keinan, Z. Livneh, E.
Shapiro. Nature, vol. 414, p430.
An Autonomous Molecular Computer for Logical Control of Gene
Expression. Y. Benenson, B. Gil, U. Ben-Dor, R. Adar, E. Shapiro. Nature,
vol.429, p432.
The Strands
Execution Cycle Revisited
Initial Setup
– Random input bits set
– Add instruction strands, start strands
Execution Cycle
– Flow strands by operation selector chambers
– Seal chambers, perform operation
– Collect, add PC strands
– Wash PC strands, add step strands
Adding Branching
Add IF instruction code where operand is
the condition bit
Use End-If IF operation
Operation selectors with solid-bound
stickers
Proper length to require both connections
to stick
Adding Branching
Trapped strands enter branching cycle
– Addition of excess PC and Step strands
(excluding PC End-If IF strands)
– Flow by End-If IF selectors
– Return trapped strands
Simple to get OR and NOT conditions
– ie. OR = clear c; set n; if a; set c; end-if if n; if
b; set c; end-if if n;
Fluorescent markers
F
Hybrid
Q
Target
Heat, pH, Denature reagents
Q
Q
F
F