Silicon upstarts aside, the best chess computers are biological--the brain of grand master Gary Kasparov, for example. Now a team of scientists at Princeton University has used a different sort of biological computer--beakers full of organic glop--to solve a chess problem. The feat, the most difficult problem ever solved by molecular computing, marks the first time RNA has been used as a molecule for computation and may point the way to powerful techniques for solving other mathematical puzzles.
Everyday computers manipulate information in the form of bits: 1s and 0s. The bits may be stored as high and low voltages (as in a computer's processor) or as north- or south-pointing magnetic fields (as in a hard drive). But they may also take more exotic forms. For example, the chemical bases that make up molecules of DNA and its cousin RNA are ideal for storing digital information. In 1994, computer scientist Leonard Adleman of the University of Southern California in Los Angeles showed that jugs of DNA could be turned into computers (Science, 11 November 1994, p. 1021). Since then, scientists have been using DNA to solve small mathematical problems such as adding two numbers together. Now, in the 15 February Proceedings of the National Academy of Sciences, evolutionary biologist Laura Landweber and her colleagues at Princeton University describe how they used RNA to solve the "knights problem" on a 3 x 3 chessboard: finding all the ways to place a collection of knight pieces (which move in an L-shaped pattern) so that no knight can attack another.
To solve this problem with a regular computer, you could start by assigning one bit to each of the nine squares on the board. Each bit represents whether a knight is sitting in that position (1) or if that position is empty (0). Then you could simply crank through all the possible combinations of 1s and 0s for the nine positions and eliminate the ones where knights are able to attack each other.
Landweber took a similar "brute force" approach. First, she synthesized 18 different stretches of DNA, each consisting of 15 base pairs. Each stretch represented a bit for a particular space--a "knight" or a "blank" for each of the nine positions on the board. (For instance, CTCTTACTCAATTCT meant that the upper left-hand corner is blank, while ACCTTACTTTCCATA meant there's a knight in the center square.) She then created a "library" of millions of DNA strands representing all possible configurations of the board--that is, every possible permutation of knights and blanks.
Landweber then methodically eliminated the permutations in which one knight could capture another. Using standard techniques, she copied the DNA into RNA, which can be readily cleaved by an enzyme called ribonuclease H. That set the stage for a molecular slice-and-dice fest that minced all the non-solution-bearing RNA strands out of the library.
The enzymatic algorithm was possible because the knights problem can be reduced to a set of logical statements. One statement might be: "Either the upper-left corner is blank, or the two squares that a knight threatens from that position must be blank." To satisfy that statement, Landweber split the library into two. Into one jug, she poured an enzyme that targeted the sequence that meant "there is a knight in the upper-left corner." To the other jug she added two enzymes that targeted the sequence that signaled the presence of a knight in the two threatened positions. After the broken fragments were all weeded out, neither jug contained an RNA strand that included sequences that had both a knight in the upper-left corner and a knight in one of the two squares threatened from that position.
Landweber then mixed the jugs together, converted the RNA back to DNA, amplified the DNA, and started all over again with another logical statement. After repeating the process for each logical statement that describes the knights process, she was left with a flask full of strands corresponding to every valid solution to the knights problem--plus a few rogues that escaped the cleaving enzymes by a fortuitous mutation. "We pulled out 42 correct solutions and one incorrect solution out of 43 clones that we tested," says Landweber.
"It is the world champion so far," says Adleman, who, along with other biochemists and computer scientists, is trying to make a molecular computer do a problem that a human can't do in a reasonable amount of time. "[Landweber] has got the inside track for trying to reach that milestone first."
To develop practical nucleic-acid computers, however, scientists will have to clear some major hurdles, such as figuring out how to correct errors and how to produce and handle large volumes of nucleic acid. Kasparov has no reason yet to feel threatened by beakers of glop, but Adleman is hopeful that nucleic-acid computers will be more than mere curiosities. "Here's nature's toolbox, a bunch of little tools that are dirt cheap; you can buy a DNA strand for 100 femtocents," he says. "Here's a great set of tools, we know they can do lots--let's build cool things!"
From
http://www.sciencemag.org/cgi/content/full/287/5456/1182
Volume 287, Number 5456, Issue of 18 Feb 2000, pp. 1182-1183.
Copyright © 2000 by The American Association for the Advancement
of Science.