Related Content
Search Google Scholar for:
More Information
Related Jobs from ScienceCareers
|
|
Science 19 May 2000:
Vol. 288. no. 5469, pp. 1223 - 1226
DOI: 10.1126/science.288.5469.1223
|
|
Reports
Molecular Computation by DNA Hairpin Formation
Kensaku Sakamoto,
1*
Hidetaka Gouzu,
1
Ken Komiya,
1
Daisuke Kiga,
1
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.
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 »
|
|
