Peng Yin, Sudheer Sahu, Andrew Turberfield, & John Reif
In Proc. Eleventh International Meeting on DNA Computing, 2005, to appear
Downloads: PDF
Abstract: Recent experimental progress in DNA lattice construction,
DNA robotics, and DNA computing provide the basis for designing DNA cellular
computing devices, i.e. autonomous nano-mechanical DNA computing devices
embedded in DNA lattices. Once assembled, DNA cellular computing devices
can serve as reusable, compact computing devices that perform (universal)
computation, and programmable robotics devices that demonstrate complex motion.
As a prototype of such devices, we recently reported the design of an Autonomous
DNA Turing Machine, which is capable of universal sequential computation,
and universal translational motion, i.e. the motion of the head of a single
tape universal mechanical Turing machine.
In this paper, we describe the design of an Autonomous DNA Cellular Automaton
(ADCA), which can perform parallel universal computation by mimicking
a one-dimensional (1D) universal cellular automaton. In the computation
process, this device, embedded in a 1D DNA lattice, also demonstrates well
coordinated parallel motion. The key technical innovation here is a molecular
mechanism that synchronizes pipelined ``molecular reaction waves'' along
a 1D track, and in doing so, realizes parallel computation. We first describe
the design of ADCA on an abstract level, and then present detailed DNA sequence
level implementation using commercially available protein enzymes. We also
discuss how to extend the 1D design to 2D.
Computer simulation: Click here,
Animation Movie: Click here
Back to pulications