DNA Computing is a rising interdisciplinary field, that uses the four DNA bases (A, T, C, G) to perform computation. It attempts to exploit the relationships between the base pairs to create faster, in some situation, computational machines. The field was created by Leonard Adleman in 1994. He demonstrated it was possible to use DNA computation to solve a trivial version of the Hamiltonian path problem. It was later shown by other researchers that this model of computation is Turing complete, so while using DNA computation may be faster in some cases, it does not provide any additional power over existing computational models. There is a (not-so) quiet hope from those in the field that DNA computers will at some point surpass silicon in commercial and industrial applications. What actually opens the door for this possibility is that DNA computers inherently compute in parallel. To better understand this let us consider how Adleman set up his original experiment.

In case you aren’t familiar with the problem: Given a graph G = (V,E), find if there is a path that touches each vertex only once and both begins and ends on the same vertex. To use DNA to do this problem, we assign a unique string of DNA to each vertex, and then a string of DNA to each edge. How we build the edges is key to how the DNA computing model works. The first half of the edge string is the compliment of the last half of the vertex it connects to one side. The other half of the edge string is the compliment of the first half it connects to on the other side. This way, the edge strings naturally try to form base pairs with the verticies they connect.

The goal then is that we take a bunch of enzymes encoded as our verticies and edges, dump them in a test tube, let the DNA do its natural processes, and then observe what connections were formed. The connections formed will be viable paths in the graph we constructed, and the fact that we dumped a LOT of copies of the enzymes into the test tube means this computation was done massively in parallel. With any moderate amount of copies of the DNA strings we would be sure to hit all possible combinations. All that is left to do is find a DNA string in the test tube thats long enough such that it actually satisfies the Hamiltonian path we are trying to discover.

Of course this is a fairly crude example, but it shows how DNA can be used to perform computations quickly, massively in parallel.  At this point the field is still in its infancy.  Aldeman and his team of researchers are still working on improvements in the model, as well as more examples of its functionality.  Like all parallel computation, it holds big consequences for security and cryptography, as it has been noted that they amount of DNA required to compute the 2^56 DES keys would occupy only a handful of test tubes.  Still, DNA computation, and its sister, molecular computation, have a long way to come before they are ready for wide stream use.