INFORMATION TECHNOLOGY

DNA-Based Computers Could Race Past Supercomputers, Researchers Predict

By VINCENT KIERNAN

But the glass, less than an inch square, is one key to building a radically different kind of computer, one that uses DNA instead of silicon to store and manipulate information. Eventually, proponents say, the technology could produce DNA-based computers that would be better even than supercomputers in solving certain types of problems.

That prospect is still far off. At present, the technology for DNA computing is so rudimentary that demonstrations have been limited to questions that a human could answer without any computer at all. But researchers in the United States and Japan are encouraged by the strides they have made in DNA computing in the three years since research in the field started.

A conventional computer represents information on silicon chips as a series of electrical impulses -- zeroes and ones -- and manipulates the information by performing mathematical computations with those zeroes and ones.

By contrast, a DNA computer represents information as a pattern of molecules in a strand of synthetic DNA.That information is manipulated by subjecting it to precisely designed chemical reactions that may mark the strand, lengthen it, or even destroy it.

"It's a different way of thinking about computing. It's a different way of thinking about chemistry," says Dr. Corn, a chemistry professor at the University of Wisconsin at Madison who is collaborating on a DNA-computer project with three other Madison faculty members: Lloyd M. Smith, a chemistry professor; Max G. Lagally, a materials-science professor; and Anne E. Condon, a computer-science professor.

The Wisconsin approach would use the gold-plated square of glass as something akin to a conventional memory chip. As many as a trillion individual strands of DNA would be anchored to the glass, each strand containing information being stored in the DNA computer.

A rival approach, pioneered by Leonard M. Adleman, of the University of Southern California, allows the bits of DNA to float freely in a test tube. Dr. Adleman, a professor of computer science, created the field of DNA computing in 1994, when he published a paper in Science describing how he had used his test-tube approach to solve a classic problem in mathematics: how to organize a traveling salesperson's itinerary among seven cities so that the traveler visits all seven cities without passing through any city more than once.

In both the Wisconsin approach and Dr. Adleman's, each DNA strand represents one possible answer to the problem that the computer is trying to solve. The strands have been synthesized by combining the building blocks of DNA, called nucleotides, with one another, using techniques developed for biotechnology. The set of DNA strands is manufactured so that all conceivable answers are included. Because a set of strands is tailored to a specific problem, a new set would have to be made for each new problem.

Most of the possible answers are incorrect, but one or a few may be correct, and the computer's task is to check each of them and winnow out the incorrect ones. The DNA computer does that by subjecting all of the strands simultaneously to a series of chemical reactions that mimic the mathematical computations an electronic computer would perform on each possible answer.

For example, some mathematical operations are performed by enzymes whose function depends on the specific values of information in one or more spots on the strand. An enzyme might add a value of 1 to the end of a strand if either of two specific values in the strand were 1. By orchestrating many such operations, researchers can use the enzymes to perform sophisticated logical and mathematical computations.

When the chemical reactions are complete, researchers analyze the strands to find the answer -- for instance, by locating the longest or the shortest strand and decoding it to determine what answer it represents.

The advantage of the DNA approach is that it works in "parallel," processing all possible answers simultaneously. An electronic computer can analyze only one potential answer at a time. Problems that have many possible answers can take a long time to solve, even for supercomputers that contain hundreds of electronic processors operating in parallel.

Since Dr. Adleman's success three years ago, other researchers have flocked to the field, enticed in part by grants from the National Science Foundation and the Pentagon's Defense Advanced Research Projects Agency. Much of the military's interest arises from the increasing sophistication of encryption techniques that other countries can use to encode their data. As a result, Washington needs ever-more-powerful computers for code breaking.

Three researchers -- Richard J. Lipton, a computer-science professor at Princeton University, Daniel Boneh, an assistant professor of computer science at Stanford University, and Christopher T. Dunworth, a computer-science doctoral student at Princeton -- have outlined a way for a DNA computer to crack messages coded with the U.S. government's own Data Encryption Standard, which is used to protect a wide range of data, including telephone conversations on classified topics and data transmissions between banks and the Federal Reserve.

When a message is encrypted according to the standard, the coding relies on one of 72 quadrillion "keys," or encoding instructions. A message coded in this way is hard to crack, because there is no way to know which specific key was used. Testing all possible keys on an electronic computer would take an enormous amount of time.

But a DNA computer could test all of the keys at the same time, find the right one, and pass it to a human code-breaker for use in translating the message. A highly automated version of a DNA computer might be able to produce the answer in as little as two hours, according to Dr. Adleman and colleagues from U.S.C. and the California Institute of Technology.

At this early stage, however, researchers are trying to advance DNA computing by solving small problems, ones with answers that can be easily calculated by conventional means.

For example, Albert Libchaber and three colleagues at the NEC Research Institute, in Princeton, N.J., reported in the October 17 issue of Science that they had used DNA computing to answer a simple-sounding mathematical question known as the "maximal clique problem": If you have a set of points, with a variety of connections between the points, what is the largest subset of the points in which all of them are directly connected with one another? Or -- in real-world terms -- if you operate an airline, how many of the cities you serve are linked to one another by non-stop service?

