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 solved a chess problem using a different sort of biological computer: beakers full of organic glop. The feat, the most difficult problem ever solved by molecular computing, may point the way to powerful techniques for solving other mathematical puzzles.
Most computers manipulate information in the form of bits, 1s and 0s, which are stored as high and low voltages or as north- or south-pointing magnetic fields in your PC. But they may also take more exotic forms, such as molecules of DNA and its cousin RNA. 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.) 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 necessary, she had a flask full of strands corresponding to every valid solution to the knights problem.
"It is the world champion so far," says Leonard Adleman of the University of Southern California in Los Angeles, who built the first DNA computer in 1994. To develop practical nucleic-acid computers, scientists will have to clear some major hurdles, 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," he says. "We know they can do lots--let's build cool things!"