DNA solution to Hamiltonian circuit?

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.

Uhh! This was in one of Greg's 'random list of story titles' - he's yet to
provide details. As Hopfield didn't really 'solve' the TS problem, but made
it easier to solve a class of maps, this may not mean that there will be any
significant effect upon Cypherpunk tech based on NP-hard graph problems (such 
as Zero Knowledge proofs) - but it would be interesting to know _what_ it's 
all about.



-----------------------------------------------------------------------------
Rishab Aiyer Ghosh             "Clean the air! clean the sky! wash the wind!
rishab@dxm.ernet.in                   take stone from stone and wash them..."
rishab@arbornet.org
Voice/Fax/Data +91 11 6853410  
Voicemail +91 11 3760335                 H 34C Saket, New Delhi 110017, INDIA

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

On Sun, 20 Nov 1994, Hal wrote:

> 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.

[ . . . ]  reasonably accurate summary elided

> 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.

It's in the Nov. 11 issue of Science, accompanied by a nice Perspectives 
piece that someone with a better appreciation of the math might be able 
to understand.  Hal (or anyone else on the list who is willing to explain 
a little of the math to me, off the list) will get a free lesson in 
Molecular Biology and the polymerase chain reaction in return that should 
explain the physical construction of this  *genetic AlGorethem*   :-)


C. J. Leonard                     (    /      "DNA is groovy"
                                   \ /                - Watson & Crick
<cjl@welchlink.welch.jhu.edu>      / \     <--  major groove
                                  (    \
Finger for public key               \   )
Strong-arm for secret key             /    <--  minor groove
Thumb-screws for pass-phrase        /   )

In article <Pine.SOL.3.91.941121222232.4011A-100000@welchlink.welch.jhu.edu>,
cjl <cjl@welchlink.welch.jhu.edu> wrote:
>It's in the Nov. 11 issue of Science, accompanied by a nice Perspectives 
>piece that someone with a better appreciation of the math might be able 
>to understand.

Yup.  Anybody who wants a copy, send me mail.  I'll also be putting it
up on the Web once I finish typing it in.
-- 
Todd Masco     | According to the US dept of Justice Statistics, 3.98% of the
cactus@hks.net | US population is in prison -- the highest ratio in the world.
  There's no place...