If the airline serves only a handful of cities, the question is easy to answer. But if the airline has expanded to include, say, more than 100 airports, the task becomes so complex that a conventional computer would require months to churn out the answer. The problem is one with significance for travelers, because they prefer non-stop flights.

For their experiment, Dr. Libchaber and his colleagues chose a modest example, which used six points with 11 connections among them. Four of the points are all connected to each other directly. Those four points are the "maximal clique" for that particular graph.

To compute that answer with DNA, Dr. Libchaber's team first created a set of strands of genetic material to represent every conceivable arrangement of the six points and the possible connections among them. An arrangement with many connections was represented by a short length of DNA, while an arrangement with few connections was represented by a long strand.

The strands were placed together in a test tube. The researchers then used enzymes to eliminate strands representing any connections not included in the problem's original 11. Any strand representing a connection between cities 1 and 5, for example, was destroyed by a specific enzyme tailored to do just that. The scientists then sorted the remaining DNA strands to find the shortest strand, which corresponded to the arrangement with the most connections among the points.

To find out precisely which points were connected in that strand, the researchers used a virus to infect an Escherichia coli bacterium with the strand of DNA. The bacterium manufactured multiple copies of the strand. After about a day, the researchers were able to extract enough of the genetic material to read its code, representing the correct answer -- in this case, connections among points 2, 3, 4, and 5.

The DNA computer took about a day to produce that answer, which a conventional computer would have yielded in the blink of an eye. But for larger versions of the problem -- perhaps 50 cities or more -- the DNA computer probably would be faster than a conventional computer, particularly if there are further advances in processes for synthesizing and decoding DNA quickly, says Qi Ouyang, a research scientist at the NEC Research Institute and a member of Dr. Libchaber's team.

The Wisconsin researchers, using DNA that is anchored to a surface, have been trying to compute the answer to what's known in computer-science circles as the "satisfiability" problem. It seeks a sequence of zeroes and ones to use in a predetermined formula so that the formula produces the value 1.

An ordinary computer would have to try each possible sequence of zeroes and ones in the formula until it found a sequence that resulted in the desired answer.

But the Wisconsin researchers represent each possible sequence of zeroes and ones as a separate strand of DNA attached to the gold-covered glass plate. They are developing a series of chemical reactions, representing the mathematical formula, that would mark all of the strands that do not satisfy the formula. After the reactions are completed, the marked strands would be cut away with enzymes. The remaining strands, if any, would represent numerical values that satisfy the formula.

At present, the Wisconsin researchers are trying to develop the technology for solving a five-variable formula. That's relatively simple, because the system has to check only 32 five-digit sequences. The task will become more difficult as the researchers add more variables. There are one million possible combinations of zeroes and ones in a 20-variable formula, and one billion in a formula with 30 variables.

One of the principal advantages of the Wisconsin approach, Dr. Corn says, is that the DNA strands are firmly anchored to the gold-covered glass slide and thus are less likely to be mistakenly siphoned away during the chemical processing. If that happened, a correct answer to the problem could literally go down the drain.

The Wisconsin approach also can build on tried-and-true methods of commercial biotechnology, which often uses strands of DNA attached to glass beads or other objects, he says. "The best place to do DNA computing, we feel, is on a surface. It's much easier to do it on a surface than in a test tube."

Dr. Adleman believes that his test-tube approach is better. A test tube can hold more genetic strands in its three-dimensional volume than a glass slide, so a test-tube DNA computer could tackle larger problems, he says.

Regardless of the approach, many technological challenges remain before DNA computing can be widely used. Researchers must develop techniques to reduce the number of computational errors produced by unwanted chemical reactions with the DNA strands. And they need to eliminate, combine, or accelerate the steps in processing the DNA.

With an eye toward such improvements, some researchers are envisioning new uses for the technology. Although the DNA computer's advantages for massive problems have received the most attention, "that may have gotten a little too much hype," says John H. Reif, a professor of computer science at Duke University.

He believes that the DNA computing, which he prefers to call "biomolecular computation," may have its biggest impact in completely different ways -- for example, enabling a computing system to read and decode natural DNA directly. Such a computer also might be able to perform DNA "fingerprinting" -- matching a sample of DNA, such as that in blood found at a crime scene, with the person from whom it came.

The DNA computer might be a cost-effective way to decode the genetic material of humans and other living things, and it might be able to create "wet data bases" of DNA for research purposes that would eliminate the time-consuming task of translating DNA into a form that can be stored in an electronic computer. "That," Dr. Reif says, "could be the killer application for biomolecular computation."

Chronicle map by Jojo Gragasin Researchers think computers made from DNA would be well suited to tackle problems that are time-consuming for conventional computers. Sequences of DNA can be crafted to represent specific patterns of information, and chemical reactions manipulate the DNA -- much as mathematical computations operate on information stored in today's computers. One such problem is depicted above: An airline serves six cities, but not all of the cities have nonstop service with each other. What is the largest group of cities that all have nonstop service with one another? The answer is four (cities 2, 3, 4, and 5). Computers now solve such problems by trial and error. But if hundreds of cities were involved, a conventional computer would require years to find the answer. A DNA computer, on the other hand, tests all possible answers simultaneously, offering the prospect of much speedier solutions.