Note to users. If you're seeing this message, it means that your browser cannot find this page's style/presentation instructions -- or possibly that you are using a browser that does not support current Web standards. Find out more about why this message is appearing, and what you can do to make your experience of our site the best it can be.

Site Tools

  • AAAS
  • Subscribe
  • Feedback

Site Search

Search Advanced

Science 11 November 1994:
Vol. 266. no. 5187, pp. 1021 - 1024
DOI: 10.1126/science.7973651
Prev | Table of Contents | Next

Articles

Science, Vol 266, Issue 5187, 1021-1024
Copyright © 1994 by American Association for the Advancement of Science

articles

Molecular computation of solutions to combinatorial problems

LM Adleman

Department of Computer Science, University of Southern California, Los Angeles 90089.

The tools of molecular biology were used to solve an instance of the directed Hamiltonian path problem. A small graph was encoded in molecules of DNA, and the "operations" of the computation were performed with standard protocols and enzymes. This experiment demonstrates the feasibility of carrying out computations at the molecular level.


THIS ARTICLE HAS BEEN CITED BY OTHER ARTICLES:
From the Cover: Infochemistry and infofuses for the chemical storage and transmission of coded information.
S. W. Thomas III, R. C. Chiechi, C. N. LaFratta, M. R. Webb, A. Lee, B. J. Wiley, M. R. Zakin, D. R. Walt, and G. M. Whitesides (2009)
PNAS 106, 9147-9150
   Abstract »    Full Text »    PDF »
Fireworks for the information age.
J. A. Rogers (2009)
PNAS 106, 9127-9128
   Full Text »    PDF »
Computational thinking and thinking about computing.
J. M Wing (2008)
Phil Trans R Soc A 366, 3717-3725
   Abstract »    Full Text »    PDF »
On the dynamics of molecular conformation.
I. Mezic (2006)
PNAS 103, 7542-7547
   Abstract »    Full Text »    PDF »
On the Integrality Ratio for the Asymmetric Traveling Salesman Problem.
M. Charikar, M. X. Goemans, and H. Karloff (2006)
Mathematics of Operations Research 31, 245-252
   Abstract »    PDF »
A modular DNA signal translator for the controlled release of a protein by an aptamer.
S. Beyer and F. C. Simmel (2006)
Nucleic Acids Res. 34, 1581-1587
   Abstract »    Full Text »    PDF »
Deoxyribozymes that recode sequence information..
J. J. Tabor, M. Levy, and A. D. Ellington (2006)
Nucleic Acids Res. 34, 2166-2172
   Abstract »    Full Text »    PDF »
Thermodynamically based DNA strand design.
D. Tulpan, M. Andronescu, S. B. Chang, M. R. Shortreed, A. Condon, H. H. Hoos, and L. M. Smith (2005)
Nucleic Acids Res. 33, 4951-4964
   Abstract »    Full Text »    PDF »
Examining the architecture of cellular computing through a comparative study with a computer.
D. Wang and M. Gribskov (2005)
J R Soc Interface 2, 187-195
   Abstract »    Full Text »    PDF »
Design of nucleic acid sequences for DNA computing based on a thermodynamic approach.
F. Tanaka, A. Kameda, M. Yamamoto, and A. Ohuchi (2005)
Nucleic Acids Res. 33, 903-911
   Abstract »    Full Text »    PDF »
The stability of Seeman JX DNA topoisomers of paranemic crossover (PX) molecules as a function of crossover number.
P. K. Maiti, T. A. Pascal, N. Vaidehi, and W. A. Goddard III (2004)
Nucleic Acids Res. 32, 6047-6056
   Abstract »    Full Text »    PDF »
DNA computing using single-molecule hybridization detection.
K. A. Schmidt, C. V. Henkel, G. Rozenberg, and H. P. Spaink (2004)
Nucleic Acids Res. 32, 4962-4968
   Abstract »    Full Text »    PDF »
Stochastic computing with biomolecular automata.
R. Adar, Y. Benenson, G. Linshiz, A. Rosner, N. Tishby, and E. Shapiro (2004)
PNAS 101, 9960-9965
   Abstract »    Full Text »    PDF »
Demonstration of a universal surface DNA computer.
X. Su and L. M. Smith (2004)
Nucleic Acids Res. 32, 3115-3123
   Abstract »    Full Text »    PDF »
Two-step total gene synthesis method.
L. Young and Q. Dong (2004)
Nucleic Acids Res. 32, e59
   Abstract »    Full Text »    PDF »
Nanotechnology and Medicine.
J. H. Thrall (2004)
Radiology 230, 315-318
   Full Text »    PDF »
Molecular flip-flops formed by overlapping Fis sites.
P. N. Hengen, I. G. Lyakhov, L. E. Stewart, and T. D. Schneider (2003)
Nucleic Acids Res. 31, 6663-6673
   Abstract »    Full Text »    PDF »
DNA-Templated Self-Assembly of Protein Arrays and Highly Conductive Nanowires.
H. Yan, S. H. Park, G. Finkelstein, J. H. Reif, and T. H. LaBean (2003)
Science 301, 1882-1884
   Abstract »    Full Text »    PDF »
