Adleman & DNA WAS Re: Gene construction advice needed
Richard P. Grant
rgrant at netscape.net
Tue Jul 11 02:52:29 EST 2000
In article <200007101647.MAA27841 at sirocco.cc.mcgill.ca>,
dalex at nexus.microimm.mcgill.ca ("(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
http://www2.mrc-lmb.cam.ac.uk/personal/rpg/ 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 http://www.gerbil.org.uk/
Please reply to rpg 'at' mrc-lmb.cam.ac.uk
Science Advisory Board: http://www.scienceboard.net/
More information about the Methods