Run a series of errands around campus and you'll know how hard it is to figure out the shortest route among six different locations. Indeed, "The Traveling Salesman Problem," as mathematicians call it, is one of the hardest problems in mathematics. The challenge is to find, among all the possible routes you can take, one that passes through each destination point only once, and gets you back home again at the end by the shortest route possible. Amazingly, ordinary DNA can solve this problem.

For most of us, if we’re running a few errands, it's not a big deal if we don't take the shortest route. We just wander from place to place, hoping not to retrace too many of our steps. But finding the shortest route is critical to mail carriers delivering packages, trucking companies shipping freight along interstates between markets, and airlines scheduling flights in and out of dozens of major cities across the country.

The reason the problem is difficult is that the number of possible routes grows rapidly as the number of cities (or other destinations) increases. For six cities, there are just over 100 paths, for seven cities, there are almost 1,000, and for twelve cities, there are about half a billion possible routes. Even supercomputers bog down as the number of cities increases. But in 1994, Leonard Adleman, a computer scientist at the University of Southern California, showed that strands of DNA had the potential to solve this problem rapidly and efficiently.

That DNA might be able to perform calculations is not as far-fetched as it might seem. Above all, DNA encodes information. Adleman realized that several features of DNA might also allow it to be used as a compact calculator. First and most importantly, DNA is small, allowing billions of reactions to occur simultaneously in a small test tube. If each reaction can perform one calculation, then a tube of DNA becomes a microscopic, massively parallel supercomputer.

Second, DNA strands pair up with complementary strands. Adleman realized that if he could figure out how to represent cities and paths in separate strands of DNA, the pairing could be used to link them up in every possible combination, thus "calculating" all possible paths among the cities. The length of the resulting DNA strands would represent the distance taken along each "journey," and the shortest strand in the tube would represent the solution to the problem.

In Adleman’s approach, each city is represented by a single strand of DNA, say 10 nucleotides long. For instance, one city might have the code AAAAAAAAAA, while another might be CCCCCCCCCC (any random sequence of the four nucleotides would work just as well). Adleman’s insight was to realize that the path between cities A and C could be represented by a strand that can physically unite their DNA, namely TTTTTGGGGG. In this "half-and-half" strand, the T’s pair up with the last half of the A strand, while the G’s pair up with the first half of the C strand, thus linking the two "cities." Multiple cities could then be joined by multiple city-to-city paths, making a single long route from start to finish.

In his initial experiment, Adleman generated seven unique strands, one for each of seven cities, plus half-and-half strands for each of the possible city-to-city links (as with airline routes, not every city could make a direct connection to every other city). To perform the "calculation," all were placed in a small test tube with appropriate enzymes, and allowed to react. At the end, the strands were sorted by length using gel electrophoresis (see Chapter 13). Some very short strands were produced that didn’t have all the requisite links, as well as many overly long ones with repeated links. The shortest one that included all seven cities with only seven links between them could then be isolated and analyzed to reveal the exact path taken, thus solving the problem. Adleman’s publication of this experiment in the journal Science launched the field of DNA-based computing, which now involves dozens of researchers at the interface of molecular biology and computer science.

Will DNA replace silicon-based computers? Not anytime soon, according to Adleman. Only certain problems are suitable for this type of approach. In addition, with current lab techniques, isolating the DNA that embodies the solution to the problem is laborious, especially with more complex problems. However, neither is Adleman’s demonstration just a neat parlor trick. Adleman and others are hard at work looking at ways to use DNA computers to solve problems in code-breaking, and even in the assembly of microscopic machines. It seems likely that as DNA’s capabilities are explored further, new uses will be discovered for this oldest of information processors.

Return to Top
Return to Web Bits Index