Studies of temperature-dependent electronic transduction on DNA hairpin loop sensor.
Y. Mao, C. Luo, and Q. Ouyang (2003)
Nucleic Acids Res. 31, e108
   Abstract »    Full Text »    PDF »
Directed nucleation assembly of DNA tile complexes for barcode-patterned lattices.
H. Yan, T. H. LaBean, L. Feng, and J. H. Reif (2003)
PNAS 100, 8103-8108
   Abstract »    Full Text »    PDF »
DNA molecule provides a computing machine with both data and fuel.
Y. Benenson, R. Adar, T. Paz-Elizur, Z. Livneh, and E. Shapiro (2003)
PNAS 100, 2191-2196
   Abstract »    Full Text »    PDF »
DNA duplex-quadruplex exchange as the basis for a nanomolecular machine.
P. Alberti and J.-L. Mergny (2003)
PNAS 100, 1569-1573
   Abstract »    Full Text »    PDF »
Protein-DNA computation by stochastic assembly cascade.
R. Bar-Ziv, T. Tlusty, and A. Libchaber (2002)
PNAS 99, 11589-11592
   Abstract »    Full Text »    PDF »
Supramolecular Chemistry And Self-assembly Special Feature: Toward complex matter: Supramolecular chemistry and self-organization.
J.-M. Lehn (2002)
PNAS 99, 4763-4768
   Full Text »    PDF »
Toward Self-Organization and Complex Matter.
J.-M. Lehn (2002)
Science 295, 2400-2403
   Abstract »    Full Text »    PDF »
A Quantum Conversation.
N. Gershenfeld (2001)
Science 293, 2035-2037
   Full Text »    PDF »
From the Cover: Using three-dimensional microfluidic networks for solving computationally hard problems.
D. T. Chiu, E. Pezzoli, H. Wu, A. D. Stroock, and G. M. Whitesides (2001)
PNAS 98, 2961-2966
   Abstract »    Full Text »    PDF »
End-specific covalent photo-dependent immobilisation of synthetic DNA to paramagnetic beads.
R. Penchovsky, E. Birch-Hirschfeld, and J. S. McCaskill (2000)
Nucleic Acids Res. 28, e98
   Abstract »    Full Text »    PDF »
Molecular Computation by DNA Hairpin Formation.
K. Sakamoto, H. Gouzu, K. Komiya, D. Kiga, S. Yokoyama, T. Yokomori, and M. Hagiya (2000)
Science 288, 1223-1226
   Abstract »    Full Text »
Computation with biomolecules.
J. Chen and D. H. Wood (2000)
PNAS 97, 1328-1330
   Full Text »    PDF »
From the Cover: Molecular computation: RNA solutions to chess problems.
D. Faulhammer, A. R. Cukras, R. J. Lipton, and L. F. Landweber (2000)
PNAS 97, 1385-1389
   Abstract »    Full Text »    PDF »
From the Cover: Using lateral capillary forces to compute by self-assembly.
P. W. K. Rothemund (2000)
PNAS 97, 984-989
   Abstract »    Full Text »    PDF »
DNA Solution of the Maximal Clique Problem.
Q. Ouyang, P. D. Kaplan, S. Liu, and A. Libchaber (1997)
Science 278, 446-449
   Abstract »    Full Text »
Ensemble quantum computing by NMR spectroscopy.
D. G. Cory, A. F. Fahmy, and T. F. Havel (1997)
PNAS 94, 1634-1639
   Abstract »    Full Text »    PDF »
Efficiency of DNA replication in the polymerase chain reaction.
G. Stolovitzky and G. Cecchi (1996)
PNAS 93, 12947-12952
   Abstract »    Full Text »    PDF »
The Evolution of Molecular Computation.
W. P. C. Stemmer (1995)
Science 270, 1510
   Abstract »    PDF »
DNA solution of hard computational problems.
R. Lipton (1995)
Science 268, 542-545
   Abstract »    PDF »
Building an associative memory vastly larger than the brain.
E. Baum (1995)
Science 268, 583-585
   PDF »
On the path to computation with DNA.
D. Gifford (1994)
Science 266, 993-994
   PDF »
Solution of a 20-Variable 3-SAT Problem on a DNA Computer.
R. S. Braich, N. Chelyapov, C. Johnson, P. W. K. Rothemund, and L. Adleman (2002)
Science 296, 499-502
   Abstract »    Full Text »    PDF »
Evolution and assembly of an extremely scrambled gene.
L. F. Landweber, T.-C. Kuo, and E. A. Curtis (2000)
PNAS 97, 3298-3303
   Abstract »    Full Text »    PDF »
Supramolecular Chemistry And Self-assembly Special Feature: Toward complex matter: Supramolecular chemistry and self-organization.
J.-M. Lehn (2002)
PNAS 99, 4763-4768
   Full Text »    PDF »


To Advertise     Find Products

Science. ISSN 0036-8075 (print), 1095-9203 (online)