DNA Computing

Leonard Adleman sends his regrets. In an e-mail FAQ he uses to fend off journalists seeking interviews, the University of Southern California computer scientist and world-famous cryptographer who invented the field of DNA computing confesses that “DNA computers are unlikely to become stand-alone competitors for electronic computers.” He continues, somewhat apologetically: “We simply cannot, at this time, control molecules with the deftness that electrical engineers and physicists control electrons.”

It was in 1994 that Adleman first used DNA, the molecule that our genes are made of, to solve a simple version of the “traveling salesman” problem. In this classic conundrum, the task is to find the most efficient path through several cities-given enough cities, the problem can challenge even a supercomputer. Adleman demonstrated that the billions of molecules in a drop of DNA contained raw computational power that might-just might-overwhelm silicon. But since then, scientists have run into tough practical and theoretical barriers. As Adleman and others in the field have come to realize, there may never be a computer made from DNA that directly rivals today’s silicon-based microelectronics.

But that doesn’t mean they’ve given up. Far from it. Although computer scientists haven’t found a clear path from the test tube to the desktop, what they have found amazes and inspires them. Digital memory in the form of DNA and proteins. Exquisitely efficient editing machines that navigate through the cell, cutting and pasting molecular data into the stuff of life. What’s more, nature packs all this molecular hi-fi equipment into a bacterium not much bigger than a single transistor. Viewed through the eyes of computer scientists, evolution has produced the smallest, most efficient computers in the world-and the beige-box set is hooked.

As Adleman now sees it, DNA computing is a field that’s less about beating silicon than about surprising new combinations of biology and computer science that are pushing the limits in both fields-sometimes in unexpected directions. Scientists are still working hard on ways to tap the awesome number-crunching abilities of DNA for specialized types of applications, such as code breaking. But beyond that, the innate intelligence built into DNA molecules could help fabricate tiny, complex structures-in essence using computer logic not to crunch numbers but to build things.

Among the most promising of these new approaches are smart “DNA tiles” invented by Erik Winfree, a 30-year-old computer scientist at California Institute of Technology (see “100 Young Innovators,” TR November/December 1999). Winfree’s brainstorm is to create nanoscopic building blocks out of DNA that not only can store data but are designed-Winfree likes to say “programmed”-to carry out mathematical operations by fitting together in specific ways. Normally, DNA exists as two intertwined strands of the chemical letters A, G, C and T-the familiar double helix. But Winfree’s DNA tiles are made by knotting together three or more of these strands, forming “tiles” about 15 nanometers (billionths of a meter) on their longest side. Taking advantage of DNA’s ability to selectively recognize other strands of DNA, Winfree has “coded” the edges of these tiles so that they come together in just the right way to form tiny built-to-order structures.

In fact, programming DNA in this way could give chemists the kind of deft control “that may allow them to build more complex structures than any considered so far,” says Paul Rothemund, a doctoral student in Adleman’s USC lab.

DNA Dominoes

The idea of smart DNA tiles got its start five years ago at Caltech’s Red Door cafe, when Winfree and Rothemund met to discuss Adleman’s first DNA computing paper. The publication had set imaginations blazing throughout the world and across scientific disciplines. Were there other ways to compute with DNA? Could it beat silicon? Rothemund brought along a stack of papers showing “all the weirdest things that had been done with DNA.” One of these was by Nadrian Seeman, a chemist at New York University who had created cubes, rings, octahedrons and other unlikely shapes from the DNA double helix. Winfree, who was working on a PhD related to artificial learning in robots, immediately saw a way that Seeman’s strange versions of DNA could be used to compute.

Winfree’s intellectual breakthrough was inspired by the theory of Wang tiles-a bit of recondite mathematics related to the patterns that can be created using squares with numbered sides. Like dominoes, the numbers on each Wang tile determine which other tiles it is allowed to touch. By carefully establishing these “matching rules,” complex and interesting patterns can emerge as more tiles are added. But it’s more than just a game of mathematical dominoes. Because Wang tiles carry both data (the numbers) and simple rules for combining it, mathematicians in the 1960s proved that the tiles could be used to add or multiply numbers. In fact, they showed that with the right set of these hypothetical constructs you could, in theory, do anything an electronic computer can-from playing chess to counting sheep. Winfree’s big idea was a simple synthesis: use Seeman’s DNA molecules as tiny real-life Wang tiles.

Applied to DNA computing, the strategy could sidestep one of the fundamental problems that has bedeviled the field from the beginning-too much lab work. While DNA computing is good at producing a vast number of answers quickly, things slow down when it comes to picking the right answers out of the mix. Take the traveling salesman problem originally solved by Adleman, in which the object is to find the most efficient route through seven cities connected by 14 one-way flights. Adleman created strands of DNA to represent each flight, then combined them in a test tube to generate every possible route.

Although the DNA in one-fiftieth of a teaspoon produced 100 trillion answers in less than one second, most of those answers were repeats-and most of them were incorrect. So Adleman’s next task was to discard the wrong answers, something that could be done in a jiffy on a PC, but in Adleman’s case required several dozen manual laboratory procedures. And that’s where the trouble lies with most DNA computing schemes-each “operation” on the data means another time-consuming lab step.

