Received: by alpheratz.cpm.aca.mmu.ac.uk id DAA11526 (8.6.9/5.3[ref pg@gmsl.co.uk] for cpm.aca.mmu.ac.uk from fmb-majordomo@mmu.ac.uk); Fri, 15 Mar 2002 03:13:37 GMT Subject: Fwd: Using 'Nature's Toolbox,' A DNA Computer Solves A Complex Problem Date: Thu, 14 Mar 2002 22:07:44 -0500 x-sender: wsmith1@camail.harvard.edu x-mailer: Claris Emailer 2.0v3, Claritas Est Veritas From: "Wade T.Smith" <wade_smith@harvard.edu> To: "Memetics Discussion List" <memetics@mmu.ac.uk>, "SKEPTIC-L" <skeptic@listproc.hcf.jhu.edu> Content-Type: text/plain; charset="US-ASCII" Message-Id: <20020315030741.CAFF31FD49@camail.harvard.edu> Sender: fmb-majordomo@mmu.ac.uk Precedence: bulk Reply-To: memetics@mmu.ac.uk
---------------- Begin Forwarded Message ----------------
MEDIA RELATIONS OFFICE
JET PROPULSION LABORATORY
CALIFORNIA INSTITUTE OF TECHNOLOGY
NATIONAL AERONAUTICS AND SPACE ADMINISTRATION
PASADENA, CALIF. 91109 TELEPHONE (818) 354-5011
http://www.jpl.nasa.gov
Contact: JPL/Carolina Martinez (818) 354-9382
USC/Matthew Blakeslee (213) 740-9335
FOR IMMEDIATE RELEASE March 14, 2002
USING 'NATURE'S TOOLBOX,' A DNA COMPUTER SOLVES A COMPLEX PROBLEM
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 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 one 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 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
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, 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.
#####
----------------- End Forwarded Message -----------------
===============================================================
This was distributed via the memetics list associated with the
Journal of Memetics - Evolutionary Models of Information Transmission
For information about the journal and the list (e.g. unsubscribing)
see: http://www.cpm.mmu.ac.uk/jom-emit
This archive was generated by hypermail 2b29 : Fri Mar 15 2002 - 03:25:55 GMT