The results are published in today's edition of the journal Science.

The new experiment was carried out by USC computer science professor Leonard Adleman, who made headlines in 1994 by demonstrating that DNA -- the spiraling molecule that holds life's genetic code -- could be used to carry out computations.

The idea was to use a strand of DNA to represent a math or logic problem, then generate trillions of other unique DNA strands, each representing one possible solution. Exploiting the way DNA strands bind to each other, the computer can weed out invalid solutions until it is left with only the strand that solves the problem exactly.

Although they are still nowhere near primetime, "DNA computers do have several attractive features," said Adleman, distinguished professor of computer science and biological sciences and holder of the Henry Salvatori Chair in Computer Science in the USC School of Engineering. "They are massively parallel, compute with extremely high energy-efficiency and store enormous quantities of information."

Adleman's first experiment proved that computing with molecules was possible. But the problem solved -- to find the shortest route among seven cities -- could easily have been solved by a person with a pencil and paper.

Adleman's new experiment solves a problem requiring the evaluation of more than a million possible solutions -- too complex for anyone to solve without the aid of a computer.

It required a set of 20 values that satisfy a complex tangle of relationships. Adleman's chief scientist, Nickolas Chelyapov, offered this illustration: Imagine that a fussy customer walks onto a million-car auto square and gives the dealer a complicated list of criteria for the car he wants.

"First," he says, "I want it to be either a Cadillac or a convertible or red." Second, "if it is a Cadillac, then it has to have four seats or a locking gas cap." Third, "If it is a convertible, it should not be a Cadillac or it should have two seats."

The customer rattles off a list of 24 such conditions, and the salesman has to find the one car in stock that meets all the requirements. (Adleman and his team chose a problem they knew had exactly one solution.) The salesman will have to run through the customer's entire list for each of the million cars in turn -- a hopeless task unless he can move and think at superhuman speed.

This serial method is the way a digital electronic computer solves such a problem.

In contrast, a DNA computer operates in parallel -- with countless molecules shimmying around together at once. This is equivalent to each car having a valet inside who will listen to the customer read his list over a PA system and will drive off the lot the moment his car fails one of the conditions. By the time the customer finishes his list, his dream car will be waiting alone on the lot.

While the time needed to solve problems of this class (called "NP-complete problems") increases exponentially (2, 4, 8, 16 ... ) for serial computers, it increases only linearly (2, 4, 6, 8 ... ) for parallel computers.

In principle, then, the DNA computer should outstrip the electronic computer on savagely complex combinatorial problems -- breaking encryption schemes, for example. Unfortunately, Adleman said, the DNA computer currently is too error-prone to achieve its great potential.

"In the past century we've become really good at controlling electrons," he said. "It would take a breakthrough in the technology of working with large biomolecules like DNA for molecular computers to beat their electronic counterparts."

Still, even if no one finds a way to beat electronic computers on very complex problems, he said, DNA computers might find applications in other areas.

"It's possible that we could use DNA computers to control chemical and biological systems in a way that's analogous to the way we use electronic computers to control electrical and mechanical systems," he said.

Adelman suggested, for example, that such systems might someday be engineered into living cells, allowing them to run precise digital programs that would interact with their natural biochemical processes.

"We've shown by these computations that biological molecules can be used for distinctly non-biological purposes," he said. "They are miraculous little machines. They store energy and information, they cut, paste and copy.

"They were built by 3 billion years of evolution, and we're just beginning to tap their potential to serve non-biological purposes. Nature has given us an incredible toolbox, and we're starting to explore what we might build."

Other co-authors of the Science paper were Ravinderjit S. Braich, a postdoctoral student; Cliff Johnson, a neurobiology Ph.D. graduate student and Paul W.K. Rothemund, who received his Ph.D. and is now at Caltech.

The research was supported by grants from the Defense Advanced Research Projects Administration (DARPA), the Office of Naval Research (ONR), the Jet Propulsion Laboratory, NASA Ames Research Center and the National Science Foundation.


[Contact: Matthew Blakeslee, Bob Calverley]

15-Mar-2002