Computation with biomolecules

Publisher Website
Google Scholar
Abstract
In 1994 Leonard Adleman used DNA strands to encode cities and flights to show that itineraries satisfying special conditions could be constructed and isolated in the laboratory (1). The abstract of this seminal paper concludes, “This experiment demonstrates the feasibility of computation at the molecular level.” Within months Richard Lipton argued (2) that fundamental problems concerning the truth of logic statements also could be addressed in this new way. In this issue of PNAS, Faulhammer et al. (3) use laboratory techniques with relatively low error rates in an experiment realizing Lipton's earlier design. However, within a year after Adleman's article, it already was known such approaches can require unrealistic quantities of materials, leading Stemmer (4) to suggest using existing laboratory procedures to evolve realistically sized molecular populations by inducing variation and selection. Such evolutionary computation is an established paradigm for conventional computers. Interest is beginning to focus on DNA-based implementations (5–7) of evolutionary computation because of its alleged robustness in the presence of errors and its ability to exploit the massive parallelism and memory inherent at the molecular level. By its success in the laboratory, Adleman's work (1) sparked intense excitement and marked the birth of a new field, DNA computation. Adleman's insight was that the ability of single-stranded DNA to seek and bind to a complementary strand allows DNA to carry out massively parallel computation. Although it seems doubtful that biologically based computers will be suitable for general-purpose applications, there are some especially difficult problems where conventional computers lack the massive parallelism and huge memory capacity inherent in molecular computation. For example, the so-called “NP-complete” problems that apparently require exponentially increasing computing time with a linear increase in problem size are notoriously difficult for silicon computers to solve. Thus, are there special applications where biomolecular computation can …