Publication Date:
2000-05-20
Description:
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.〈br /〉〈span class="detail_caption"〉Notes: 〈/span〉Sakamoto, K -- Gouzu, H -- Komiya, K -- Kiga, D -- Yokoyama, S -- Yokomori, T -- Hagiya, M -- New York, N.Y. -- Science. 2000 May 19;288(5469):1223-6.〈br /〉〈span class="detail_caption"〉Author address: 〈/span〉Department of Biophysics and Biochemistry, Graduate School of Science, University of Tokyo, 7-3-1 Hongo, Bunkyo-ku, Tokyo 113-0033, Japan.〈br /〉〈span class="detail_caption"〉Record origin:〈/span〉 〈a href="http://www.ncbi.nlm.nih.gov/pubmed/10817993" target="_blank"〉PubMed〈/a〉
Keywords:
Algorithms
;
Biotinylation
;
Computational Biology/*methods
;
DNA Ligases/chemistry
;
DNA, Single-Stranded/*chemistry
;
DNA-Directed DNA Polymerase/chemistry
;
Electrophoresis, Agar Gel
;
*Nucleic Acid Conformation
;
Nucleic Acid Denaturation
;
Polymerase Chain Reaction
;
Temperature
;
Templates, Genetic
Print ISSN:
0036-8075
Electronic ISSN:
1095-9203
Topics:
Biology
,
Chemistry and Pharmacology
,
Computer Science
,
Medicine
,
Natural Sciences in General
,
Physics
Permalink