-
- Kensaku Sakamoto
- Department of Biophysics and Biochemistry,
-
- Hidetaka Gouzu
- Department of Biophysics and Biochemistry,
-
- Ken Komiya
- Department of Biophysics and Biochemistry,
-
- Daisuke Kiga
- Department of Biophysics and Biochemistry,
-
- Shigeyuki Yokoyama
- Department of Biophysics and Biochemistry,
-
- Takashi Yokomori
- Department of Mathematics, School of Education, Waseda University, 1-6-1 Nishi-waseda, Shinjuku-ku, Tokyo 169-8050, Japan.
-
- Masami Hagiya
- Department of Information Science, Graduate School of Science, University of Tokyo, 7-3-1 Hongo, Bunkyo-ku, Tokyo 113-0033, Japan.
書誌事項
- 公開日
- 2000-05-19
- DOI
-
- 10.1126/science.288.5469.1223
- 公開者
- American Association for the Advancement of Science (AAAS)
この論文をさがす
説明
<jats:p>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.</jats:p>
収録刊行物
-
- Science
-
Science 288 (5469), 1223-1226, 2000-05-19
American Association for the Advancement of Science (AAAS)