Introduction

Top Abstract Introduction Materials and Methods Results and Discussion References

Adleman (1) introduced DNA-based computing as an approach to solving mathematical problems, which uses DNA as a data carrier and techniques of molecular biology to operate on DNA. Since then, there have been relatively few experimental demonstrations of DNA-based computations (2, 3), although the theoretical foundation is strong (4, 5). Here we introduce a method for the construction of binary nucleic acid libraries, and we introduce RNA as a molecule for computation to present a general approach for the solution of the famous satisfiability (SAT) problems of propositional logic.

Using a combination of a binary RNA library and ribonuclease (RNase) H digestion, we developed a destructive algorithm (6) that would hydrolyze RNA strands that did not fit the constraints of a chosen problem, instead of an algorithm that required efficient hybridization extraction (1, 2). The use of restriction endonucleases (3) would have also permitted a logical binary-style operation, as each restriction enzyme cleaves only in the presence of its recognition site, and cleaves the double-stranded DNA sufficiently to completion. However, by using RNase H in the context of different sets of oligonucleotides, one can go beyond the set of available restriction enzymes. Here, RNase H acts as a "universal restriction enzyme" because it allows selective marking of virtually any RNA strands for digestion in parallel, and use of a thermostable RNase H (7) ensures fidelity of hybridization between DNA and RNA strands, minimizing incorrect marking of noncognate strands.

	Materials and Methods

Top Abstract Introduction Materials and Methods Results and Discussion References

Chemical Synthesis of DNA "Half Libraries." The DNA library was prepared as two halves by using mix and split phosphoramidite chemistry with the sequence codes shown in Table 1. In brief, bit n set to 0 and spacer n were synthesized on one column, and bit n set to 1 and spacer n were synthesized on the other column. The columns were decrimped and the two resins poured together and mixed, and then half of this mixture (containing approximately equal proportions of 0's and 1's at bit position n) was returned to each column for synthesis of the next variable position, and the entire process was repeated (Fig. 1). Each of the four combinatorial synthesis products was purified by polyacrylamide gel electrophoresis on a 6% denaturing gel (Sequagel, National Diagnostics) and was recovered by a "crush and soak" procedure (500 mM ammonium acetate/1 mM EDTA/0.1% SDS) and ethanol precipitation (8). Annealing of the four half-sized strands in a 50-µl PCR reaction containing 1 µM of each of four halves (9) and primer overlap extension during five thermocycles (94°C for 30 sec, 45°C for 30 sec, and 72°C for 30 sec per cycle) generated the DNA library of full sized strands with a total of 1,024 (2¹⁰) unique strands. (Note that the 3 × 3 instance of this problem considers nine bits, or a total of 512 different chessboards. Bit 10 was unused in the actual selections.) The degeneracy of the DNA pool was verified by direct sequencing (10) using 5' end-radiolabeled primers TXR (Prefix; [CAT]₄CTCGAGAATT) and 32.41 (Suffix complement; [CTA]₄CGGGATCCTAATGACCAAGG) in cycle sequencing reactions (SequiTherm Excel, Epicentre Tech).

View larger version (22K): [in this window] [in a new window]   Fig. 1.   Modular construction of the combinatorial DNA library from two half-libraries. Linear mixing and splitting steps yield exponential increases in pool complexity. Each half is synthesized on two columns beginning with bit f or its reverse complement. Synthesis of one half continues through bit a and the prefix; the other half contains the reverse complement of bits f through j and the suffix. Because the halves are complementary at position f, primer extension of the two halves creates the full-length 10-bit library. Black and white boxes represent 1 and 0, respectively; shaded boxes represent prefix, suffix, and spacer sequences.

DNA Bit Oligonucleotides. The set of DNA bit oligonucleotides used both to operate on the RNA library and as the downstream primers in readout PCR were from Operon Technologies (Alameda, CA) and are shown in Table 2.

