Search This Blog

25 March 2008

DNA solves all your tough problems, like the 13-node Travelling Easter Bunny Problem which no one has yet solved. (AMY! HELP!)

Click, it gets bigger and easier to read.

I just received Dover's clip art "Classic Full-Color Illuminated Borders," in book and on CD, and this one looked pretty nice.

Well, it's a border, so I have to put something inside.

About 12 years ago Leonard Adleman considered that a great deal of what DNA "does" is essentially digital computing. DNA stores vast volumes of information in a remarkably stable and reliable way for remarkably long periods of time, and all in a fairly hostile thermal and chemical and radiation environment. If it screws up and can't fix the tiny error, you get some loathsome genetic disease and die; usually you just aren't born in the first place.

It rarely screws up, because it's constantly fixing errors with an evolved set of very powerful Error-Correcting techniques. In other words, while our DNA is constantly replicating -- making millions of identical copies of itself -- it's also constantly fixing almost every tiny mistake which pops up. Biological life would be impossible if DNA wasn't so good at correcting such a high percentage of errors.

Adleman cooked up a scheme to try to harness this computing power using arbitrarily synthesized strands of DNA. He chose as a first demonstration the famous "Travelling Salesman Problem" (TSP), a classic math nightmare requiring vast volumes of computation from combinatorics and graph theory. He picked a TSP with 7 nodes -- just like Vleeptron's Travelling Santa Problem, which RamanuJohn solved on his more conventional high-speed general-purpose digital personal computer.

So, in just a few seconds, in a glop of wet goop in a Petrie dish, the strands of DNA analyzed and compared the 5040 different possible paths the Salesman could take to travel to each city only once, and the DNA found the shortest path. (It's possible Adleman's DNA only had to analyze 2520 paths, because the length of path CBDAE is the same length of its reflection, EADBC.)

Actually, the Santa problem was a little harder, it had 7 kids' houses for Santa to visit, but he started at the North Pole and had to return to the North Pole after delivering all the toys.

This illustration is from an article in the journal of EMBO, the European Molecular Biology Organization.

Vleeptron still has received no solution to the 13-node Travelling Easter Bunny Problem, and Easter (for Catholics and Protestants anyway) has come and gone. That sucks. Now Bob actually has to get to work and force the new Vleeptron Supercomputer ("Powercow") to solve the goddam thing.

This is going to hurt.

Amy, can you synthetically sequence strands of DNA? Do you have a clue what this Adleman guy did and how? How hard can this be, huh?

No comments: