LEONARD ADLEMAN’s computer is a bit, um, peculiar. There are none of the
usual silicon circuits or magnetic memory devices, no monitor, no keyboard. In
their place are test tubes—rows and rows of test tubes, some empty,
others
filled with DNA, the molecule of life. And hovering overhead are several dozen
robot arms, which periodically reach down to add something to a test tube or
combine the contents of two of them. To the uninitiated—which is just
about everybody—it’s hard to believe that such a mess of glassware,
tubing
and chemicals might someday outperform silicon supercomputers. But for a small
cadre of computer scientists that is the dream.
At present, the bizarre machine exists only on paper. But it is no pipe
dream. A year and a half ago, Adleman, who is a computer scientist at the
University of Southern California, described how he solved a mathematical
puzzle
called a Hamiltonian path problem with a test tube of DNA. It wasn’t a difficult
problem—a 14-year-old with a pencil and paper could crack it in a few
minutes, and a personal computer with the right software could do it in a
microsecond—but it generated sparks.
Test-tube calculations
Advertisement
“It got computer scientists thinking about another model of computation,”
says Peter Kaplan, an experimental physicist at the NEC Research Institute in
Princeton, New Jersey, who replicated Adleman’s test-tube calculation. Over the
past 20 years, molecular biologists have developed a host of powerful
methods to
create and manipulate strands of DNA: cutting them, copying them, joining them
end to end, zipping and unzipping pairs of strands, separating out strands with
a particular molecular sequence, and more. For researchers such as Kaplan, the
question of what might emerge from the marriage of molecular biology and
computer science was an irresistible intellectual challenge.
The possibility of a big payoff only adds to the appeal. In theory, one
should be able to perform trillions of computations simultaneously in a single
test tube of DNA, or to store in one small jar millions of times as much
information as is possible in today’s largest computer memories.
Sceptics abounded, of course. Some pointed out that to solve a truly large
mathematical problem with the sort of computer that Adleman described
would take
oceans of DNA. Others called attention to the large—and very
expensive—amount of enzymes that would be needed for the solution of all
but the simplest problems. Still others argued that the natural messiness of
DNA’s chemical reactions could doom computers that use it to unacceptably high
error rates. In short, there might be fundamental, unavoidable reasons why DNA
computers could never work.
Today, however, those initial worries have faded. At the Second Annual
Meeting on DNA-Based Computing, held last month at Princeton University,
researchers described a number of ways to reduce error rates, for instance. And
Adleman’s group reported that in principle it is possible to design a DNA
computer that needs less than a gram of DNA and uses almost no enzymes. Adleman
argues that today, at least in theory, there doesn’t appear to be anything to
hold DNA computers back. “All of this is encouraging,” he says.
So the focus has now shifted to practical issues. For Richard Lipton, a
computer scientist at Princeton and one of the leaders of the nascent field of
DNA computing, the big questions now are, “Can you really build these things?
And, assuming you can build them, can you do anything interesting with them?”
What looks doable on paper may fail in practice. And even if Adleman’s
test-tube
and robot-arm computer, or someone else’s design, can be made to run, they may
never be able to handle important problems as quickly and cheaply as their
silicon rivals.
Perfect partners
If these computers can be made to work, their power will flow from DNA’s
intrinsic properties, and particularly its defining feature: two long strands
that latch onto one another when brought close together. Each strand is
assembled from four molecules called “bases”, usually denoted by A, C, G and T.
The bases A and T are chemically attracted to one another, as are C and G.
So if
one DNA strand consists of ACGG, then its complementary strand, TGCC, will bind
to it. Conversely, two strands that are not complementary—say, ACGG and
ATAG—will not bind.
Molecular biologists can engineer the conditions in a solution of DNA to
encourage complementary strands to join, or to persuade joined strands to part
company. Furthermore, they can synthesise strands of DNA with any desired
sequence of bases, and read the sequence of bases in a strand of DNA.
Scientists have long known that DNA is, in essence, a natural computer
carrying a tremendous amount of information. But it was Adleman who first came
up with a way to harness that natural computing ability. In his seminal paper in
Science (vol 266, p 1021) he showed how to find a particular route
through several points on a graph—the Hamiltonian path problem. He
created
a set of DNA molecules corresponding to the points and the paths, then tipped
them into a test tube, where they linked up to create a larger DNA molecule
which represented the required route (See `Pathways to success’). It was unlike
anything that had ever been done with silicon computers.
DNA goes digital
Since then, researchers have devised a number of schemes to compute
with DNA.
Many even encode information in a digital format, similar to that used by their
electronic rivals, by treating DNA strands as strings of 0s and 1s. To
represent
the binary number 110100, for instance, you would link six strands of DNA
end to
end. The first 1 might be denoted by, say, the sequence of bases AACTG, the
second 1 by GGGTA, and so on. You cannot simply use the same sequence for every
1 in the binary number and another for every 0 because the DNA computer
needs to
be able to keep track of the order of the digits.
Shortly after Adleman’s original article appeared, Lipton showed that such
digital encoding could solve the well-known satisfaction, or SAT, problem of
computer science. If x and y are binary variables which can take the
values 0 or
1, a simple SAT problem would be to find all values for x and y that make the
logical statement (x=1 OR y=0) AND (x=0 OR y=1) true. In this case, x=1, y=1
would be a solution. The first clause, (x=1 OR y=0), is true because x has the
value 1. The second clause, (x=0 OR y=1), is true because y has the value
1. The
AND between the clauses indicates that both must be true, so, for
instance, x=0,
y=1 is not a solution because the first clause is not true.
A conventional silicon computer tackles a SAT problem by checking every
possible solution in turn. This is fine for problems with only a few variables
and clauses. But with dozens of variables and clauses the problem rapidly
becomes intractable, and even a high-speed electronic computer can take
weeks or
years combing through all the possibilities. On the other hand, a DNA computer
could attack the problem in a totally different way. Lipton showed that one
could create strands of DNA corresponding to all possible solutions—in a
big problem there might be trillions or more—and then search through them
all in parallel.
The heart of Lipton’s method is a process he calls extraction. When a
problem
has only two variables, x and y, the possible solutions are represented by the
numbers 00, 01, 10, and 11—where, for instance, 01 represents x=0,
y=1. An
extraction step could remove from the test tube all DNA corresponding to
strings
with, say, a 1 in the second position. Such an extraction would pull out the
strands encoding 01 and 11, leaving behind strands for 00 and 10.
To solve the first clause of the above SAT problem, one would first extract
all x=1 strands (10 and 11), then extract all y=0 strands (10 and 00), and mix
them in a new test tube—the OR corresponds to adding possibilities
together. From this batch of DNA one would solve the second clause by
extracting
all x=0 strands (00), and y=1 strands (11). These represent the answers to the
problem.
To perform an extraction in practice, Lipton proposed using probes made of
complementary DNA. If, for example, the sequence GGGTA corresponded to a 1 in
the second position, Lipton would make its complementary sequence CCCAT and
attach copies of it to magnetic particles. When these probes were poured into
the test tube, they would latch onto the DNA strands representing binary
strings
with a 1 in the second position. Then, with a magnet, Lipton would extract the
magnetic particles—together with the probes and long DNA strands. In
another test tube he would peel off the probes to leave the required DNA
strands.
Solving SAT problems and related calculations may be where DNA computers will
score over conventional computers. Compared to a silicon machine, where each
step in a calculation takes a fraction of a microsecond, extraction would be
very slow, taking perhaps minutes or hours. But a DNA computer could make
up for
this by performing vast numbers of operations at once. For every extra variable
in a SAT problem, the number of possible solutions doubles—and so
does the
computational time on a silicon computer. In a DNA computer, however, one more
variable would double the number of DNA strands needed for the calculation, but
the computational time would increase little.
Sticky digits
Some silicon computers, of course, have multiple processors which allow them
to perform many operations at once, but the largest can do only hundreds or
thousands of calculations at once. DNA computers should be able to perform
billions of times as many. Similarly, since a single test tube can hold
quadrillions of DNA strands, each encoding a string of hundreds or thousands of
0s and 1s, it may be possible to create DNA memories with capacities far
exceeding anything available today.
Using a technique based around extraction, Lipton and two of his students,
Dan Boneh and Christopher Dunworth, showed that it was possible—in
theory,
at least—to crack the data encryption standard (DES), the code
invented by
IBM for the US government, and now widely used in business. The key is a string
of 56 digits, which can be discovered only by searching through 2+56 different
sequences. This was precisely Lipton’s angle of attack. But his theoretical
method is more of a benchmark than a threat to national security: cracking the
code is already possible for someone willing to part with many millions of
dollars for a massively parallel computer.
Recently, Adleman and his team have found a more powerful technique for
making DNA compute. In it, Adleman starts with a large number of identical
strands of DNA, each of which is thousands of bases long. By itself, one of
these “memory strands” represents a long string of 0s. To put a 1 in particular
positions, Adleman uses “stickers”—short strands of DNA that are
complementary to the memory strands in those positions and so naturally stick
there (see Diagram below).
Adleman’s sticker method can match Lipton’s technique, and do much more. In
particular, Adleman can modify the computer’s memory during the course of a
calculation. Where Lipton’s strands are unalterable, Adleman can change his
memory strands in the middle of a series of calculations by adding stickers to
every strand in the test tube at the same place on each strand. This gives
him a
capability similar to that of silicon computers, allowing him to update his
calculations. The sticker computer also avoids the need for enzymes since none
of the calculation steps involves making copies of the strands, cutting the
strands, or linking two strands end to end.
Other researchers looking for ways to compute with DNA have gone in
different
directions. At the University of Wisconsin, for instance, Anne Condon and
colleagues propose attaching strands of DNA to a surface and manipulating them
there instead of letting them float free in a liquid. The idea is to avoid
losing DNA molecules during the extraction steps—a likely problem for
Lipton’s and Adleman’s designs. On the other hand, without being able to
extract
strands of DNA, the Wisconsin team has to rely on a more limited set of
computing operations.
At Caltech, Erik Winfree has abandoned DNA strands altogether in favour of
two-dimensional “bricks” of DNA, in which several strands of DNA are
combined to
create structures with four corners. Winfree, a student of Adleman’s, designed
the bricks so they would fit together much as the DNA strands did in Adleman’s
original work, except that the self-assembly would be in two dimensions instead
of one. The bricks assemble themselves in an inverted triangle —one
in the
first row, two in the second, three in the third, and so on. The answer would be
read off from the sequence of the last row of bricks after the triangle is
complete. Winfree is also working in three dimensions to try and assemble
pyramids.
It’s possible to envisage such a variety of DNA computers because no one yet
knows which type, if any, will work. “There are no ground rules,” Lipton says.
There is, however, one thing that everyone agrees on. Building a useful DNA
computer, not just a toy like Adleman’s original model, won’t be easy.
At the Princeton meeting, Nadrian Seeman of New York University described
some of the frustrations awaiting would-be DNA computer engineers. Seeman has
spent more than a decade assembling DNA into various structures, including
knots
and cubes, and knows better than most the pitfalls of dealing with DNA. If the
concentration of DNA in a test tube is too high or too low, Seeman warned,
or if
the temperature or acidity of the solution is wrong, reactions that have worked
well before may flop. Although in theory the bases A and T latch onto each
other, as do C and G, Seeman said that in practice any base can pair up
with any
other base, even itself, if conditions are not carefully controlled. Likewise,
paired strands of DNA do not always stay paired.
Kaplan has focused on another sort of difficulty likely to dog DNA
computers:
problems with the polymerase chain reaction (PCR), which lets researchers run
off millions of copies of a single DNA strand. Because answers to problems are
likely to be represented by only one or a few strands of DNA, researchers will
need some way to isolate these strands. “You must have an amplifier if you’re
going to have a DNA computer,” Kaplan says, “and PCR is the obvious choice for
an amplifier.”
Spurious results
However, problems with PCR are likely to arise when two or more different,
but similar, molecules remain at the end of the computation. If two
molecules—A and B—have similar sequences of bases, Kaplan
says, “one
strand of A could interact with one strand of B” to create spurious results. To
avoid this, Kaplan recommends designing the DNA strands used in calculations so
that no two are very similar. He also advocates running the PCR at low
amplification, because with fewer strands of A and B in the test tube, there is
less of a chance that they will meet and interact.
Lipton and Boneh warn that extraction could also generate errors. At best,
they say, only about 99 per cent of the molecules that should be extracted will
actually be removed in any given step. Losing 1 per cent of the strands
may seem
a small loss, but in a large DNA calculation with a thousand or more steps
there
would be little chance that the strand representing the solution would be left
at the end. To get round this, Lipton and Boneh suggest using PCR every few
steps to double the number of strands left in the test tube.
The most intriguing option for combating errors is also the most
speculative.
Some computer scientists have suggested designing DNA computers that exploit
evolution. A calculation would begin with a number of potential solutions to
some large problem, but, unlike most of the designs under discussion now, it
would not contain all potential solutions. Perhaps the number of potential
solutions is too large even for a DNA computer, or perhaps the problem is so
vaguely defined that it is not possible to list all potential solutions. Either
way, at each step in its calculation, the DNA computer would throw out, say, 90
per cent of the potential solutions and keep only the best 10 per
cent—”best” according to some criteria that the experimenter would decide
upon. From these 10 per cent the computer would produce a new generation of
solutions. The computer would do this over and over again, at each step
evolving
a set of potential solutions better than the last, until it produced a
satisfactory answer. Again, it would be up to the experimenter to define
“sپڲٴǰ”.
One advantage of such an approach, Adleman notes, is that the inevitable
errors in working with DNA would not be so threatening. Since the computer
itself makes “mistakes” in order to evolve its solutions, any additional
mistakes would make little difference.
What’s one plus one?
In the long run, the future of DNA computers may well depend on such
imaginative schemes. As Adleman says, with a note of irony: “All we have to do
is outperform the miracle of our time, the electronic computer.” It’s unlikely
that DNA computers will triumph by trying to beat electronic computers at their
own game. Instead, they are likely to make their mark only by finding
something—such as evolutionary computations—that they can call
their
own.
For the foreseeable future, the work on DNA computers is likely to be mostly
theoretical. Experimental studies will probably be limited to testing the
individual techniques that a complete machine might rely upon. The only
functioning DNA computers built are likely to be toys, such as the “two-bit
adder” described at the Princeton conference. It can add 1 and 1 and get
2. This
may not seem like much, but since in binary terms this sum reads 01+01=10, the
feat demanded a “carry” operation, which wasn’t easy to perform with numbers
represented by strands of DNA. And while DNA computers may have tremendous
potential, the difficulty they have in adding 1 and 1 is a reminder of just how
far they have to go.
* * *
Pathways to success
DNA COMPUTING got its start with the test tube solution of a simple problem:
find a route between seven cities along one-way and two-way roads. The trip
should start at city 0 and end at city 6. With a little trial and error, it is
easy to identify the route as 0→1→2→3→4→5→6.
To solve this with DNA in a test tube, Leonard Adleman of the University of
Southern California made strands of DNA, each one 20 bases long, and each
corresponding to a city or one of the allowable paths between cities. Adleman
designed the strands so that they would link up in ways that mirrored the
possible paths between the cities. For example, the strand representing
the path
from 5 to 2 latches onto the back half of the strand for city 5 and the front
half of the strand for city 2, linking those two strands.
When the strands were mixed in a test tube, they linked up in a variety of
ways, including such obviously wrong answers as a route that shuttles back and
forth between 2 and 3. Adleman began isolating the correct strand by using the
polymerase chain reaction (PCR) to amplify only those strands that started at
city 0 and ended at city 6. From this batch of DNA, he isolated strands that
were 140 bases long, and so corresponded to passing through exactly seven
cities. From these, he pulled out all strands that contained the sequence for
city 1; from this batch he pulled out strands containing city 2, and so on
through 3, 4 and 5. The only strands in the final batch contained all the
sequences in the correct order. The computation took about seven days in the
lab.
