Science Vol 268 #5210 28, April 1995
+ A Boom in Plans for DNA Computing
-Leonard Aldeman
-Tailor-made approach to attacking one specialized problem.
-Princeton U.
-COMPUTING W/ DNA
-Apply techniques of Molecular biology to computational problems from cracking codes to a universal computer.
= a device to carry out any combo of logic + artihmetic operations.
-A scheme to use DNA to solve a problem that requires searching a universe of solutions so large it would defeat any conventional computer.
-Chance to perform billions of operations simultaneously vs only a few thousand parallel operations in even the most advanced electronic computers.
-A flag holds 10^19-10^20 strands of DNA each encoding astring of data in its sequence of nucleotides.
-Data is manipulated w/ molecular biology -> split, combine, copy, extract strand
-Each manipulation minutes/hours vs microseconds but operation done to all DNA in flask at once.
SAT PROBLEM
-Many scientists said "this is dumb"
-Lipton applied to difficult computational task - Satisfaction problem (SAT)
-Start w/ strands representing all possible solutions, then discard the ones which don't work.
-Shows DNA computer = a powerful search machine. combing through astronomical #s of possible answers to find the correct one.
DES
-Used DNA Computing to crack data encryption standard system
developed by NSA (uses 2^56 keys to scramble messages)
-Usually breaking w/ one-by-one search.
-But can code each possible key as a strand of DNA then test them all simultaneously.
-Consists of a series of extractions, replications, ... (over months), but would
yield the single DNA strand corresponding to the DES key.
-Combines molecular biology w/ computer science.
________________________________________________________________________________
+ CHEMISTS SELF-ASSEMBLE IN SOUTHERN CALIFORNIA
Self-Building Blocks
-ACS (American Chemical Society) Meeting
-Self-assembly where molecular building blocks put themselves together to form a wide variety of durable materials.
-Take place ina beaker / vat vs $1bil manufacturing plant.
-New class of polymers build themselves into films of 100lays.
-Vary properties.
At the heart of self-assembling films :
-2-part molecules "rodcoils" half-rigid/half-flexible structure.
coil portion = rubbery organic building block = isoprenes + styrene
(isoprene+styrene)-(carboxilic acid group)-(biphenyl ester)
--------coil portion------------------- --rod portion--
||
||
\/
Organic solvent (chloroform)
||
||
\/
evaporates -> weak intermolecular attraction (van der Waals force)
pulls neighboring rodcoils together.
Rod line up side by side. Forces rodcoils into 2D sheets.
Sheets stack up -> 100 layers thick.
________________________________________________________________________________
Oceans & Atmosphere
Subatomic Physics
Condensed matter/ Solid state physics
Atomic, Optical & Molecular physics
Plasma Physics
Mathematics
Mechanics
Astronomy
Inorganic/Analytical Chemistry
Organic Chemistry
Physical chemistry
Micro biology
Biomedical/Physiology
Integrative biology
Geoscience
________________________________________________________________________________
+ DNA Solution of Hard Computational Problems
SUMMARY
-DNA experiments to solve the famous "SAT" problem of
computer science. A special case of a more general method to solve NP-complete
problems. Taking advantage of the huge parallelism of
DNA computing.
TSP & NP-COMPLETE
-DNA computing to solve traveling salesman problem. (TSP)
-TSP (Hamiltonian path problem) is an NP-complete
i.e. all problems like it can be reduced to it.
-Metric 1. How many parallel processes it can do (biological computing 3g of H20 has 10^22 molecules)
2. How many steps each can perform per unit time. (silicon computers)
SAT PROBLEM
-Famous SAT Problem : F=(x||y)&&(~x||~y) find x , y so F=True (2^n solutions)
DNA DYNAMICS
-DNA C+G ; A+T
-1. copy operation : large number of any short single strand (20+ nucleotides)
2. Create operation : can make a double strand of DNA from complementary single strand by annealling
3. Extract operation : single sequences w/ consecutive pattern of length l.
4. Detect operation : find presence of a DNA strand. (w/ polymerase chain reaction)
5. Amplify : replicates all of the DNA in the test tube.
-If a "left" decision branch is taken this is given a "0", or assigned to "C"
a right = "G"
________________________________________________________________________________
+ Computation beyond the Turing Limit
-Extensive efforts have been made to prove the Church-Turing thesis, which
suggests that all realizable dynamical and physical systems cannot be more powerful than
classical models of computation. A simply described but highly chaotic dynamical system
called the analog shift map is presented here, which has
computational power beyond the Turing limit (super-Turing); It
computes exactly like neural networks and analog machines. This
dynamical system is conjectured to describe natural physical phenomena
________________________________________________________________________________
+ Building an Associative Memory Vastly Larger than the Brain
Leonard M Adleman proposes
using the tools of molecular biology to solve
computational problems like HPP.
Solve any NP class problem to speed
up solution of some important practical problems.
Possible to use these tools to produce an associative, content addressable memory of immense
capabilities.
A content addressible memory is one where a stored word may be retrieved from sufficient, partial, knowledge of its content vs needing to know a specific address as in a standard computer memory.
Content addressible memories are useful in widely thought to be an important component of human intelligence.
A vessel w/ DNA. Store binary words of fixed length. 2 DNA subsequences would be assigned to each component, the first coding for "1" and the other coding for "0".
Content addressable by a subset of component values, for each cue, return DNA on a magnetic bead.
--fin