A DNA-based computer has solved a logic problem that no person could complete by hand,
setting a new milestone for this infant technology that could someday surpass the electronic digital
computer in certain areas.
The results are published in the online version of the journal Science on March 14 and will also
run in the print edition.
The new experiment was carried out by USC computer science professor Dr. 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 research was partially supported by grants from NASA's Jet Propulsion Laboratory,
Pasadena, Calif., and NASA's Ames Research Center, Moffett Field, Calif., as part of the Computing,
Information and Communication Technology Program.
The idea was to use a strand of DNA to represent a math or logic problem, and 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
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 one million possible solutions -- too complex for anyone to solve without the aid of a
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 said, "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
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,
Adleman 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 post-doctoral 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 also supported by grants from the Defense Advanced
Research Projects Administration, the Office of Naval Research and the National Science Foundation.
JPL is a division of the California Institute of Technology in Pasadena.