DNA computing on surfaces

Qinghua Liu, Liman Wang, Anthony G. Frutos, Anne E. Condon, Robert M. Corn and Lloyd M. Smith ()
Additional contact information
Qinghua Liu: Department of Chemistry
Liman Wang: Department of Chemistry
Anthony G. Frutos: Department of Chemistry
Anne E. Condon: University of Wisconsin
Robert M. Corn: Department of Chemistry
Lloyd M. Smith: Department of Chemistry

Nature, 2000, vol. 403, issue 6766, 175-179

Abstract: Abstract DNA computing was proposed1 as a means of solving a class of intractable computational problems in which the computing time can grow exponentially with problem size (the ‘NP-complete’ or non-deterministic polynomial time complete problems). The principle of the technique has been demonstrated experimentally for a simple example of the hamiltonian path problem2 (in this case, finding an airline flight path between several cities, such that each city is visited only once3). DNA computational approaches to the solution of other problems have also been investigated4,5,6,7,8,9. One technique10,11,12,13 involves the immobilization and manipulation of combinatorial mixtures of DNA on a support. A set of DNA molecules encoding all candidate solutions to the computational problem of interest is synthesized and attached to the surface. Successive cycles of hybridization operations and exonuclease digestion are used to identify and eliminate those members of the set that are not solutions. Upon completion of all the multi-step cycles, the solution to the computational problem is identified using a polymerase chain reaction to amplify the remaining molecules, which are then hybridized to an addressed array. The advantages of this approach are its scalability and potential to be automated (the use of solid-phase formats simplifies the complex repetitive chemical processes, as has been demonstrated in DNA and protein synthesis14). Here we report the use of this method to solve a NP-complete problem. We consider a small example of the satisfiability problem (SAT)2, in which the values of a set of boolean variables satisfying certain logical constraints are determined.

Date: 2000
References: Add references at CitEc
Citations:

Downloads: (external link)
https://www.nature.com/articles/35003155 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:nat:nature:v:403:y:2000:i:6766:d:10.1038_35003155

Ordering information: This journal article can be ordered from
https://www.nature.com/

DOI: 10.1038/35003155

Access Statistics for this article

Nature is currently edited by Magdalena Skipper

More articles in Nature from Nature
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().