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.
AAAS Store

Site Tools

  • AAAS
  • Subscribe
  • Feedback

Site Search

Search Advanced

Science 19 May 2000:
Vol. 288. no. 5469, pp. 1223 - 1226
DOI: 10.1126/science.288.5469.1223
Prev | Table of Contents | Next

Reports

Molecular Computation by DNA Hairpin Formation

Kensaku Sakamoto, 1* Hidetaka Gouzu, 1 Ken Komiya, 1 Daisuke Kiga, 1dagger Shigeyuki Yokoyama, 1 Takashi Yokomori, 3 Masami Hagiya 2*

Hairpin formation by single-stranded DNA molecules was exploited in a DNA-based computation in order to explore the feasibility of autonomous molecular computing. An instance of the satisfiability problem, a famous hard combinatorial problem, was solved by using molecular biology techniques. The satisfiability of a given Boolean formula was examined autonomously, on the basis of hairpin formation by the molecules that represent the formula. This computation algorithm can test several clauses in the given formula simultaneously, which could reduce the number of laboratory steps required for computation.

1 Department of Biophysics and Biochemistry,
2 Department of Information Science, Graduate School of Science, University of Tokyo, 7-3-1 Hongo, Bunkyo-ku, Tokyo 113-0033, Japan.
3 Department of Mathematics, School of Education, Waseda University, 1-6-1 Nishi-waseda, Shinjuku-ku, Tokyo 169-8050, Japan.
*   To whom correspondence should be addressed.

dagger    Present address: Yokoyama Cytologic Project, Exploratory Research for Advanced Technology, Japan Science and Technology Corporation, c/o RIKEN, Hirosawa, Wako-shi, Saitama 351-0198, Japan.

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 »
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 »
Rational design of DNA sequences for nanotechnology, microarrays and molecular computers using Eulerian graphs.
P. Pancoska, Z. Moravek, and U. M. Moll (2004)
Nucleic Acids Res. 32, 4630-4645
   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 »
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 »
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 »


ADVERTISEMENT
Click Me!

ADVERTISEMENT
Click Me!

To Advertise     Find Products