The DNA tiles could solve that problem. Unlike the DNA used by Adleman in his original experiments that combined randomly, Winfree’s tiles follow simple rules to get the correct result. “Ideally, you just put [the tiles] in the test tube and whammo!, you’ve got a right answer,” says John Reif, a Duke University computer scientist.

Working with Winfree and Thom LaBean, a biochemist at Duke, Reif hopes to put the idea into practice by creating a simple molecular abacus out of DNA tiles. The goal is to add up binary numbers from zero to eight. With genetic letters standing in for 0s and 1s, the team has designed sets of tiles, each of which represents a possible column in an addition. Rules for combining columns correctly are coded into loose strands of DNA protruding from the sides of the tiles.

If all goes well, the experiment will generate several trillion multi-tile structures each of which has carried out an orderly addition of three binary bits. The scientists then will read off the results using standard methods for decoding DNA. The experiment underlines the potential power of DNA computers-massive parallelism and speed. Reif estimates that a single test tube of DNA tiles could perform about 10 trillion additions per second-about a million times faster than an electronic computer.

Nanotech C++

The enormous raw power of dna computing keeps the field moving in spite of all the daunting technical obstacles. Yet even if those obstacles ultimately prove insurmountable, Winfree’s work could mean a breakthrough in the construction of ultrasmall devices. Indeed, Winfree himself thinks DNA tiles’ most exciting application is as intelligent building blocks that put themselves together piece by piece on the nanometer scale-assembling into large and complex structures.

Collaborating with Rothemund and Adleman at USC, Winfree aims to fabricate a two-dimensional shape known as the Sierpinski triangle. Named after the Polish mathematician who discovered it in 1915, the triangle is a complex and beautiful fractal produced by repeating a simple geometric rule. The team plans to construct a real-world version of the triangle in a test tube using only seven different DNA tiles. Winfree has designed each tile type to carry out a simple program-to add itself to the growing shape or not, depending on the molecular cues provided by the triangle’s outer edge.

In the hands of nanofabrication experts like NYU’s Seeman, the DNA tiles could lead to easier methods to make exotic molecular structures-doing for nanotech what CAD and pre-fab building materials have done for the construction industry. “Greater control leads to things that you almost can’t imagine,” says Seeman. “Our expectation is that this approach can be applied to making designer materials and interesting patterns much more economically.”

Seeman’s lab, for instance, is already trying to attach nanoparticles of gold to DNA tiles in order to prototype tiny electrical circuits. These DNA “assemblies” would be about 10 times smaller than the tiniest features etched in silicon chips. However, Rothemund notes that there are limits to the patterns “computable” with DNA tiles. “We can’t make anything we want,” says Rothemund. “But the simple assemblies we’ve made so far show how well the basic operations work.”

They also show how much scientists still have to learn. Winfree compares his efforts so far to one-line programs written in biochemical Basic. What he’d really like to be doing is programming biochemical reactions in C++. He expects this more advanced language will evolve as researchers master new operations, such as selectively removing tiles from an assembly. Winfree speculates that one day it may be possible to bring this growing repertoire of programmable components together to build synthetic systems-call them “nanorobots” if you wish-capable of independently carrying out useful tasks. “The really interesting direction DNA computing is taking us is to see just how far we can learn to program biochemical reactions,” says Winfree.

That may sound like futuristic hype, but researchers are already beginning to figure out ways to do it. At Lucent Technologies’ Bell Labs, physicist Bernie Yurke, for one, is working with DNA in the hopes of assembling ultrasmall molecular motors. Yurke imagines that some day it might be possible to build a DNA motor that could walk across Winfree’s DNA tiling constructs, making chemical changes at specific points. “You could lay down an arbitrarily complex pattern,” Yurke says, which might then be transferred to a silicon substrate to fabricate nanometer-scale circuits and transistors. “My hope is that in the future complicated electronic structures like computers will be made this way.”

Electronic computers assembled using DNA that computes? It may sound like an unlikely twist in the evolution of DNA computing, but it’s one that Adleman believes is entirely in keeping with the field he helped launch. “Like quantum computing, DNA computing is very futuristic, and both make the point that computation doesn’t have to take place in the box that sits on our desks,” says Adleman, this time in a telephone interview. “Even if they don’t become a viable means of computing in the future-and I don’t know if they will-we may learn what the real computer of the future should look like.”

Computing (and Constructing) With DNA Organization Key Researchers Focus Bell Labs Bernie Yurke, Allan Mills Fabricating DNA motors for assembling electronic components Duke University/Caltech John Reif, Thomas LaBean, Erik Winfree (Caltech) Working on massively parallel addition using DNA tiles New York University Nadrian Seeman Assembling complex nanostructures out of DNA Princeton University Laura Landweber, Richard Lipton RNA-based computer used to solve chess puzzle known as the “knight problem” University of Southern California Leonard Adleman Automating a self-contained lab system for DNA computing; proved, in theory, that DNA can crack DES data encryption standard University of Wisconsin Robert M. Corn, Lloyd M. Smith, Anne E. Condon, Max G. Lagally Adapting DNA-chip technology to do DNA computation on a solid surface