Further DevelopmentThe Maximum Clique Problem
In 1997, a team of researchers from the NEC Research Institute, finally showed some new experimental results for solving NP-complete problems using molecular computing. Unlike the vast majority of papers written since Adleman’s first crude experiment, this article was not purely theoretical, as it described an actual experiment where researchers solved the maximum clique problem given a six vertex graph. The NEC team demonstrated a new technique used in the construction of the initial dataset which was considerable improvement over Adleman's. Instead of constructing each possible node and node-to-node connection individually as Adleman did, the researchers only made one DNA strands for each node, then employed a method (exploiting the simple network structure of cliques) which would automatically generate all possible paths between the nodes using a method called “thermal cycling.” However, removing illegal choices (because not all nodes in the graph are interconnected) still involved manual splicing. Once the data set was created, finding the maximum clique simply required using get electrophoresis to find the longest clique. However, because the number of "unconnections" between nodes grew exponentially just like the number of connections did, using manual removal of illegal configurations made this algorithm impractical on a larger scale as well, even if we ignored the many errors inherent in DNA processing.
RNA Solves the "Knights Problem"
As scientists around the world continued searching for more algorithms to classic problems for DNA, a team of scientists from Princeton demonstrated a way of using RNA as a molecule for computation in an experiment which solved the “Knights Problem” (how to place a number of knights on a chessboard so that none of them are attacking each other) on a 3x3 board. Building on the NEC team’s method of automatically building the dataset, the researchers created 18 different strands of DNA, one to represent each board positions with and without a knight. (9 squares x 2 possible choices/square = 18 different combinations). Using these 18 combinations, the researchers created an RNA library containing the 512 (2^9) board configurations. The researchers then described the problem as a SAT problem by assigning each square a variable and setting them up in a series of logical expressions; this can be done for any “chess” problem. The next step, where the incorrect strands are removed is where this experiment shines. Whereas previous experiments required all kinds of manual cutting, splicing, mixing, and complex screening to recover the correct answers in various test tubes, RNA could be easily digested using an enzyme called RNase H. The researchers could simply digest incorrect RNA strands inside the test tube using this enzyme. By using a series of branching, digesting, and then recombining, the researchers could “execute” the entire Boolean statement, resulting in the possible board configurations. In a random sample of 43 results, there was only one error which was attributed to RNA mutation. The researchers concluded that their method of “in place” RNA digestion was quite robust and could be applied to problems involving up to 2^50 RNA molecules.
The trend in DNA computing was naturally toward more automation and more generalization. In 2000, an interesting concept was introduced: utilizing the biological structure of DNA to increase automation. Previous experiments required large amounts of “old-fashioned, shake-the-test-tube lab work for each step in the calculation” (Cho). The new method takes advantage of DNA’s property of twisting itself into knots, hence the term "hairpin". Instead of manually cutting apart strands using various enzymes, or even using enzymes to digest RNA to generate the all the possibilities, this team designed strands that would automatically “fold over” when lowered below a specific temperature. This allowed larger datasets because of the reduced manual labor, but it also greatly increased erroneous results and required searching over many redundant solutions because of the repeated complementary sequences required for the folding to be possible. Major researchers in the area have expressed interest in this technique, but caution that they must “reduce the large proportion of errors” (Landweber) for this method to be viable.
previous page next page