A sticker-based model for DNA computation

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 phys ical substrate in which information is represented and of separation by hyb ridization as a central mechanism. However, unlike previous models, the sti ckers model has a random access memory that requires no strand extension an d uses no enzymes; also (at least in theory), its materials are reusable. T he paper describes computation under the stickers model and discusses possi ble 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 abo ut 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 sea rch 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 comp utation. Fourth, we show that a single essential biotechnology, sequence-sp ecific separation, suffices for constructing a general-purpose molecular co mputer. Concerns about errors in this separation operation and means to red uce them are addressed elsewhere (Karp ct at, 1995; Rowels and Winfree, 199 9). Despite these encouraging theoretical advances, we emphasize that subst antial engineering challenges remain at almost all stages and that the ulti mate success or failure of DNA computing will certainly depend on whether t hese challenges can be met in laboratory investigations.