Implementing the RNA Algorithm. RNase H digestions destroyed the RNA strand of RNA·DNA hybrids marked by hybridization of the pool RNA to the complementary bit oligonucleotides shown in Table 2. One hundred-microliter RNase H reactions contained 20 µg of gel-purified RNA (250 pmol), 1 nmol of each bit oligonucleotide, 5 units of Hybridase Thermostable RNase H (Epicentre Tech), 50 mM Tris·HCl (pH 7.5), 100 mM NaCl, and 10 mM MgCl₂. After preincubation at 72°C for 3 min to denature strands, enzyme and MgCl₂ were added at 45°C. The reaction was held at 45°C for 60 min and then was stopped by addition of 10 mM EDTA. Spin column chromatography (CLONTECH Chroma Spin-200, DEPC-H₂O) was used to remove DNA bit oligonucleotides and short RNA digestion products. The eluted RNA was ethanol-precipitated, and remaining full-length (undigested) RNA was purified on a 5% denaturing polyacrylamide gel. Recovered RNA was reverse transcribed in 80 µl with 1.25 µM suffix complement (Superscript II, BRL). One-tenth of this reaction was amplified by PCR (200 µl, 1 µM primers T7TXR and 32.41, 2-5 cycles of 94°C for 30 sec, 60°C for 30 sec, and 72°C for 30 sec). After ethanol precipitation, the two halves of each pool were combined, and half of the DNA was transcribed in vitro for the next step in the algorithm.

Multiplex Colony PCR Readout. PCR products were directly cloned by using the TOPO-TA cloning kit (Invitrogen). Cells were grown on LB-agar plates containing 50 µg/ml ampicillin (8). Positive (white) colonies were randomly picked, were transferred to 50 µl of LB media containing 50 µg/ml ampicillin, and were grown for 4-6 hours at 37°C. Colony PCR (11) of 2 µl of media (95°C for 5 min, followed by 25 cycles of 95°C for 30 sec, 60°C for 30 sec, and 72°C for 30 sec with 0.2 µM primers TXR and 32.41) allowed rapid screening and recovery of individual DNA library strands. To readout the bit settings of cloned strands, 1 µl of a 1:100 dilution of the colony PCR product was first amplified by linear PCR (9) (10 µl, 0.2 µM primer T7TXR; 10 cycles as above) in the presence of prefix only to generate an excess of single-stranded DNA; then equimolar mixtures of 5' end-radiolabeled "0"- or "1"-complementary DNA oligonucleotides (1 nM each) were added to the same tube, and the reaction was continued for an additional five cycles. Reaction products were separated on a 6% denaturing polyacrylamide gel (Long Ranger gel solution, FMC Bioproducts). The dried gel was analyzed by autoradiography on a PhosphorImager (Molecular Dynamics).

Error Analysis. To determine potential sources of error, we measured the efficiency and recovery of each operation.

	Results and Discussion

Top Abstract Introduction Materials and Methods Results and Discussion References

The "Knight Problem." Chess problems create a class of SAT problems that are flexible in both scale and complexity. A "true" or "1" variable represents the presence of a knight at positions a-i whereas a "false" or "0" variable represents the absence of a knight at that position. This is a particular instance of a class of NP-complete SAT problems. For a 3 × 3 board    

Design and Synthesis of a 10-Bit RNA Library. A 10-bit pool size was chosen because this represents a pool of significant complexity, containing 1,024 different strands. Each strand of RNA follows the template below (4):

Each bit can be set to an "on" (= 1) or "off" (= 0) sequence. Using computer simulations, we incorporated three important criteria into the design of the combinatorial pool: (i) Each of the bit encodings must be fundamentally different. Hence, sequences were chosen to maximize the Hamming Distances between different library strands and between the different parts of individual strands (no more than five matches over a 20-nt window, both within and between all 2¹⁰ possible strands). Bit sequences were also selected to have an average melting temperature of 45°C. (ii) The strands were biased to avoid secondary structure so that each bit position would be equally accessible to the enzymes and oligonucleotides that operate on the pool molecules. This was accomplished by using a three-letter alphabet for the bits and spacers in the library, A, C, and U, eliminating the potential for both G-C pairs and G:U pairs (which form in RNA) as well  as G stacking. (iii) The strands were controlled to avoid hybridization to themselves or to any other library strands by more than seven consecutive base pairs (12) because such interactions would interfere with our ability to operate on the RNA strands by making these regions inaccessible to reagents.

