A sticker based model for DNA computation

摘要

Vve 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, uses no enzymes, and (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.We go on to propose a specific machine architecture for implementing the stickers model as a microprocessor-controlled parallel robotic workstation.Finally, we discuss several methods for achieving acceptable overall error rates for a computation using basic operations that are error prone.In t he course of this development a number of previous general concerns about molecular computation [36, 2 0 , 24 ) are addressed.First, it is clear that general-purpose algorithms can be implemented by DNA-based computers, potentially solving a " .. •ide class of search problems.Second, we find 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.This means that costly and short-lived materials such as enzymes are not necessary, nor are energetically costly processes such as PCR.Fourth , \ .... e show that a single essential biotechnology, sequence-specific separation , suffices for constructing a general-purpose molecular computer.Fifth, we illustrate that separation errors can theoretically be reduced to tolerable levels by invoking a trade-off between time, space, and error rates at the level of algorithm design; we also outline several specific ways in which this can be done and present numerical calculations of their per formance.Despite these encouraging theoretical advances , we emphasize that sub-stantial engineering challenges remain at almost all stages and that the ultimate success or failure of DNA computing will certainly depend on whether t.hese challenges can be met in laboratory investigations.