rishab@dxm.ernet.in writes:

srctran@world.std.com (Gregory Aharonian): [on Internet Patent News Service] Scientist uses DNA sequences to solve Hamiltonian path problem of combinatorial mathematics, a precursor of the PTO's headache of including biotechnology in it software prior art searches. Think of Hopfield's paper on using neural nets for the traveling salesman problem to predict where DNA computing will end up.

There is an interesting crypto connection here in that the work was done by Len Adelman of USC, the "A" of RSA. This research was reported in a recent issue of Science, but I am going by a report in Science News. What I will describe is the gist of the work, but I may have some details wrong. The Hamiltonian path problem asks whether there is a path through a given graph which passes through each node exactly once. Adelman took a smallish graph and encoded each of the 20-odd links as a particular short DNA sequence. He then made DNA sequences which consisted of pairs of these codes connected together for each case of two paths which shared a node. Then he had some other pieces of DNA which could stick these together if the codes on the end matched. The net result was that every possible path through the network would be represented by a DNA strand which would self-assemble. Then it was a matter of filtering the DNA for strands of the proper length which did not have any duplicate nodes. The SN article wasn't clear about how this was done. So, my take on this is that the clever part was casting the problem in a way which matched the behavior of DNA strands. Realizing that the Hamiltonian path problem can be expressed in terms of self-assembly of short strands was the real trick. I doubt that any reasonable extension of this technique would do modular arithmetic or the complicated logic of DES, so this presumably doesn't represent any immediate threat to crypto algorithms. I suppose the question would be whether there could be a compiler which would take logic equations and turn them into DNA strands which mirrored the equations. That seems unlikely but more plausible IMO than the quantum computers people have discussed. Hal