World's First Game-Playing DNA Computer

An anonymous reader writes "NewScientist.com posted an article today about the first game-playing 'computer' powered by DNA logic. An interesting read, although not at all a practical alternative for those looking to replace their PlayStation2 with the next great platform." The machine is "...an enzyme-powered tic-tac-toe machine that... uses a complex mixture of DNA enzymes to determine where it should place its nought or cross, and signals its move with a green glow."

Comments

Summary for those to lazy to RTA

[stienman]

Essentially they have 9 enzymes to specify the nine possible moves of the player. Once a move is chosen the enzyme for that position is added to each of the nine wells. The DNA inside each well is aware of its location, and, of course, each of the player's moves since the enzymes are added to each well.

The DNA in each well makes a simple logic decision based on all the enzymes it currently detects and turns green to indicate that the dna 'computer' is choosing to move there.

Overall it's an interesting logic puzzle, not only because it's done in DNA, but because the method involves seperate logic cells which have no means of communication - only the knowledge that they know everything that their brethren know.

It has weaknesses in that it's easy to fool them all individually so they all light green.

Probably has many good applications in chemical sniffing and quite possibly future DNA analysis speed ups.

-Adam

DNA based computer used to solve TSP

[GillBates0]

I submitted a related story about another article on CNN today.

Apparently, Leonard Adleman of the University of Southern California used his DNA based computer to solve the travelling salesman problem by exploiting the predictability of how DNA interacts. "Adleman used his computer to solve the classic "traveling salesman" mathematical problem -- how a salesman can visit a given number of cities without passing through any city twice -- by exploiting the predictability of how DNA interacts. Adleman assigned each of seven cities a different strip of DNA, 20 molecules long, then dropped them into a stew of millions of more strips of DNA that naturally bonded with the "cities." That generated thousands of random paths, in much the same way that a computer can sift through random numbers to break a code. From this hodgepodge of connected DNA, Adleman eventually extracted a satisfactory solution -- a strand that led directly from the first city to the last, without retracing any steps. DNA computing was born".

Apparently, a single gram of DNA can store as much information as a trillion CDs.

Re:DNA based computer used to solve TSP

[jfengel]

The problem, unfortunately, is that TSP is still an exponential problem. Solving it for seven cities is reasonably trivial. Although DNA is extremely small, an exponential about of it is not. By the time you get to 200 cities, you start requiring masses of DNA larger than the planet.

DNA based solutions basically call for you to use DNA to sort through every possible combination. Since it's all done in parallel, it can be done fairly fast, as long as you provide enough DNA. However, the only interesting problems are exponential ones (since polynomial problems can already be solved fairly fast), and you're basically trading material for time.

A 200 city TSP problem really isn't all that much. Some crypto breaking is equivalent to a 1,000 city TSP. The whole point of NP-completeness is that if you can solve one of them you can solve all of them. Traveling salesman is easy to explain, and more interesting than, say, 3SAT. So solving TSP for large numbers would be interesting, but sadly the solutions don't scale.

More comp-sci background: These problems are NP in that they are "nondeterministic polynomial". That is, you can check a proposed solution in polynomical (read: reasonable) time. If you guess right the first time, you can "solve" the problem immediately. The trick is guessing right the first time. But you don't have to with DNA: you can use the molecules to check all solutions at once, which is equivalent to guessing right the first time.

The "complete" part means that one NP-complete problem can be reduced to another in polynomial (again, read reasonable) time. So if you can solve TSP, you can solve all the other NP problems, which include scheduling, some cryptography, and a bunch of other interesting stuff.

Sadly, the numbers get big. 10^20 DNAs weighs only micrograms, but 10^200 DNAs weighs 10^170 tons. That's why we use it for crypto: it's hard to do. Just solving it in parallel doesn't help, because there are too many things to do in parallel.

There may be uses for DNA computing; note that the article talks more about sensors than math problems. So don't oversell it for math problems.