Simulating Boolean Circuits on a DNA Computer |
| |
Authors: | M Ogihara A Ray |
| |
Affiliation: | (1) Department of Computer Science, University of Rochester, Rochester, NY 14627, USA. ogihara@cs.rochester.edu., US;(2) Department of Biology, University of Rochester, Rochester, NY 14627, USA. ray@ar.biology.rochester.edu., US |
| |
Abstract: | We demonstrate that DNA computers can simulate Boolean circuits with a small overhead. Boolean circuits embody the notion
of massively parallel signal processing and are frequently encountered in many parallel algorithms. Many important problems
such as sorting, integer arithmetic, and matrix multiplication are known to be computable by small size Boolean circuits much
faster than by ordinary sequential digital computers. This paper shows that DNA chemistry allows one to simulate large semi-unbounded
fan-in Boolean circuits with a logarithmic slowdown in computation time. Also, for the class NC
1
, the slowdown can be reduced to a constant. In this algorithm we have encoded the inputs, the Boolean AND gates, and the
OR gates to DNA oligonucleotide sequences. We operate on the gates and the inputs by standard molecular techniques of sequence-specific
annealing, ligation, separation by size, amplification, sequence-specific cleavage, and detection by size. Additional steps
of amplification are not necessary for NC
1
circuits. The feasibility of the DNA algorithm has been successfully tested on a small circuit by actual biochemical experiments.
Received May 29, 1997; revised February 15, 1998. |
| |
Keywords: | , Boolean circuits, DNA computation, Parallel computation, |
本文献已被 SpringerLink 等数据库收录! |
|