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.

Originally published in Science Express on 14 March 2002
Science 19 April 2002:
Vol. 296. no. 5567, pp. 499 - 502
DOI: 10.1126/science.1069528
Prev | Table of Contents | Next

Research Articles

Solution of a 20-Variable 3-SAT Problem on a DNA Computer

Ravinderjit S. Braich,1 Nickolas Chelyapov,1 Cliff Johnson,1 Paul W. K. Rothemund,2 Leonard Adleman1*

A 20-variable instance of the NP-complete three-satisfiability (3-SAT) problem was solved on a simple DNA computer. The unique answer was found after an exhaustive search of more than 1 million (220) possibilities. This computational problem may be the largest yet solved by nonelectronic means. Problems of this size appear to be beyond the normal range of unaided human computation.

1 University of Southern California, Laboratory for Molecular Science, Los Angeles, CA 90089-1340, USA.
2 California Institute of Technology, Pasadena, CA 91125, USA.
*   To whom correspondence should be addressed. E-mail: Adleman{at}USC.edu. Web site: www.usc.edu/dept/molecular-science/index.html

Read the Full Text


THIS ARTICLE HAS BEEN CITED BY OTHER ARTICLES:
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 »
A thermodynamic approach to designing structure-free combinatorial DNA word sets.
M. R. Shortreed, S. B. Chang, D. Hong, M. Phillips, B. Campion, D. C. Tulpan, M. Andronescu, A. Condon, H. H. Hoos, and L. M. Smith (2005)
Nucleic Acids Res. 33, 4965-4977
   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 »
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 »
Demonstration of a universal surface DNA computer.
X. Su and L. M. Smith (2004)
Nucleic Acids Res. 32, 3115-3123
   Abstract »    Full Text »    PDF »
Paradigms for computational nucleic acid design.
R. M. Dirks, M. Lin, E. Winfree, and N. A. Pierce (2004)
Nucleic Acids Res. 32, 1392-1403
   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 »
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 »
RNAsoft: a suite of RNA secondary structure prediction and design software tools.
M. Andronescu, R. Aguirre-Hernandez, A. Condon, and H. H. Hoos (2003)
Nucleic Acids Res. 31, 3416-3422
   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 »
Molecule Cascades.
A. J. Heinrich, C. P. Lutz, J. A. Gupta, and D. M. Eigler (2002)
Science 298, 1381-1387
   Abstract »    Full Text »    PDF »


To Advertise     Find Products

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