From: Hal <hfinney@shell.portal.com>
Date: Sun, 20 Nov 94 21:56:10 PST
To: cypherpunks@toad.com
Subject: Re: DNA solution to Hamiltonian circuit?
In-Reply-To: <gate.P994Vc1w165w@dxm.ernet.in>
Message-ID: <199411210556.VAA26633@jobe.shell.portal.com>
MIME-Version: 1.0
Content-Type: text/plain


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