PRINCETON, N.J. Princeton University researchers claim to have reached a new level of complexity in DNA computing. The group has demonstrated an RNA-based computer capable of solving mathematical problems that were encoded as 10-bit strings.
Strands of RNA containing 1,024 base pairs were encoded with every possible solution to a specific chess problem. Ribonuclease digestion progressively narrowed down the possible solutions until only the 43 correct solutions plus one incorrect one remained.
"Molecules can store more information than silicon chips, and this was the largest problem ever solved by a molecular computer using either DNA or RNA. We also learned how far we can push this technology when we discovered why it made a single error," said professor Laura Landweber, the leading Princeton researcher on the project. Landweber's colleagues are professor Richard Lipton and post-doctorate candidates Dirk Faulhammer and Anthony Cukras.
In 1994, Leonard Adleman of the University of Southern California-Los Angeles conceived of harnessing DNA to solve tough computation problems. He demonstrated his concept on the classic seven-city traveling-salesman problem using the base-four encoding of DNA. After synthesizing trillions of DNA strands to stand for every possible solution, his test tube finally came to the correct conclusion after about a week.
Tough combinatorial problems like that chosen by Landweber's Princeton team present significant hurdles to any finite-size computer. The possible solutions to such problems expand so fast, Adleman reasoned, that even a few variables will result in a problem so complex that only approximate solutions can be found.
The Princeton research team's problem was toy-sized, having a mere 1,024 possible solutions, but the group claims the basic nature of the single error indicates that it can be scaled up to real-world-size problems. Apparently, the error came from a rare source that will not increase geometrically with the higher-dimensional solution spaces of real-world problems.
"We just had a bit of bad luck or more literally two bits, since it was two single-point errors in a row that foiled our algorithm," Landweber said. "Two errors in a row are exceedingly rare and shouldn't become a problem when we scale up."
The Princeton team substituted RNA for DNA to enable the use of a universal enzyme that targets any part of a molecule. DNA has only a limited set of restriction enzymes, so scientists may not be able to cut the molecule where they want. The group demonstrated that its streamlined approach using RNA could inherently scale up to real-world-size problems by virtue of the universal enzyme.
Using a combination of binary RNA libraries and ribonuclease digestion, the Princeton team created a destructive algorithm that acts as a "universal restriction enzyme" a kind of molecular scissors that can selectively cut out any specified strand for digestion (removal). The thermostable reaction proved impervious to single-bit errors, ensuring the fidelity of the hybridization.
Since the algorithm (by virtue of its universal restriction enzyme) operates in parallel on every molecule in the test tube, it can make trillions of parallel computations theoretically possible. In the Princeton test, for example, it took only a series of five steps to target all of the enzymes that slashed away those coded strands that represented the incorrect solutions.
The particular problem posed to the RNA computer was how many ways there are to place knights on a chess board so that none can take any other. A 3-by-3 chess board was chosen so that each of its nine squares could represent a bit in the RNA strand. A 10-bit library of RNA strands gave a 1-bit buffer, used to correct 1-bit errors chemically.
There were a total of 43 correct solutions among 512 total possibilities; the RNA computer found all 43 correct ones and one incorrect one.
For the future the Princeton team intends to go after problems that, while not yet approaching real-world proportions, scale beyond the toy category. "The class of general satisfiability, where we got this chess problem, is naturally extendible. We might go to larger boards or different variations on the chess problem," said Landweber.
Landweber's department, evolutionary biology, tracks the biological evolution of species, including that of biological computers. Her particular take has been to apply evolutionary biological principles to what she calls molecular evolution.
"I want to trace the evolution of the molecules themselves from their earliest emergence up to the complex organic molecules of today. In molecular evolution it was the correct solutions to biological computations that had a better chance at survival," said Landweber.
Her aim is to identify the component molecules, along with their mutual reactions and their interrelationships, that have evolved to create the biological computer called the human brain. Armed with the correct molecules and their known reactions, previously intractable problems could turn out to be child's play for trillions of parallel-processing molecular computers.