Soloveichik, David and Winfree, Erik (2005) The computational power of Benenson automata. Theoretical Computer Science, 344 (2-3). pp. 279-297. ISSN 0304-3975. http://resolver.caltech.edu/CaltechAUTHORS:20110309-104201537
- Submitted Version
See Usage Policy.
Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:20110309-104201537
The development of autonomous molecular computers capable of making independent decisions in vivo regarding local drug administration may revolutionize medical science. Recently Benenson et al. [An autonomous molecular computer for logical control of gene expression, Nature 429 (2004) 423–429.] have envisioned one form such a “smart drug” may take by implementing an in vitro scheme, in which a long DNA state molecule is cut repeatedly by a restriction enzyme in a manner dependent upon the presence of particular short DNA “rule molecules.” To analyze the potential of their scheme in terms of the kinds of computations it can perform, we study an abstraction assuming that a certain class of restriction enzymes is available and reactions occur without error. We also discuss how our molecular algorithms could perform with known restriction enzymes. By exhibiting a way to simulate arbitrary circuits, we show that these “Benenson automata” are capable of computing arbitrary Boolean functions. Further, we show that they are able to compute efficiently exactly those functions computable by log-depth circuits. Computationally, we formalize a new variant of limited width branching programs with a molecular implementation.
|Additional Information:||© 2005 Elsevier B.V. Received 21 December 2004; revised 29 July 2005; Accepted 29 July 2005. Communicated by T. Yokomori. Available online 24 August 2005. We thank Georg Seelig for first bringing Benenson et al.’s work to our attention. Further, we thank two anonymous reviewers for very detailed reading of this paper and useful suggestions. This research was supported by NIH training Grant MH19138-15.|
|Subject Keywords:||molecular computing; DNA computing; computational complexity; restriction enzymes; branching programs; circuit complexity|
|Official Citation:||David Soloveichik, Erik Winfree, The computational power of Benenson automata, Theoretical Computer Science, Volume 344, Issues 2-3, 17 November 2005, Pages 279-297, ISSN 0304-3975, 10.1016/j.tcs.2005.07.027.|
|Usage Policy:||No commercial reproduction, distribution, display or performance rights in this work are provided.|
|Deposited By:||Lucinda Acosta|
|Deposited On:||21 Oct 2011 18:36|
|Last Modified:||07 Mar 2015 00:30|
Repository Staff Only: item control page