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.
No comments:
Post a Comment