CaltechAUTHORS
  A Caltech Library Service

A sticker-based model for DNA computation

Roweis, Sam and Winfree, Erik and Burgoyne, Richard and Chelyapov, Nickolas V. and Goodman, Myron F. and Rothemund, Paul W. K. and Adleman, Leonard M. (1998) A sticker-based model for DNA computation. Journal of Computational Biology, 5 (4). pp. 615-629. ISSN 1066-5277. http://resolver.caltech.edu/CaltechAUTHORS:20110309-104205486

[img]
Preview
PDF - Published Version
See Usage Policy.

1277Kb
[img]
Preview
PDF - Submitted Version
See Usage Policy.

556Kb
[img]
Preview
PDF - Published Version
See Usage Policy.

7Mb

Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:20110309-104205486

Abstract

We introduce a new model of molecular computation that we call the sticker model. Like many previous proposals it makes use of DNA strands as the physical substrate in which information is represented and of separation by hybridization as a central mechanism. However, unlike previous models, the stickers model has a random access memory that requires no strand extension and uses no enzymes; also (at least in theory), its materials are reusable. The paper describes computation under the stickers model and discusses possible means for physically implementing each operation. Finally, we go on to propose a specific machine architecture for implementing the stickers model as a microprocessor-controlled parallel robotic workstation. In the course of this development a number of previous general concerns about molecular computation (Smith, 1996; Hartmanis, 1995; Linial ct al., 1995) are addressed. First, it is clear that general-purpose algorithms can be implemented by DNA-based computers, potentially solving a wide class of search problems. Second, we Rnd that there are challenging problems, for which only modest volumes of DNA should suffice. Third, we demonstrate that the formation and breaking of covalent bonds is not intrinsic to DNA-based computation. Fourth, we show that a single essential biotechnology, sequence-specific separation, suffices for constructing a general-purpose molecular computer. Concerns about errors in this separation operation and means to reduce them are addressed elsewhere (Karp ct at, 1995; Rowels and Winfree, 1999). Despite these encouraging theoretical advances, we emphasize that substantial engineering challenges remain at almost all stages and that the ultimate success or failure of DNA computing will certainly depend on whether these challenges can be met in laboratory investigations.


Item Type:Article
Related URLs:
URLURL TypeDescription
http://dx.doi.org/10.1089/cmb.1998.5.615DOIUNSPECIFIED
http://www.liebertonline.com/doi/abs/10.1089/cmb.1998.5.615PublisherUNSPECIFIED
Additional Information:© 1998 Mary Ann Leibert, Inc. Received for publication November 9, 1997; accepted as revised June 6, 1998. We would like to express their appreciation to Professor John Baldeschwieler for his contributions to this paper through early discussions of this work. S.R. and E.W. are also grateful to their advisor, Professor John Hopfield, for his perpetual wisdom and long-term advice. Thanks to Kazuyoshi Harada for some corrections. S .R. is supported in part by the Center for Neuromorphic Systems Engineering as a part of the National Science Foundation Engineering Research Center Program under grant EEC-9402726 and by the Natural Sciences and Engineering Research Council of Canada. E.W. is supported in part by National Institute for Mental Health (NIMH) Training Grant no. 5 T32 MH 19138-06; also by General Motors' Technology Research Partnerships program. L.M.A., N.V.C., and P.W.K.R. are supported in part by grants from the National Science Foundation (CCR-9403662) and Sloan Foundation.
Funders:
Funding AgencyGrant Number
NSFEEC-9402726
Natural Sciences and Engineering Research Council of Canada (NSERC)UNSPECIFIED
National Institute of Mental Health5 T32 MH 19138-06
General Motors' Technology Research PartnershipsUNSPECIFIED
NSFCCR-9403662
Alfred P. Sloan FoundationUNSPECIFIED
Subject Keywords:molecular computation; DNA computation; sticker model
Record Number:CaltechAUTHORS:20110309-104205486
Persistent URL:http://resolver.caltech.edu/CaltechAUTHORS:20110309-104205486
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:22779
Collection:CaltechAUTHORS
Deposited By: Lucinda Acosta
Deposited On:09 Mar 2011 19:13
Last Modified:26 Dec 2012 13:01

Repository Staff Only: item control page