USC News

Menu Search

COMPUTING WITH DNA

Writing mathematics in the language of life.

Computer scientists are always looking for ways to make computers
faster and smaller. Now, Leonard M. Adleman of the School of
Engineering has demonstrated that it is possible to carry out
computations at the molecular level.

In an experiment reported in the Nov. 11 issue of the journal Science,
Adleman solved a simple example of a well-known computational problem
by encoding mathematical structures in molecules of DNA and carrying
out computational steps in a test tube using standard techniques from
molecular biology.

“It is premature to judge the long-term implications of this approach
to computation,” said Adleman, who holds the Henry Salvatori Chair in
Computer Science. “However, molecular computation has certain
intriguing properties that warrant further investigation.

“For example, while current supercomputers can execute about a trillion
operations per second, molecular computers conceivably could execute
more than a thousand trillion operations per second. Further, molecular
computers might be as much as a billion times more energy efficient
than current electronic computers. Also, storing information in DNA
requires about 1 trillionth the space required by existing storage
media such as videotape.”

The “directed Hamiltonian path problem” that Adleman addressed involves
finding a special path through a network of points. Consider, for
example, this set of cities: Atlanta, Baltimore, Chicago and Detroit.
Assume that nonstop plane flights are scheduled only from Atlanta to
Chicago, Chicago to Detroit, Chicago to Baltimore and Baltimore to
Detroit. The directed Hamiltonian path problem would be: Could a
traveler book exactly three flights in a sequence – starting in Atlanta
and ending in Detroit – that would take him to each of the four cities?

It’s easy to see the answer is yes. Fly from Atlanta to Chicago, from
Chicago to Baltimore, then from Baltimore to Detroit.

But when the number of cities and flights grows even moderately larger,
the number of possible itineraries becomes astronomical. Even the
best-known algorithms running on the fastest supercomputers will fail
to find a solution. Moreover, mathematical analysis has shown that the
directed Hamiltonian path problem is one of a class of problems for
which a truly efficient algorithm will probably never be found.

Adleman’s DNA-encoded molecular computation of the solution proceeded
as follows.

For each of the four cities, a “DNA name” written in the four-letter
alphabet of DNA – A, T, G and C – was chosen at random. The letters
stand for the substances adenine, thymine, guanine and cytosine, which
form the rungs joining the double-spiral structure of DNA and carry
genetic information. For example:

(In the actual experiment. Adleman used DNA names 20 letters long
rather than six, and seven cities rather than four.)

Nobel laureates James D. Watson and Francis H.C. Crick showed that
every strand of DNA has a “complementary sequence” that sticks to it
(this is what gives DNA its double-spiral structure). In the
complementary sequence, each A is replaced by a T, each T by an A, each
C by a G and each G by a C.

Hence, each of the cities also had a “complementary DNA name”:

For each flight, Adleman then created a “DNA flight number” by taking
the three letters at the end of the DNA name for the departure city and
attaching the three letters at the beginning of the DNA name for the
destination. Thus:

Genetic engineering technology has made it routine to synthesize DNA
component strings like these with any desired sequence. In Adleman’s
experiment, 30 trillion molecules of each city’s complementary DNA name
and each DNA flight number were synthesized and added to a test tube.

Watson-Crick complementarity made the complementary DNA names act as
“splints” to bind DNA flight numbers together. For example:

After a short reaction time, the test tube contained trillions of long
DNA molecules consisting of DNA flight numbers splinted together by
complementary DNA names.

Molecules for all possible combinations of flights formed. Given the
sheer number of reacting molecules, probability makes it virtually
certain that, by pure chance, a molecule will form that corresponds to
the flight combination we are looking for – Atlanta to Chicago, Chicago
to Baltimore, Baltimore to Detroit.

The molecule encoding this solution is distinguishable from the others
because of its length (in our example, it is four DNA city names long),
its beginning (the DNA name for Atlanta), its end (the DNA name for
Detroit) and the fact that it contains the DNA names for both remaining
cities (Baltimore and Chicago).

Because of these properties, Adleman was able to use the tools of
molecular biology, including polymerase chain reaction and affinity
separation, to isolate the DNA molecule coding the solution to the
problem from all of the others that formed in the test tube.

In the experiment reported in Science, Adleman solved a small problem
with just seven cities. Clearly, however, the methods described can be
scaled up to handle much larger Hamiltonian path problems of the same
kind. The solution to such problems has a number of real-world
applications, including the design of telephone networks, scheduling of
work tasks and artificial-intelligence work.

In his Science paper, Adleman said, “the potential of molecular
computation is impressive. What is not clear is whether such massive
numbers of inexpensive operations can be productively used to solve
real computational problems. One major advantage of electronic
computers is the variety of operations they provide and the flexibility
with which these operations can be applied.

“Nonetheless, for certain intrinsically complex problems – such as the
directed Hamiltonian path problem, where existing electronic computers
are very inefficient and where massively parallel searches can be
organized to take advantage of the operations that molecular biology
currently provides – it is conceivable that molecular computation might
compete with electronic computation in the near term.”

Adleman is best known for his work on computer security – the “A” in
the widely used RSA (Rivest-Shamir-Adleman) coding system, which was
developed at the Massachusetts Institute of Technology. And 11 years
ago last week, on Nov. 11, 1983, one of Adleman’s students, Fred Cohen,
demonstrated a new kind of computer program designed to reproduce
itself surreptitiously. Adleman coined for it the now familiar term
“computer virus.”

Adleman said a key inspiration for the computational molecular biology
experiment was a 1959 talk by Richard Feynman, in which the legendary
physicist discussed the possibility of creating sub-microscopic
machines, including computers.

The experiment was performed at the USC-associated Institute for
Molecular Medicine and Technology and was supported by a National
Science Foundation grant and a Zumberge Research Grant.

[Photo:] Leonard M. Adleman in a chemistry lab. The computer scientist
learned the techniques of molecular biology in order to perform the
experiments reported in last week’s issue of Science.

COMPUTING WITH DNA

Top stories on USC News