Transcript DNA 5, MIT, MA

A Mechanical Turing Machine:
Blueprint for a Biomolecular Computer
Udi Shapiro
Ehud Shapiro
“One can imagine the eventual emergence of a
general purpose computer consisting of nothing
more than a single macromolecule conjugated
to a ribosomelike collection of enzymes that act
on it”.
--- Len Adelman, 1994.
Scaling electro and bio devices
 = 0.25 micron
in Pentium II
1 micron
E. Coli
E. Coli
E. Coli internals
(1Mbyte)
Ribosomes in operation
Ribosomes translate RNA to Proteins
RNA Polymerase transcribes DNA to RNA
Ribosomes in operation
(= protein)
Computationally: A stateless string transducer from the RNA alphabet of nucleic acids
to the Protein alphabet of amino acids
Scaling the Ribosome
25 nm
Transfer RNA
Ribosome Components
A Loaded Ribosome
Protein construction (0)
Protein construction (1)
Protein construction (2)
Protein construction (3)
The Turing Machine
1900 Hilbert Posed a Problem


23rd: Find a method for deciding the truth or
falsity of any statement of predicate calculus
(decision procedure)
Part of larger program to establish all of
mathematics on solid formal foundation, by
proving every mathematical theorem
mechanically from “first principles” (first order
logic and elementary set theory)
1936 Turing had an answer...



Hilbert’s 23rd problem has no solution, i.e.,
there is no such procedure
The proof required to formalize the notion of
a procedure
So Turing defined a “pencil-and-paper”
computation device, now called the Turing
Machine

and established its universality (Church-Turing
thesis)
The Turing Machine
INFINTE TAPE
D AT A
Read/Write Head may read
and/or write a symbol, and
move one cell to the left or
to the right
S7
Tape Cell may contain
one symbol of a given
tape alphabet
Finite Control may be in one of finitely
many states S0,S1,…,Sn
Transitions



If the control is in state S and the read/write
head sees symbol A to the left [right], then
change state to S’, write symbol A’, and move
one cell to the left [right].
S,A  A’,S’ or
A,S  S’,A’ where A can be “blank”
Configuration
A
B
S
C
D
State symbol and location of read/write head
Alphabet tape symbols
S0
A
Initial configuration
B
C
D
Example Control Program:
Well-formed Expressions



Accept well-formed expressions over “(“ and “)“
(), (()), ()(), (())() are well-formed, ((), )(, ()), ()()(,
are not.
States:
• S0: Scanning right, seeking right parenthesis
• S1: Right paren found, scan left seeking left paren.
• S2: Right end of string found, scan left, accept if no excess
parens found.
• S3: Accept
Example computation
S0
(
( (
#
Scan right to first )
#
Scan left to first (
#
Scan right to first )
Scan left to left paren
Stop, not accepting
Example Control Program:
Well-formed Expressions








S0,(  (,S0
S0,# ,  #,S0
S0,)  #,S1 (erase right paren and enter S1)
S0,blank  #,S2 (end of string, enter S2)
(,S1  S0,# (erase left paren and enter S0)
#,S1  S1,#
#,S2  S2,#
blank,S2  S3,# (end of string, enter S3)
S0
Movie
(
)
)
A Mechanical Turing Machine
Device Components
Alphabet monomers
Transition monomers
Control
Alphabet Monomers
Side group representing symbol
A
Left Link
A
B
C
Right Link
Alphabet Monomer
Alphabet Polymer
D
Transition Molecules
S’
Transition Molecule for
A,S  S’,X
A


S
One side group representing target state S’
Three recognition sites: source state S, source
symbol A, target symbol A’
Transition Molecules
S’
S’
A
S
S
Transition Molecule for
A
Transition Molecule for
A,S  S’,X
S,A  X,S’
S’
A’
A
S
A Loaded Transition Molecule for
A,S  S’,A’
Example Configuration
A
B
S’
S
A
C
D
Example Configuration
Current state
Tape polymer
A
B
C
S2 E
D
D
S1
S1
Trace polymer
S0
S0
The device in operation: Before
Example Transition: Before
A
B
S0 S0
D
D
S1 S1
C
C
S3
S2
S2
F
E
The device in operation: After
Example Transition: After
A
B
S0
S0
D
S1
D
S1
C
C
S3
S2
S2
F
E
Example Control Program:
Well-formed Expressions
(
S0
#
S0
#
S1
S0
(
S0
#
S0
#
S2
)
S0
b
S3
#
b
S2
#
S1
#
S2
#
(
S1
#
S1
#
S2
2
S0
Example Computation
S0
S0
L
L
R
R
L
S0
We show only “good” random moves
Movie
Example Trace Polymer
A
S’
A’
A
A
S
S’
A’
A
A
S
S’
A’
A
S
A
S’
A’
S
A
Implementation
Implementation
Alphabet Molecules
Transition Molecules
A Transition
4
3
1
1
4
5 6
3
5 6
2
2
Before
After
The Device
A
4
3
1
5
2
B
1a
2a
1b
2b
3a 5a 4a
3b
3a
4a
5a
4b
5b
5b
4b
Front
Back
3b
Device ~ Ribosome





Both operate on two polymers symultaneously
Tape polymer ~ messenger RNA
Transition molecule ~ transfer RNA
Trace polymer ~ Polypeptide chain
Move one cell per transition ~ Move one codon per
transition
Device is unlike the Ribosome




Read/write tape vs. Read-only tape
Transition molecule with side group vs. transfer RNA
without side group
Move in both directions vs. Move in one direction
Trace polymer made of transition monomers vs.
Polypeptide chain made of amino acids
Interaction: Input



Device suspends if needed molecules are
not available
Non-deterministic choices can be affected
by availability of molecules
Hence device can be sensitive to chemical
environment
Interaction: Output



Device extended with transition that
cleaves the tape polymer and releases one
part to the environment
Hence device can synthesize any
computable polymer of alphabet molecules
If alphabet monomers are ribonucleic
acids, cleaved segment can be used as
messenger RNA
Applications



Universal programmable computing device
that can operate in vivo
Can interact with biochemical
environment, be part of biochemical
pathways
Can be “sent on a mission”, detect and
respond
Reversibility



No “erase” operation; displaced alphabet
monomers are kept in the history tape
Computer can be made reversible
Answers Bennett’s requirements
Error Detection and Correction



Cascade several computer along history
polymer
Each computer checks computation of
previous computer, aborts/corrects errors
Only last computer produces visible output
Related work



C. H. Bennett 1970• “Assignment considered (thermodynamically)
harmful”
• Reversible computation is the answer
• “Hypothetical Enzymatic Turing machine”
L.M. Adelman et al. 1994• DNA Computing
• “Biological steps” (outside intervention)
• Self-assembly (tiling)
S. A. Kurtz et al. 1997
• Hypothetical modified ribosome implements string
rewriting on RNA