DNA
solves big problem
By
Kimberly Patch,
Technology Research NewsDNA computers can theoretically solve problems that have a lot of variables because many DNA molecules can work on different parts of a problem at once. There is still a long way to go, however, before this ability can be leveraged to actually solve very large problems.
Researchers from the University of Southern California and the California Institute of Technology have taken a substantial step toward that end by solving a 20-variable problem using a DNA computer.
The problem was NP-complete, meaning solving it required an exhaustive search of its 1,048,576 possibilities. To date, it is the largest problem solved without electronic computers, according to Nickolas Chelyapov, a research scientist at the University of Southern California. "We did something that would require a human several years to do with pen and paper," he said. Previously researchers used RNA, which is chemically similar to DNA, to solve a nine-variable problem, which has 512 possibilities.
Chelyapov likened the 20-variable problem to that of a car dealer with a one million-car auto lot trying to satisfy a customer who has a complicated list of 24 intertwining criteria for the car he wants. Two of the criteria could be, for instance, that the car must be either a Cadillac or red, and if it is a Cadillac it must have four seats or a gas cap that locks.
To solve the 20-variable problem, the researchers carried out logical computations using short, artificial strands of DNA that had information embedded in the order of their bases. DNA is made up of adenine, cytosine, guanine and thymine bases strung together on a sugar-phosphate backbone. Single strands of DNA zip together to form a double helix when the bases on the two strands match in a way that allows adenine to pair with thymine, and cytosine to pair with guanine.
The variables were represented by 15-base DNA sequences. The problem involved finding a unique answer to a mathematical formula that used 20 of the sequences, or variables. The variables were strung together in sets of three, or triads. The answer contained 24 combinations of triads. The researchers made "library" strands of DNA that could combine with all the variables.
Once the pieces were in place, the "DNA computer had to take a look at all the answers and find one satisfying the formula," said Chelyapov. To do this, the researchers immobilized DNA strands representing the formula in gel-filled glass modules. They then coaxed the complementary library strands to move through the modules by electrophoresis, which uses electricity to move charged particles across a field. DNA molecules naturally carry a charge.
The library strands that had sequences complementary to the immobile ones joined with the residents and stayed in the module. Library strands without complementary sequences passed through. The researchers released the captured strands -- preliminary answers -- using a higher temperature electrophoresis.
The researchers were able to exhaust the possibilities and find an answer using 24 of these capture-release steps. "At each of the 24 steps [the] library was depleted of wrong answers, leaving only those involved in the formula. [The] final module contains just one answer... the correct unique assignment satisfying the formula," said Chelyapov.
One of the challenges in using DNA to solve a 20-variable problem was synthesizing the relatively long artificial DNA strands it required, said Chelyapov. Although biological DNA can be very long -- our 23 pairs of chromosomes together contain about 3.3 billion base pairs -- it is difficult to artificially produce even much shorter strands. The strands the researchers used were about 150 bases long.
The gel-filled modules made for a computer design that is dry and could be automated, and because the method does not damage the DNA, the strands can be reused, according to Chelyapov.
Although DNA computers are not likely to to compete with electronic computers for most uses, their ability to check many possible solutions at once could eventually allow them to solve NP-complete problems faster than for electronic computers, according to Chelyapov. A DNA computer that could solve a 50- to 60-variable problem would in theory solve it faster than today's electronic computers, he said.
In addition, because DNA computers are very energy-efficient and take up very little room, they may someday find use in environments where extreme energy-efficiency or small size are required, Chelyapov said. "Molecular computers can be considered in a broader context. They may provide a much-needed means for controlling chemical/biological systems in the same way that electronic computers have provided a means for controlling electrical/mechanical systems," he said.
It will be 10 years before DNA computers find practical uses, however, said Chelyapov.
The work is outstanding, according to Nadrian Seeman, a chemistry professor at New York University. "They have used a relatively quick electrophoretic method to go through a huge problem," he said.
The research shows that a DNA computer can solve a large problem "through a clever version of a sticker method. It works in part because the [formula DNA strand] is attached to a solid support, so that there is no competition from other molecules in solution," Seeman said.
Chelyapov's research colleagues were Ravinderjit S. Braich, Cliff Johnson and Leonard Adleman of the University of Southern California, and Paul W. K. Rothemund of the California Institute of Technology. They published the research in the March 14, 2002 issue of the journal Science.
The research was funded by the National Aeronautics and Space Administration (NASA), Defense Advanced Research Projects Agency (DARPA), the Office of Naval Research (ONR) and the National Science Foundation (NSF).
Timeline: 10 years
Funding: Government
TRN Categories: Biology; Biological, Chemical, DNA and Molecular Computing
Story Type: News
Related Elements: Technical paper, "Solution of a 20-Variable 3-SAT Problem on DNA Computer," Science, March 14, 2002.
Advertisements:
March 20/27, 2002
Page One
Monkey think, cursor do
DNA solves big problem
Carving beams shrink circuits
Lasers snatch free-floating DNA
Etching could boost disk capacity
News:
Research News Roundup
Research Watch blog
Features:
View from the High Ground Q&A
How It Works
RSS Feeds:
News
| Blog
| Books 
Ad links:
Buy an ad link
| Advertisements:
|
 |
Ad links: Clear History
Buy an ad link
|
TRN
Newswire and Headline Feeds for Web sites
|
© Copyright Technology Research News, LLC 2000-2006. All rights reserved.
