Molecular computing in a DNA soup.

Putting on a lab coat, getting out test tubes, and handling chemicals aren't normally part of a computer scientist's routine for solving a mathematical problem. But when the answer is encoded in strands of DNA, hands-on computing in the biotechnology laboratory becomes necessary.

Computer scientist Leonard M. Adleman of the University of Southern California in Los Angeles has taken just such a route. He has ventured into the laboratory to use the tools of molecular biology -- simple DNA manipulations -- to explore the possibility of computing directly with molecules.

In the Nov. 11 SCIENCE, Adleman describes a laboratory experiment in which he solved a computational problem that involved finding a particular path through a maze of points and links. "This is the first example, I think, of an actual computation carried out at the molecular level," Adleman says.

Adleman's guinea pig was a particular network, or graph, consisting of seven points (called nodes or vertices) and 14 links (known as edges) connecting the points in various ways (see diagram). Identifying each node as a city and each link as a one-way, nonstop flight between two cities, one has to determine whether there is a route that takes a traveler from a given starting point to a given end point and passes through each city exactly once. For this example, Adleman knew, there is only one solution.

[CHART OMITTED]

Mathematically, this is known as the directed Hamiltonian path problem, and it serves as a surrogate for a wide variety of practical computational problems.

Adleman proceeded by assigning each of the seven cities a unique code name in the form of a short DNA sequence made up of 20 nucleotides. The four different types of nucleotides are designated C, G, T, and A, and the cities' codes were written as some combination of these letters.

By replacing A with T, T with A, G with C, and C with G, he also created a complementary DNA sequence for each city code. Such a string of nucleotides would stick to its mate.

Adleman then constructed each of the 14 links by attaching the last 10 nucleotides of the DNA code for the originating city to the first 10 of the destination city. To begin his experiment, he obtained small quantities of each of the DNA sequences representing the 14 links and the complement codes for the seven cities.

Adleman then mixed together pinches of each of these 21 powders in a test tube and dissolved them in water. This caused the DNA strands to join end to end, forming longer sequences. The complementary strands served as splints to hold the pieces together. This reaction resulted in the formation of DNA molecules encoding an enormous number of random paths through the graph.

The remaining steps involved isolating out of the trillions of molecules present the one type of DNA strand that corresponds to the solution of the route problem.

"What you know about the winning molecule is that it has to start with the right DNA name and it has to end with the right DNA name, and it must have the DNA names of all the cities in between," Adleman says. "You [will also know] how much it will weigh and how many nucleotides long it will be."

Advances in molecular biology have made such separations practically routine. Adleman spent a week in the laboratory obtaining his result. "In the end, you wind up with a test tube in your hand containing just the Hamiltonian path molecules," he remarks.

"In essence, Adleman has used the enormous parallelism of solution-phase chemistry to solve a hard computational problem," David K. Gifford of the Massachusetts Institute of Technology comments in the same issue of SCIENCE.

"My goal was to show feasibility," Adleman says. "Whether it really turns out to be practical remains to be seen."