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.

Science 28 April 1995:
Vol. 268. no. 5210, pp. 542 - 545
DOI: 10.1126/science.7725098
Prev | Table of Contents | Next

Articles

Science, Vol 268, Issue 5210, 542-545
Copyright © 1995 by American Association for the Advancement of Science

articles

DNA solution of hard computational problems

RJ Lipton

Princeton University, NJ 08540, USA.

DNA experiments are proposed to solve the famous "SAT" problem of computer science. This is a special case of a more general method that can solve NP-complete problems. The advantage of these results is the huge parallelism inherent in DNA-based computing. It has the potential to yield vast speedups over conventional electronic-based computers for such search problems.


THIS ARTICLE HAS BEEN CITED BY OTHER ARTICLES:
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 »
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 »
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 »
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 »
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 »
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 »
The Evolution of Molecular Computation.
W. P. C. Stemmer (1995)
Science 270, 1510
   Abstract »    PDF »
Response.
L. M. Adleman (1995)
Science 268, 483-484
   PDF »
Building an associative memory vastly larger than the brain.
E. Baum (1995)
Science 268, 583-585
   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 »


To Advertise     Find Products

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