| |
DNA computing holds vast potential for solving
problems that are extremely difficult to solve by conventional
computation methods. A DNA molecule is a long string of bases,
Adenine, Thymine, Guanine, and Cytocine. This string of bases
is a code. Within an organism, the DNA code represents the information
necessary to assemble proteins, which in turn perform various
functions throughout the body. Conventional computing uses a
binary code, strings of 1's and 0's, representing switches that
are on or off. In DNA computation, if one can uniquely recognize
the four different bases, then the bases are bits of data, and
a string of bases on a DNA molecule represents a quaternary
code. Using the toolbox of biochemistry, various problems can
be encoded in DNA and manipulated through a series of biomolecular
reactions, which act as the computation steps. After the computation
is completed, the code of the remaining DNA is deciphered to
reveal the solution to the problem. Because of the ability to
perform biochemical operations simultaneously on many different
DNA molecules, a problem that would take all the supercomputers
in the world running in parallel years to solve could, in principle,
be solved in a matter of minutes with a DNA computer.
The mapping of information onto DNA sequences is the basis for
the ability of DNA to store data and perform computations. To
provide a feeling for the magnitude, consider the following:
on a written page, there are approximately 1,500 characters.
If 3 bases were to represent a character, then a set of 34,
81, different characters could be represented, and 4,500 bases
could encode a page. If each DNA molecule is limited to 20 bases
(human DNA contains ~3 billion of bases) and if each of the
119 million volumes in the Library of Congress has 1000 pages,
then approximately 2 x 1013 different DNA molecules each only
20 bases long could encode for the entire contents of the library.
A milliliter sample of 1 millimolar (1mM) solution of DNA molecules
20 bases long could represent the entire library as well as
provide ~40,000 copies.
A potentially more reliable approach to DNA computation uses
surfaces to support the DNA reactions. The principles are the
same as described above, but the benefits of surface-based DNA
computation are numerous. (1) With DNA bound to a surface, the
computational operations of the computer become very simple.
Solutions that represent a computation step by reacting with
the bound DNA are introduced to the flat surface with the DNA
tethered to it. Later, DNA strands in the reaction solution
are simply washed away. (2) When the DNA is attached to the
surface, the loss of DNA between one step and another is minimal.
In a test-tube-based DNA computational system, every transfer
from one test tube to another leaves residual liquid behind,
and in that liquid, some fraction of the DNA mixture, thus introducing.
(3) Once immobilized on a surface, the oligonucleotides cannot
interact with each other, thus reducing interference and false
signals. In solution, two complementary single-stranded sequences
can form duplexes. (4) Purification of DNA sequences, necessary
at each step, is as simple as washing the surface with water
to remove unwanted reaction products. Separation in a test-tube-based
system is usually achieved through gel electrophoresis (a standard
separation technique), and dialysis (a procedure which removes
the majority of salts from a reaction mixture) is necessary
sometimes to remove unwanted salts; both procedures are tedious
and time consuming. (5) DNA computation on a surface can benefit
from the wealth of tools available in silicon processing, designed
for integrated-circuit fabrication, including patterning, etching,
and transporting of silicon wafers, eliminating the need to
design new materials-processing technology. Marrying the parallel
processing of DNA to the controllability that surfaces allow
gives a tangible methodology to implement DNA computation.
A schematic outline of the DNA operations for surface-based
DNA computation. In DNA computation, difficult computation
problems deemed intractable are investigated using the parallel
approach of DNA. (1) Generation involves creating a large
pool of different DNA sequences to represent the different
possible solutions to a problem. (2) We immobilize the strands
to a surface, and (3) MARK, or hybridize, a specific subset
of sequences with its complementary sequence that corresponds
to a potentially correct answer in the computation problem.
(4) Then we DESTROY the remaining single-stranded sequences
on the surface with a judicious choice of enzymes that distinguish
between the MARKed strands and the single-strands. The single-strands
are cut off of the surface through enzymatic digestion. (5)
Afterwards, the complementary sequences are UNMARKED or separated
from their complements to allow for further computation. Steps
3, 4 and 5 can be repeated many times before READOUT is performed.
(6) In READOUT, we determine the sequences of the strands
that remain after the DNA computation operations.[A.G. Frutos,
Nucleic Acid Research. 1997]
References:
Clelland, C.T.; Risca, V.; Bancroft, C. Hiding Messages in
DNA Microdots. Nature. 399, 533-534 (1999).
Adleman, L.M. Molecular Computation of Solutions to Combinatorial
Problems. Science. 266, 1021 (1994).
DIMACs, Journal of Computational Biology. DNA7 Seventh International
Meeting on DNA Based Computers June 10-13, 2001. http://www.cas.usf.edu/dna7/
Lipton, J. R. DNA Solutions to Hard Computational Problems.
Science. 268, 542 (1995).
Ouyang, Q.; Kaplan, P.D.; Shumao, L.; Libchaber, A. DNA Solution
of the Maximal Clique Problem. Science. 278, 446 (1997).
Smith, L.M.; Corn, R.M.; Condon, A.E.; Lagally, M.G.; Frutos,
A.G.; Liu, Q.; Thiel, A.J. A Surface-based Approach to DNA
Computation. J. Comput. Biol. 5, 255 (1998).
Erik Winfree, Furong Liu, Lisa Wenzler, Nadrian C. Seeman.Design
and self-assembly of two-dimensional DNA crystals. Nature.
394, 539-544 (1998).
Frutos, A.G.; Liu, Q.; Thiel, A.J.; Sanner, A.M.W.; Condon,
A.E.; Smith, L.M.; Corn, R.M. Demonstration of a Word Design
Strategy for DNA Computing on Surfaces. Nucleic Acids Research.
1997, 25(23), 4747-4757
Liu, Q.; Wang, L.; Frutos, A.G.; Condon, A.E.; Corn, R.M.;
Smith, L.M. DNA Computing on Surfaces. Nature 403,
175 (2000).
Frutos, A.G.; Condon, A.E.; Smith, L.M. Corn, R.M. Enzymatic
Ligation Reactions of DNA "Words" on Surfaces for DNA Computing.
J. Am. Chem. Soc., 120 10277 (1998).
Wang, L.; Liu, Q.; Corn, R.M.; Condon, A.E.; Smith, L.M. Multiple
Word DNA Computing on Surfaces. J. Am. Chem. Soc., 122(31),
7435-7440 (2000).
Mao, C.; LaBean, T.H.; Reif, J.H.; Seeman, N.C. Logical Computing
Using Algorithmic Self-Assembly of DNA Triple-Crossover Molecules.
Nature. 407, 493-496 (2000).
Sam Roweis, Erik Winfree, Richard Burgoyne, Nickolas V. Chelyapov,
Myron F. Goodman, Paul W. K. Rothemund, Leonard M. Adleman
A Sticker-Based Model for DNA Computation. Journal of Computational
Biology. 5(4), 615-629, 1998.
Links:
http://dope.caltech.edu/winfree/DNA.html
http://www-scf.usc.edu/~pwkr/index.html
http://users.aol.com/ibrandt/discover_article.html
http://corninfo.chem.wisc.edu/writings/DNAcomputing.html
http://www.chem.wisc.edu/~smith/research.html
This material is based upon work supported
by the National Science Foundation under Grant No. 9613799.
Any opinions, findings, and conclusions or recommendations
expressed in this material are those of the author(s) and
do not necessarily reflect the views of the National Science
Foundation.
|
|
Back to DNA Research