Featured Research

from universities, journals, and other organizations

Using "Nature's Toolbox," A DNA Computer Solves A Complex Problem

Date:
March 21, 2002
Source:
NASA/Jet Propulsion Laboratory
Summary:
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.

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.


Story Source:

The above story is based on materials provided by NASA/Jet Propulsion Laboratory. Note: Materials may be edited for content and length.


Cite This Page:

NASA/Jet Propulsion Laboratory. "Using "Nature's Toolbox," A DNA Computer Solves A Complex Problem." ScienceDaily. ScienceDaily, 21 March 2002. <www.sciencedaily.com/releases/2002/03/020315072402.htm>.
NASA/Jet Propulsion Laboratory. (2002, March 21). Using "Nature's Toolbox," A DNA Computer Solves A Complex Problem. ScienceDaily. Retrieved October 21, 2014 from www.sciencedaily.com/releases/2002/03/020315072402.htm
NASA/Jet Propulsion Laboratory. "Using "Nature's Toolbox," A DNA Computer Solves A Complex Problem." ScienceDaily. www.sciencedaily.com/releases/2002/03/020315072402.htm (accessed October 21, 2014).

Share This



More Computers & Math News

Tuesday, October 21, 2014

Featured Research

from universities, journals, and other organizations


Featured Videos

from AP, Reuters, AFP, and other news services

Thanks, Marty McFly! Hoverboards Could Be Coming In 2015

Thanks, Marty McFly! Hoverboards Could Be Coming In 2015

Newsy (Oct. 21, 2014) If you've ever watched "Back to the Future Part II" and wanted to get your hands on a hoverboard, well, you might soon be in luck. Video provided by Newsy
Powered by NewsLook.com
Robots to Fly Planes Where Humans Can't

Robots to Fly Planes Where Humans Can't

Reuters - Innovations Video Online (Oct. 21, 2014) Researchers in South Korea are developing a robotic pilot that could potentially replace humans in the cockpit. Unlike drones and autopilot programs which are configured for specific aircraft, the robots' humanoid design will allow it to fly any type of plane with no additional sensors. Ben Gruber reports. Video provided by Reuters
Powered by NewsLook.com
Japanese Scientists Unveil Floating 3D Projection

Japanese Scientists Unveil Floating 3D Projection

Reuters - Innovations Video Online (Oct. 20, 2014) Scientists in Tokyo have demonstrated what they say is the world's first 3D projection that floats in mid air. A laser that fires a pulse up to a thousand times a second superheats molecules in the air, creating a spark which can be guided to certain points in the air to shape what the human eye perceives as an image. Matthew Stock reports. Video provided by Reuters
Powered by NewsLook.com
Apple Enters Mobile Payment Business

Apple Enters Mobile Payment Business

AP (Oct. 20, 2014) Apple is making a strategic bet with the launch of Apple Pay, the mobile pay service aimed at turning your iPhone into your wallet. (Oct. 20) Video provided by AP
Powered by NewsLook.com

Search ScienceDaily

Number of stories in archives: 140,361

Find with keyword(s):
Enter a keyword or phrase to search ScienceDaily for related topics and research stories.

Save/Print:
Share:

Breaking News:

Strange & Offbeat Stories


Space & Time

Matter & Energy

Computers & Math

In Other News

... from NewsDaily.com

Science News

Health News

Environment News

Technology News



Save/Print:
Share:

Free Subscriptions


Get the latest science news with ScienceDaily's free email newsletters, updated daily and weekly. Or view hourly updated newsfeeds in your RSS reader:

Get Social & Mobile


Keep up to date with the latest news from ScienceDaily via social networks and mobile apps:

Have Feedback?


Tell us what you think of ScienceDaily -- we welcome both positive and negative comments. Have any problems using the site? Questions?
Mobile: iPhone Android Web
Follow: Facebook Twitter Google+
Subscribe: RSS Feeds Email Newsletters
Latest Headlines Health & Medicine Mind & Brain Space & Time Matter & Energy Computers & Math Plants & Animals Earth & Climate Fossils & Ruins