solves big problem
Technology Research News
DNA 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
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
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,
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
TRN Categories: Biology; Biological, Chemical, DNA and
Story Type: News
Related Elements: Technical paper, "Solution of a 20-Variable
3-SAT Problem on DNA Computer," Science, March 14, 2002.
Monkey think, cursor do
DNA solves big problem
Carving beams shrink
Lasers snatch free-floating
Etching could boost
Research News Roundup
Research Watch blog
View from the High Ground Q&A
How It Works
News | Blog
Buy an ad link