|
January 25, 2008
Nano Computers, Part 2
What do tiles have to do with molecules?
By Scott C. Anderson
So what about the molecular computers I promised in Part 1 of this article?
For that we take a break from tiles, math, computers and crystals to talk a little about DNA. Don’t leave yet! You’ve made it this far, and we’re only going to use DNA as a building block, not for any tricky genetic stuff. In the same year that Dan Shechtman found his ten-fold crystal, Nadrian Seeman was playing with bits of DNA as if they were tinker toys.
There are four informational “bases” in DNA: adenine (A), thymine (T), cytosine (C) and guanine (G). The rules are wonderfully simple: A is attracted to T and C is attracted to G, so a single strand of DNA that has the sequence CAT would be attracted (complementary) to the sequence GTA. Dr. Seeman's building blocks were rods composed of double strands of DNA with frayed “tails”. These untidy tails consist of short single-stranded pieces overhanging the ends. He called them "sticky" because they would hook up to complementary strands as if they were hot-glued.
ATTAAATTTGGGCCC GTAAAATTTGGGCCC
|||||||||||| ||||||||||||
TTTAAACCCGGGCAT TTTAAACCCGGGACG
The two strands above will attract each other and connect up because the CAT end of one strand is complementary to the GTA end of the other. Seeman found that if he put together twelve of these DNA rods with the correct sticky ends, he could create a wire-frame cube of DNA (a cube has twelve edges, count ‘em). Actually, the cubes assembled themselves. This was an astonishing feat of nanotechnology. He went on to create tetrahedrons, dodecahedrons and dozens of other shapes. DNA, it turns out, is a remarkable tinker toy – not many other materials can assemble themselves just by being tossed together.
However, that's not all we can expect from DNA. Everyone knows that DNA provides the blueprint for a living creature, but we don't usually think of it as a computer. Yet, it's not too much of a stretch to view the DNA sequence as a program, with proteins being the data output. Maybe DNA has more computing power than we realize.
Another Interesting Development
In 1984, Leonard Adleman took a fresh look at DNA and envisioned a parallel computer where the output was the DNA itself. Adleman, an expert in computer science as well as molecular biology, wanted to see if he could use DNA to compute something called the Hamiltonian path. This problem is typically posed as a type of traveling salesman problem, where there are a bunch of cities, but not all of them are connected by roads or airlines. The salesman has to figure out how to use the existing connections to visit each city just once. The algorithm is easy to solve for just a few cities, but it quickly gets nasty as more cities are added. Even supercomputers can choke when the number of cities exceeds a few hundred. Adleman took brute force to a new level: he used billions of DNA molecules to solve the problem in parallel.
Remember we use four letters to represent the DNA bases: A, T, G and C. If you used a sequence of three letters to signify a location (like a 3-letter airport code) you could represent sixty-four (the four bases raised to the third power, 4x4x4=64) different locations. With four letters, you could code for 256 locations, and so on. Adleman actually used over a dozen letters, but for purposes of illustration, we'll use three.
He devised a scheme that represented flights between cities by a three-letter code for the origination and another three-letter code for the destination. Here are some possible locations using this scheme:
TAC: Tacoma
ATA: Atlanta
CAC: Calcutta
Then a flight from Tacoma to Atlanta would start with TAC and end with ATA. Actually, to make the end of one flight connect with the next, we would end with Atlanta’s complement (TAT), which would then automatically link up with ATA. To represent the plane trip between them, you could create a DNA string like this:
TAC-TAT Tacoma to the complement of Atlanta
So a trip from Tacoma to Calcutta through Atlanta would look like this:
TAC-TAT
|||
ATA-GTG
|||
CAC
Adleman used a machine called a DNA sequencer to create strands of DNA corresponding to each possible flight, and made millions of copies of each. Then he put them all in a test tube with some proteins called ligase to help them link up. By their natural attraction, each leg of the trip connected to every other possible leg, generating billions of potential flight-plans – most of them wrong. However, with billions of flight-plans to choose from, one of them was bound to be a winner.
To find that optimal path, Adleman first found all the strands that that had the correct starting and ending location. By creating so-called primers that matched those locations, he was able to amplify just the specific strands of DNA that started and stopped at the right place.
Adleman ran these amplified candidates through a gel. This is a standard technique to tease apart DNA of different sizes. The gel slows down the larger molecules, so you can pluck out just the sizes you want. Adleman selected all the DNA strands that had the right number of locations and discarded the rest. He now had DNA of the proper length and with the proper starting and ending locations.
Finally, he used something called affinity purification to pull out all the DNA sequences that didn't contain every location. This allowed him to pull out those DNA strings that didn't have Atlanta, for instance. Finally, he was left with DNA with the right length, starting location, ending location and every location in between. These were the winners – the DNA strands describing a complete path between all the cities with no repetition.
Clearly, doing all this chemistry is a tedious way to compute an algorithm, but as a proof of concept, it was pretty revolutionary. DNA manages to pack the data tightly, up to 100,000 times denser than today's RAM, and its ability to perform parallel computations is, well, unparalleled.
You can imagine some simple tweaks to make this experiment solve more complicated problems. You could make the length of each strand correspond to the cost of each flight. For instance assume these are the relevant prices for our set of cities:
Tacoma (TAC) to Atlanta ~ $200
Atlanta (ATA) to Calcutta ~ $900
Then a flight from Tacoma to Atlanta might look like this:
TAC-TTT-TTT-TAT
|||
ATA
Here the two T triplets in the middle represent the (really cheap) $200 fare.
So our trip from Tacoma to Calcutta through Atlanta would look like this:
TAC-TTT-TTT-TAT
|||
ATA-TTT-TTT-TTT-TTT-TTT-TTT--TTT-TTT-TTT-GTG
|||
CAC
Now the shortest strand of DNA that still hits every city once will also be the one to save the most money.
Still, this is not an efficient way to do general-purpose calculations. That turns out to be a real head-scratcher. But when Erik Winfree found out about Adleman's and Seeman's DNA research, he had an epiphany: what if Adleman's DNA computer and Seeman's DNA building blocks could be combined into a more general-purpose computer? Winfree knew about Wang tiles, and saw a way to build them using Seeman's molecular tinker toys. Instead of colors that need to match up, why not tiny postage-stamps of DNA with sticky edges?
Working with Seeman, that’s exactly what he did. To make a DNA tile, he would need something flatter and stiffer than a single helical strand. But he knew that in nature, DNA “crosses over”. This is how our mother’s and father’s genes get mixed up to make our own unique blend of features and quirks. Where the DNA crosses, it gets reinforced and gains rigidity. Like lashing sticks together to make a raft, Winfree was able to create very tiny rectangles of DNA from a collection of strands. And, of course, he made them with sticky edges that were particular about what they would stick to. They were Wang tiles, alright, but they were pretty special: they didn’t need a tiler to grout them into place. Instead, tossed together into the right molecular soup, these DNA tiles would line up with the complementary edges of other tiles and lay out their own surface.
Amazingly, Winfree had created tiny bits of DNA that could self-assemble into a Turing machine. With these magical DNA seeds, he could actually grow a computer.
And now for a short break
That’s the end of part 2. In the next installment, you'll see how to put these remarkable molecular computers together into an injectable drug-delivery machine I call the nanodoctor.
Copyright © 2000-2014 by Scott Anderson
For reprint rights, email the author:
Scott_Anderson@ScienceForPeople.com
Here are some other suggested readings about self-assembling molecules:
|
