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.

Published Online March 14, 2002
Science DOI: 10.1126/science.1069528

Research Articles

Submitted on January 3, 2002
Accepted on March 5, 2002

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 Adleman 1*

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.

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.


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)