Algorithm for Solving the Knight Problem Using the RNA Library. We executed the algorithm for solving a variant of the knight problem with our RNA combinatorial library as follows (Fig. 2): Initially we have a test-tube that encodes all 1,024 possible 10-bit strings. Each string has the general form x₁... x_n, where a variable x_i is either 1 or 0, representing a bit set to on or off. (In our experiment, x₁ = a, x₂ = b,... , x₉ = i.) Then we systematically perform the first operation to destroy strings that fail to satisfy the first clause ((h  f)  a) as follows: (i) One executes an OR clause by dividing the library into two "equal" collections. In one test-tube, we select those strands that contain a 1 at position a by annealing DNA bit oligonucleotide a₀ to the library, hence digesting those strands with position a set to 0 (thereby setting bit a to 1). Simultaneously, we destroy any 1's at those bit positions that must be set to 0 to fulfill the clause (bits f and h in this case). In the other test-tube, we anneal DNA bit oligonucleotide a₁ to perform the mirror operation setting bit position a to 0 (a). (ii) Undigested molecules are recovered and reverse transcribed. After not more than five PCR cycles, the contents of both tubes are mixed and amplified to high copy number during T7 RNA polymerization. The library is split again to execute the next OR clause, and this process is repeated until all clauses have been processed. The combinations of bit oligonucleotides in each step were as follows: a 1: a₀, f₁, h₁; 0: a₁; b 1: b₀, g₁, i₁; 0: b₁; c 1: c₀, d₁, h₁; 0: c₁; d 1: d₀, c₁, i₁; 0: d₁; f 1: f₀, a₁, g₁; 0: f₁.

View larger version (21K): [in this window] [in a new window]   Fig. 2.   Outline of the RNA algorithm. A value of 1 or 0 is assigned to a specific bit position by destroying all strands in the RNA library which do not have the value at this position (the step shown sets bits a, f, and h). The library is divided into two equal ensembles. In one test-tube, a specific bit position is set to 1 along with its accompanying constraints; in the other set, this bit is set to 0, using targeted digestion by RNase H. Continuing with this series of operations on the combined ensemble of strands leads to execution of the algorithm, which ends with readout of a randomly chosen subset of the surviving strands.

"Bit Shuffling." Recombination events are likely to occur during PCR amplification of heterogeneous target sequences (13), especially because the strands in our 10-bit library share several stretches of sequence identity constrained by the bit structure of the library. To measure this effect, the PCR products derived from two clones (wt-I 011 111 001 and wt-II 010 110 010, a, ... ,i) were combined and amplified for 25 cycles of PCR (0.2 µM primers TXR and 32.41; conditions as above). The resulting PCR products were cloned, and 20 clones were randomly chosen and analyzed by multiplex colony PCR readout at positions c, f, and h. Eight of twenty resulting clones (40%) were the product of bit shuffling. This indicates that bit shuffling poses a serious threat to successful execution of the algorithm; however, when only 15 instead of 25 PCR cycles were used, no bit shuffling was detected in 20 randomly chosen clones. This suggests that bit shuffling in our system is mostly due to a high proportion of incompletely extended strands annealing to heterologous target sequences, and it suggests that we can sufficiently reduce this problem by limiting the number of PCR cycles.

Methods of "Readout." Readout of a randomly sampled set of clones was accomplished by colony PCR (10) followed by multiplex linear PCR. This creates a "bar code" for each strand (Fig. 3). If one wanted to solve a stricter version of the knight problem, one could select the board containing the maximal number of knights by choosing sequences of unequal length for 1's and 0's and purifying either the longest or shortest strands (3), but the use of bit sequences of unequal length would preclude the quick and streamlined readout in Fig. 3 because it relies on equal length for 1's and 0's (Table 1) to generate a bar code pattern. Furthermore, unlike that of Ouyang et al. (3), our approach requires neither the isolation of plasmid DNA nor actual sequencing of any clones for readout.

View larger version (73K): [in this window] [in a new window]   Fig. 3.   Multiplex colony PCR readout. Colony PCR (10) allowed rapid screening and recovery of individual library strands. The boards represented by two clones are shown above their respective readouts on a 6% polyacrylamide gel. These clones represent the strings 010 011 010 and 001 011 000. Left lane, 10-bp ladder.

RNA Solutions. After subjecting the RNA library to the algorithm outlined above, 43 clones were randomly chosen and interpreted by readout PCR. Forty-two of these represented solutions to our version of the Knight problem (Fig. 4). Ten solutions occurred more than once, even though they were selected at random. However, the overall distribution of these 42 clones was not significantly different from a random sampling of all 94 possible solutions (Table 3), with a very modest preference for higher numbers of knights. We did not attempt to recover the other 64 solutions, as they are all variants of the classes of solutions shown in Fig. 4, and it would require a much larger sampling to ensure representation of each unique solution at least once. One clone (represented as 010 111 011) contained two illegal interactions, resulting from incorrect placement of one knight. Hence, of 127 knights on 43 boards, only one knight had an unacceptable placement. This was effectively a 97.7% success rate in finding correct solution strands, which is indeed satisfactory for choosing a clone that is likely to encode a solution.

View larger version (64K): [in this window] [in a new window]   Fig. 4.   Representations of the 31 unique boards analyzed by PCR readout. The last board contains one "illegal" white knight.