Molecular computation by DNA hairpin formation.
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.
Sakamoto
K
K
Department of Biophysics and Biochemistry, Graduate School of Science, University of Tokyo, 7-3-1 Hongo, Bunkyo-ku, Tokyo 113-0033, Japan.
Gouzu
H
H
Komiya
K
K
Kiga
D
D
Yokoyama
S
S
Yokomori
T
T
Hagiya
M
M
D000465:Algorithms; D019921:Biotinylation; D019295:Computational Biology / Q000379:methods*; D011088:DNA Ligases / Q000737:chemistry; D004277:DNA, Single-Stranded / Q000737:chemistry*; D004259:DNA-Directed DNA Polymerase / Q000737:chemistry; D004587:Electrophoresis, Agar Gel; D009690:Nucleic Acid Conformation; D009691:Nucleic Acid Denaturation; D016133:Polymerase Chain Reaction; D013696:Temperature; D013698:Templates, Genetic
D004277:DNA, Single-Stranded; D004259:DNA-Directed DNA Polymerase; D011088:DNA Ligases