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...
participants (4)
-
cactus@bb.hks.net -
cjl -
Hal -
rishab@dxm.ernet.in