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 2, 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 2, 2014).

Share This



More Computers & Math News

Thursday, October 2, 2014

Featured Research

from universities, journals, and other organizations


Featured Videos

from AP, Reuters, AFP, and other news services

Mozilla Bets On Software To Sell Its Chromecast Competitor

Mozilla Bets On Software To Sell Its Chromecast Competitor

Newsy (Oct. 1, 2014) Mozilla's Matchstick streaming device is entering a crowded market. The company is banking on open-source software to rise above the competition. Video provided by Newsy
Powered by NewsLook.com
App Teaches Kindergarteners to Code

App Teaches Kindergarteners to Code

AP (Oct. 1, 2014) They can't all read yet, but soon kindergarteners may be able to create basic computer code. Researchers in Massachusetts developed an app that teaches young kids a simple computer programming language. (Oct. 1) Video provided by AP
Powered by NewsLook.com
Microsoft Goes For Familiarity Over Novelty In Windows 10

Microsoft Goes For Familiarity Over Novelty In Windows 10

Newsy (Sep. 30, 2014) At a special event in San Francisco, Microsoft introduced its latest operating system, Windows 10, which combines key features from earlier versions. Video provided by Newsy
Powered by NewsLook.com
French Apple Fans Discover the Apple Watch

French Apple Fans Discover the Apple Watch

AFP (Sep. 30, 2014) Apple fans in France discover the latest toy, the Apple Watch. The watch comes in two sizes and an array of interchangeable, fashionable wrist straps. Duration: 00:42 Video provided by AFP
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