Computing Books

“These potential advantages of DNA computing over the traditional approach and the seminal experimental work of Adleman, demonstrating the practical in vitro implementation of a DNA algorithm for solving an instance of the Hamiltonian path problem, caused a strong increase of interest in DNA computing over the past years. Although the set of “bio-operations” that can be executed on DNA strands in a laboratory (including operators such as synthesizing, mixing, annealing, melting, amplifying, separating, extracting, cutting, and ligating DNA strands) seems fundamentally different from traditional programming languages, theoretical work on the computational power of various models of DNA computing demonstrates that certain subsets of these operators are computationally complete. In other words, everything that is Turing-computable can also be computed by these DNA models of computation. Furthermore, it has also been shown that universal systems exist, so that the programmable DNA computer is theoretically possible.
The algorithms for DNA computing that have been presented in the literature use an approach that will not work for NP-complete problems of realistic size, because these algorithms are all based on extracting an existing solution from a sufficiently large initial population of solutions. Although a huge number (≈ 1012) of DNA molecules (i.e., potential solutions to a given problem) can be manipulated in parallel, this so-called filtering approach (i.e., generate and test) quickly becomes infeasible as problem sizes grow (e.g., a 500-node instance of the traveling salesman problem has > 101000 potential solutions).”
― Laura F. Landweber, Evolution as Computation