Adleman & DNA WAS Re: Gene construction advice needed

Richard P. Grant rgrant at
Tue Jul 11 02:52:29 EST 2000

In article <200007101647.MAA27841 at>, 
dalex at ("(David Alexander)") wrote:

> Molecular computation of solutions to combinatorial problems. 
> Adleman LM 
> They were trying to solve the 'salespersons' problem.
> i.e. finding the shortest distance between a set of destinations.
> without visiting any destination twice.
> (it's an easy problem if there are only 4 or 5 destinations,
>  but with 10, 100 or 1000, it becomes very complicated
>  especially  if there are limitations on any of the destinations
>  i.e. you can go from A to B, but not from B to A)

Known as the Hamiltonian Path Problem, this is in the class of problems 
where the computing time required increases exponentially with the 
complexity of the problem, rather than in a linear fashion.

I wrote a brief article which mentioned this for the Biochemist - go to  and follow the 'Molecular 
Computing' link.  There's a URI to an idiots' guide in the references, 
IIRC.  About a wek before that was published, a similar article appeared 
in Nature, which may be worth looking up if you're interested.

> To make a long story short, they created an oligo for
> each possible trip - but designed them in such a way
> that each destination had an unique  sequence.
> They threw all of the possible oligos in together,
> amplified them, separated them by size,
> and isolated the product of the appropriate size 
> to give all destinations, without visiting any twice.
> (i.e. if you had 7 destinatinos, the fragment would be
>  the length of 6 oligos - or maybe 7 if you had to
> return to the first destination....)

That's more or less it.  The problem - for the computational side of it 
- is that a problem that one could solve with a pencil and paper would 
take a week with DNA . . .  and to increase the complexity so that it 
would take inordinately long on a supercomputer - this DNA-based 
approach lends itself to parallel 'computing' - would take literally 
tonnes of oligo DNA.

Nice proof of principle, though!  :)


Richard P. Grant MAD Phil
Please reply to rpg 'at'
Science Advisory Board:

More information about the Methods mailing list