title: DNA computing using single-molecule hybridization detection.
abstract: DNA computing aims at using nucleic acids for computing. Since micromolar DNA solutions can act as billions of parallel nanoprocessors, DNA computers can in theory solve optimization problems that require vast search spaces. However, the actual parallelism currently being achieved is at least a hundred million-fold lower than the number of DNA molecules used. This is due to the quantity of DNA molecules of one species that is required to produce a detectable output to the computations. In order to miniaturize the computation and considerably reduce the amount of DNA needed, we have combined DNA computing with single-molecule detection. Reliable hybridization detection was achieved at the level of single DNA molecules with fluorescence cross-correlation spectroscopy. To illustrate the use of this approach, we implemented a DNA-based computation and solved a 4-variable 4-clause instance of the computationally hard Satisfiability (SAT) problem.
authors.affiliation: Institute of Biology, Leiden University, Wassenaarseweg 64, 2333 AL Leiden, The Netherlands. kristiane.schmidt@philips.com
authors.forename: Kristiane A
authors.initials: KA
authors.lastname: Schmidt
authors.forename: Christiaan V
authors.initials: CV
authors.lastname: Henkel
authors.forename: Grzegorz
authors.initials: G
authors.lastname: Rozenberg
authors.forename: Herman P
authors.initials: HP
authors.lastname: Spaink
mesh_terms: D000465:Algorithms; D019295:Computational Biology; D039301:Computers, Molecular; D004247:DNA / Q000032:analysis* / Q000737:chemistry; D009693:Nucleic Acid Hybridization / Q000379:methods*; D013050:Spectrometry, Fluorescence
chemical_list: D004247:DNA