In 1994, Adleman decided to use DNA to solve the directed Hamiltonian Path Problem, also called the Traveling Salesman Problem. He chose a classic computer problem to ensure that he would not be accused of picking a problem to fit the machine. In the Traveling Salesman Problem, a hypothetical salesman must determine the best travel route. For example, the salesman might need to travel from Los Angeles to New York, passing through three other cities--Dallas, Chicago, and Miami--on the way. Specific restrictions are placed on the itinerary. For example, the airline allows a flight from Los Angeles to Chicago, but not from Miami to Chicago. To avoid missing a destination, visiting a city twice, or not making it to the final destination of New York, only one itinerary is possible: beginning in L.A., the salesman flies to Chicago, Dallas, Miami, and then to New York.

This problem, while easy with a few cities, becomes problematic for an individual and for a computer when the number of cities increases and the number of possible routes increases exponentially.

Adleman solved this problem with a DNA computer, a clear liquid in a test tube. He assigned each of seven cities a different 20-nucleotide genetic sequence, generated all possible itineraries, and then selected the correct one. This would not be the ideal approach using a silicon computer because it would take too long to search all possible routes one after another. But DNA is well suited to this shotgun approach. Enzymes working on many DNA molecules simultaneously favor a massively parallel selection process.

Using gel electrophoresis, which analyzes the size of DNA, Adleman was able to eliminate many routes that would require visiting some cities twice by screening for only DNA sequences that were 140 nucleotides long (seven cities times 20 nucleotides). Then he used affinity purification to separate the DNA molecule containing the correct sequence.

When Adleman announced his breakthrough, scientists from around the world gathered for the first conference on DNA computing. The field is still going strong--the 14th International Conference on DNA Computing took place June 2-6 in Prague. And money continues to flow into the research. Anthony Macula, an associate professor at the State University of New York at Geneseo, is funded by the U.S. Air Force to harness DNA's speed and increase computation capacity. He also has a large National Science Foundation grant to train undergraduates to perform research in biomathematics. At the same time, he is using private funds from CFD Research of Huntsville, Alabama, to create a simulated DNA computer that acts as a tool for understanding disease.

The initial applications of DNA computing solved the types of problems in computation and logic that computer scientists traditionally used to measure their programming skills and the powers of generations of silicon-based computers. DNA computers have attacked the Knight problem in chess (using RNA to compute how to place a collection of knights on a chessboard so that none can attack each other) and the knapsack problem (figuring out how to choose objects for a knapsack to maximize their value within a certain weight limitation). They've even consistently beat human opponents at tic-tac-toe.

Researchers at Stanford University and Princeton University have suggested using the parallel processing ability of a DNA computer to break the United States government's digital encryption standard; while the system might keep data secure from silicon computer decryption, DNA would work like a billion silicon computers at once, each trying a different combination.

As with silicon-based computers, many of the theoretical and practical advances in DNA computing are coming from Japan. In March 2008, a Japanese team from Waseda University reported in Biosystems that DNA computing is an appropriate way to solve problems of "clustering"--analyzing concepts and algorithms in huge, heterogeneous data sets to reveal meaningful relationships.

But DNA computers have their own, unique drawbacks. Using Adleman's original DNA computer for a Hamilton path problem with 200 cities would require an amount of DNA that was heavier than the weight of the earth. Plus, DNA replication can introduce errors in the DNA sequence. And even when the DNA itself may contain the right answer, analyzing the DNA to get the answer can be a cumbersome

1 2 3 4 Next Page