Transcript AQUEOUS COMPUTING - Writing on Molecules

AQUEOUS COMPUTING
- Writing on Molecules T. Head, M. Yamamura, and S. Gal
Binghamton University
1. Introduction
 The
only way to compute with DNA?
1 design sequences for DNA molecules
2 order many custom DNA molecules
3 anneal and filter
( 4 if failure goto 1 )
↓
 Aqueous computing
– framework for using molecular memory
– laboratory implementation
7/9/99
CEC'99
2
Molecular Memory
Memory
Address
Content
LSI
HD
DNA
wired grid
head pos.
specific subsequence
electronic
magnetic
1. molded together
2. fixed on solid materials
3. serial processing
markings on molecules
1. individual access
2. randomize location
3. parallel processing
easily separate
mix again
AQUEOUS
7/9/99
CEC'99
3
2. Mathematical Basis
 Common
algorithmic problem (CAP)
– a description of the pattern of the problem
 Aqueous
algorithm
– a way to use molecular memory
7/9/99
CEC'99
4
Common algorithmic problem
 CAP
given
S: finite set
F ⊂2S (the forbidden subsets)
find the largest cardinal number n for which there is a
subset T of S for which: |T|=n, ∀U∈F U⊂T.
– NP-complete problems having the CAP pattern
» maximum independent set
» minimum vertex cover
» Hamiltonian cycles
» Boolean satisfiability, etc.
7/9/99
CEC'99
5
Example
 Maximum
independent set problem
given: G=(V, A)
(the arcs are forbidden)
find max |T| s.t. TV ,∀x,y∈T, {x,y}∈A
Find max # of animals
you can keep in one
cage?
7/9/99
CEC'99
6
Aqueous Algorithm
Initialize;
For each {s1, s2, ..., sk} in F Do
Pour (k)
1: SetToZero( s1 )
2: SetToZero( s2 )
...
k: SetToZero( sk )
Unite
EndFor;
MaxCountOfOnes
7/9/99
CEC'99
7
Example
Initialize: 111
Pour(2)
a
b
c
SetToZero(a)
SetToZero(b)
011
101
Pour(2)
SetToZero(b)
SetToZero(c)
001,101
010,100
MaxCountOfOnes: 2
001,101,010,100
7/9/99
CEC'99
8
3. Biomolecular Implementation
 DNA modification
enzymes
– how to write on molecules
 DNA plasmid
– use of bacteria and blue/white selection
7/9/99
CEC'99
9
Write on molecules
 Restriction
enzyme
– cuts DNA at a specific subsequence (site)
5’-TATCGA-3’
3’-ATAGCT-5’
↓ Hind III
5’-T
ATCGA-3’
3’-ATAGC
T-5’
 Circular
DNA + modification enzymes
– Bit =1 (site exists), =0 (no site)
7/9/99
CEC'99
10
Cut/fill/paste
5’-TATCGA-3’
3’-ATAGCT-5’
cut
↓
5’-T
ATCGA-3’
3’-ATAGC
T-5’
fill
↓
5’-TATCG ATCGA-3’
3’-ATAGC TAGCT-5’
paste
↓
5’-TATCGATCGA-3’
3’-ATAGCTAGCT-5’
7/9/99
CEC'99
Bit=1, circular
restriction enzyme
linear
DNA polymerase
DNA ligase
Bit=0, circular
11
Cloning with DNA plasmid
 DNA plasmid
– circular, double stranded
– set of unique sites
» multiple cloning site (MCS)
 transform
to bacteria
– useful genes
» antibiotics resistance (ex.ampr)
» coloring matters (b-galactosidase)
NotI
XbaI SpeI BamHI XmaI PstI EcoRI EcoRV HindIII ...
5’-GCGGCCGCTCTAGAACTAGTGGATCCCCCGGGCTGCAGGAATTCGATATCAAGCTTATCGAT-3’
3’-CGCCGGCGACATCTTGATCACCTAGGGGGCCCGACGTCCTTAAGCTATAGTTCGAATAGCTA-5’
7/9/99
CEC'99
12
Genetic code translation
 Genetic
code
– translated into a series of amino acids by groups
of 3 base pairs (codon)
 Reading
frame
– 3 different meanings
ex)
7/9/99
5’-GCTCTAGAACTAGTGGATCCCCCGGGCTGCAGGAATTCGATATC
A L E L V D P P G C R N S I
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
(under construction)
CEC'99
13
Blue / white selection
 initial
DNA plasmid
express b-galactosidase gene → blue
↓
 1st
cut/fill/paste
+4bp ⇒ reading frame shift → white
↓

2nd cut/fill/paste
+8bp ⇒ reading frame still shift → white
↓
 3rd
cut/fill/paste
+12bp ⇒ readinf frame restored → blue
» useful as a debugging tool
7/9/99
CEC'99
14
Blue/white example
7/9/99
CEC'99
15
Preliminary results
pBSK
XbaI
BamHI
HindIII
GCTCTAGAACTAGTGGATCCCCCGGGCTGCAGGAATTCGATATCAAGCTTATCGATACCGTCG
A L E L V D P P G C R N S I S S L S I P S
[H]
GCTCTAGAACTAGTGGATCCCCCGGGCTGCAGGAATTCGATATCAAGCTAGCTTATCGATACC
A L E L V D P P G C R N S I S S stop
[HB]
GCTCTAGAACTAGTGGATCGATCCCCCGGGCTGCAGGAATTCGATATCAAGCTAGCTTATCGA
A L E L V D R S P G L Q E F D I K L A Y R
[HBX] GCTCTAGCTAGAACTAGTGGATCGATCCCCCGGGCTGCAGGAATTCGATATCAAGCTAGCTTA
A L A R T S G S I P R A A G I R Y Q A S L
sample blue / white
accuracy
[H]
4 / 40
87%
[HB]
3 / 80
96%
[HBX]
97 / 17
85%
7/9/99
SetToZero
->
->
CEC'99
Hind III
BamH I
Xba I
16
Example
a
b
c
[HB] (+8, white)
a=0
(SpeI)
b=0
(XhoI)
b=0
(XhoI)
c=0
(XbaI)
7/9/99
mix; +12 & +16
(solution = +12, white)
0 +4 +8 +12
under construction
CEC'99
17
4. Discussion
 Advantages
as DNA computing
– start with one DNA plasmid
» no custom DNA for individual problem
– amplify in bacteria
» blue/white selection as debugging tool
» preserving the distribution of DNA plasmids
7/9/99
CEC'99
18
5. Conclusion
 Molecular
Memory
– Aqueous Algorithm
» general framework to use molecular memory
– Cut/fill/paste
» laboratory implementation
 Further
issues
– scale up & speed up
– new algorithm fits bacteria
7/9/99
CEC'99
19
International Connection
Binghamton
University
(USA)
Aqueous Computing
Leiden
University
(Netherlands)
7/9/99
Tokyo Institute of
Technology
(Japan)
CEC'99
20
Acknowledgement
 Xia
Chen & Shalini Aggarwal in S.Gal
Laboratory at Binghamton University
 NSF CCR-9509831
 DARPA/NSF CCR-9725021
 JSPS-RFTF 96100101
 LCNC at Leiden University
7/9/99
CEC'99
21