Wettestware - computing with DNA

PLAY A WORD-ASSOCIATION GAME WITH DNA. What comes to mind? Genes. Heredity. A certain West Coast trial. Computation--no, that probably won't make your list. But it should. While David Deutsch and other physicists are trying to figure out how to build a quantum computer, Len Adleman, a mathematician at the University of Southern California, has already used DNA molecules to solve a classic math problem. Granted, the problem was rather simple, but Adleman clearly demonstrated DNA's computational potential--and that's a lot more than can be said for anyone working with photons.

Adleman tackled a version of the "traveling salesman" problem, in which a person is presented with a map of a certain number of cities, a number of specified roads connecting the various cities, and a starting and an ending point. The task is to find a path that passes through each city only once. With just a few cities and roads, the problem can be solved with pencil and paper. But as soon as you get up to as few as 60 cities, a conventional computer, which must process all possible routes one at a time, takes impossibly long to find the answer.

How does DNA do better? To understand, you first need to recall the basic structure of the DNA molecule, which normally consists of two strands intertwined to form the famous double helix. Projecting from each strand at regular intervals, like the rungs on a ladder, are four chemical subunits--the bases adenine, cytosine, thymine, and guanine, usually abbreviated as A, C, T, and G. An A on one strand always binds with a T on the other; C always binds with G.

As set up by Adleman, the task was to find the correct route through 7 cities connected by 14 streets. He represented each city as a single strand of DNA 20 bases long. The sequence C-C-T-A-G-T-C-A-G-A-A-C-G-T-T-C-G-A-A-A, say, might represent Chicago; C-C-C-A-T-T-A-A-A-G-A-T-T-A-C-C-C-G-T-C might be New York.

Now we get to the clever part: picture these two 20-base-long DNA "cities" laid end to end. A road connecting the two is represented by another 20-base strand of DNA that partially overlaps both cities: the first 10 bases of the road will be complementary to the 10 bases at the end of one city and to 10 at the beginning of the other. Since T always binds to A, and G to C, the sequence T-G-C-A-A-G-C-T-T-T-G-G-G-T-A-A-T-T-T-C, for example, would link Chicago and New York.

Adleman mixed in a test tube some 100 trillion DNA molecules containing all 7 cities and 14 roads, and let them join up as they saw fit. Many of the combinations that formed from the random pasting turned out to be useless--two cities repeatedly linked by the same road, for example. But because Adleman used so many copies of each DNA city and street, at least one of the combinations that formed was bound to link the cities correctly. Using standard biomolecular techniques, Adleman was able to extract the molecule that encoded the route that passed through each city just once.

Though he took a week to solve a fairly simple problem, Adleman opened up a whole new way of thinking about what makes a computer a computer. "DNA is designed by nature to process information," points out Eric Baum, a computer scientist at the NEC Research Institute in New Jersey. Instead of using the standard computer binary code of zeros and ones, DNA uses A's, T's, C's, and G's. And rather than carrying out a few calculations simultaneously, trillions of DNA molecules can react at once.

Other researchers have expanded on Adleman's idea. Richard Lipton, a Princeton computer scientist, showed that a DNA computer could, in principle, break a coding system widely used by government agencies and private corporations. The system, known as the data encryption standard system, or DES, has [2.sup.56] possible ways to encrypt a message. Each involves 16 stages of scrambling the order of parts of the message, adding parts together, and rescrambling. The sentence "He left the room" might be scrambled as follows: First it would become "He the room left." Then fragments of the sentence would be added: "He room the room left he he," and so on for 14 more rounds of contortion until the simple message is lost in a thicket of disguise. (And of course, all this camouflaging is done mathematically, after the words have been turned into numbers.) It's practically impossible for a conventional computer to break the code by testing one of the [2.sup.56] keys at a time. Even a supercomputer, performing thousands of operations at once, would take decades. But just about two-tenths of an ounce of DNA in solution would probably be enough to solve the problem.

"It would take about four months to make this magic soup that would contain all the answers," says Lipton. "But once that's done you can break the system at relatively rapid rates."

DNA will probably be useful only for certain specialized computing tasks. Even though a DNA computer can perform an amazing number of calculations in an instant, extracting an answer is time-consuming. "You're not going to throw away your laptop," predicts Lipton. "Or it's not going to slosh around as you type on it. Of course, in the 1950s if you had said everyone would eventually own a computer, you would have been put in a loony bin. Maybe I'm wrong, too."

COPYRIGHT 1995 Discover
COPYRIGHT 2004 Gale Group