Molecular Computation by DNA Hairpin Formation

See allHide authors and affiliations

Science  19 May 2000:
Vol. 288, Issue 5469, pp. 1223-1226
DOI: 10.1126/science.288.5469.1223

You are currently viewing the abstract.

View Full Text

Log in to view the full text

Log in through your institution

Log in through your institution


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.

  • 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.

View Full Text

Stay Connected to Science