DNA-algorithms and NP-completeness What is the relationship between DNA-algorithms and the complexity classes defined using Turing machines? What do the complexity measures like time and space correspond to in DNA-algorithms? Can they be used to solve instances of NP-complete problems like TSP that von Neumann machines can not solve feasibly in practice?
Soundbite answer: DNA computing does not provide a magic wand to solve NP-complete problems, even though some respected researchers in the 1990s thought for a time it might.

The inaugural DNA computing experiment was performed in a laboratory headed by the renowned number theorist Len Adleman.  Adleman solved a small Traveling Salesman Problem -- a well-known NP-complete problem, and he and others thought for a while the method might scale up.  Adleman describes his approach in this short video, which I find fascinating.  The problem they encountered was that to solve a TSP problem of modest size, they would need more DNA than the size of the Earth.  They had figured out a way to save time by increasing the amount of work done in parallel, but this did not mean the TSP problem required less than exponential resources to solve. They had only shifted the exponential cost from amount-of-time to amount-of-physical material.

(There's an added question: if you require an exponential amount of machinery to solve a problem, do you automatically require an exponential amount of time, or at least preprocessing, to build the machinery in the first place?  I'll leave that issue to one side, though.)

This general problem -- reducing the time a computation requires at the expense of some other resource -- has shown up many times in biologically-inspired models of computing.  The Wikipedia page on membrane computing (an abstraction of a biological cell) says that a certain type of membrane system is able to solve NP-complete problems in polynomial time.  This works because that system allows for the creation of exponentially-many subobjects inside an overall membrane, in polynomial time.  Well... how does an exponential amount of raw material arrive from the outside world an enter through a membrane with constant surface area?  Answer: it's not considered.  They're not paying for a resource that the computation would otherwise require.

Finally, to respond to Anthony Labarre, who linked to a paper showing AHNEPs can solve NP-complete problems in polynomial time.  There's even a paper out showing AHNEPs can solve 3SAT in linear time.  AHNEP = Accepting Hybrid Network of Evolutionary Processors.  An evolutionary processor is a model inspired by DNA, whose core has a string that at each step can be changed by substitution, deletion, or (importantly) insertion.  Further, an arbitrarily large number of strings is available at every node, and at each communication step, all nodes send all their correct strings to all attached nodes.  So without time cost, it's possible to transfer exponential amounts of information, and because of the insertion rule, individual strings can become ever larger over the course of the computation, so it's a double whammy.

If you are interested in recent work in biocomputation, by researchers who focus on computations that are real-world practical, I can offer this book review I recently wrote for SIGACT News, which touches briefly on multiple areas.