DNA logic gates. Fredkin gates are of fundamental importance in the design of computers because (I) they can function with extremely small amounts of energy (in principle, arbitrarily low energy), and (ii) arbitrary Boolean circuits can be assembled using Fredkin gates. We have shown how to encode information in DNA and use DNA amplification to implement Fredkin gates. We have shown successful readout, and we have demonstrated in the laboratory that the output of our Fredkin gate can then be used as legal input to a second Fredkin gate computation. We completed a laboratory demonstration of fabrication of DNA logic registers. Executed a reversible (Toffoli) universal Boolean logic operation using the ligase chain reaction. This is the first demonstration of a reversible gate via DNA computation, which may be very significant for low energy applications. Tested the efficiency of the reaction by end-labeling the 5' end oligo with 32-P, followed by analysis of the LCR products and detection.

Joshua P. Klien, Thomas H. Leete, and Harvey Rubin. A biomolecular implementation of logically reversible computation with minimal energy dissipation. Also in Peter J. Angeline, Zbyszek Michalewicz, Marc Schoenauer, Xin Yao, and Ali Zalzala, editors, 1999 Congress on Evolutionary Computation. IEEE Computer Society Press, New York, to appear, 1999. Also to appear in DIMACS Series in Discrete Mathematics and Theoretical Computer Science, ed. . L. Kari, (1999). Extended version of DNA4 and CEC99 papers. BioSystems, to appear.

Rubin, H., J. Klein, T. Leete, A biomolecular implementation of logically reversible computation with minimal energy dissipation, To appear in DIMACS Series in Discrete Mathematics and Theoretical Computer Science, ed. . L. Kari, (1999).

Note: We had previously used a horizontal chain reaction for DNA-Based addition that did not allow repetitions; see:

Guarnieri, F., and C. Bancroft. Use of a Horizontal Chain Reaction for DNA-Based Addition. DIMACS Series in Discrete Mathematics and Theoretical Computer Science. 4:105-111 (1999).

The Sticker Machine for DNA Computation. We also significantly improved the performance of the `sticker' machine for molecular computation by building the basis for a `solid state' device. Our previous research revealed the difficulties of having the information carrying DNA in aqueous solution -- in particular spillage and volume expansion. To overcome these problems, we have designed and implemented a `solid state' method in which DNA is confined to acrylamide gels throughout the computation. During the computation, DNA is passaged from location to location via electrophoresis.

Graphic URLs:

(http://www-scf.usc.edu/~pwkr/BMC/modules.gif, 206 KB) Stackable glass modules containing acrylamide gel (colored blue for visibility). The acrylamide has embedded DNA probes which are covalently bound to the acrylamide via acrydite chemistry. Each module is approximately 1cm long.

(http://www-scf.usc.edu/~pwkr/BMC/plungers.gif, 113 KB) Glass `plungers' containing buffer for electrophoresis. Two plungers shown `head to head'. Blue region shows acrylamide plugs. Vertical shafts are for attaching electrodes and releasing gas.

(http://www-scf.usc.edu/~pwkr/BMC/block.gif, 116 KB) `Solid state' apparatus consisting of two aluminum blocks with central bore into which glass modules and plungers are inserted. During electrophoresis, the left block is heated and the right block is cooled. DNA leaves modules in the left block to migrate toward and be captured in modules in the right block.

Sam Roweis, Erik Winfree, Richard Burgoyne, Nickolas V. Chelyapov, Myron F. Goodman, Paul W.K. Rothemund and Leonard M. Adleman, A Sticker-based Model for DNA Computation, Journal of Computational Biology, V. 5 N. 4, pp. 615-629, 1998.

(A new representation for encoding bits in DNA is presented and examined.)

Leonard M. Adleman, Paul W.K. Rothemund, Sam Roweis and Erik Winfree, On Applying Molecular Computation to the Data Encryption Standard, Journal of Computational Biology, V. 6. N. 1, pp. 53-63, 1999.

(An algorithm for breaking DES using the Stickers model is outlined. Size, space, and error rates of a practical machine designed to implement this algorithm are considered.)

Sam Roweis, Erik Winfree, Richard Burgoyne, Nickolas V. Chelyapov, Myron F. Goodman, Paul W.K. Rothemund and Leonard M. Adleman, A Sticker-based Model for DNA Computation, 26 pages, Journal of Computational Biology, V. 5 N. 4, pp. 615-629, 1998. (http://www-scf.usc.edu/~pwkr/stickers.ps.gz 284 KB ), (http://www-scf.usc.edu/~pwkr/stickers.ps, 1.2 MB), (http://www-scf.usc.edu/~pwkr/stickers.pdf, 694 KB) (A new representation for encoding bits in DNA is presented and examined.) The version available at the links above has a section concerning methods for decreasing separation error rates that is not included in the JCB article cited. Instead this material appears in:

Leonard M. Adleman, Paul W.K. Rothemund, Sam Roweis and Erik Winfree, On the Reduction of Errors in DNA Computation, Journal of Computational Biology V. 6 N. 1, pp. 65-75. On Applying Molecular Computation to the Data Encryption Standard, 21 pages. (http://www-scf.usc.edu/~pwkr/des.ps.gz, 90 KB ), (http://www-scf.usc.edu/~pwkr/des.ps, 211 KB), (http://www-scf.usc.edu/~pwkr/des.pdf, 206 KB) Journal of Computational Biology, V. 6. N. 1, pp. 53-63, 1999. (An algorithm for breaking DES using the Stickers model is outlined. Size, space, and error rates of a practical machine designed to implement this algorithm are considered.)

We executed surface based DNA computation operations, encoding bits by use of DNA hybridization chemistry. We have developed a prototype DNA computer (by solving a small example of the Satisfiability (SAT) problem) in which a set of DNA molecules encoding all candidate solutions to the computational problem of interest is manipulated while attached to a surface. Successive cycles of MARK (hybridization) and Destroy (exonuclease digestion) steps identify and eliminate members of the set which are not solutions to the problem, followed by the step of identification of the solution to the computational problem using PCR amplification of the remaining molecules and hybridization to an addressed array (READOUT). We demonstrated:

-DNA computer arithmetic and logic registers,

-MARK and UNMARK operations using DNA hybridization chemistry (. Preliminary results on multi-word MARK.),

-DESTROY operations using exonuclease degradation, for destroying unwanted strands on the surface, and use of restriction enzymes to cleave strands from the surface,

-APPEND (ligation) on multi-word strands.

These tests verified the feasibility of this method for surface based DNA computation. We also developed methods for constructing sets of short DNA strands satisfying certain combinatorial or free energy constraints, for use in DNA computing or as molecular bar codes in chemical libraries. We used single-word strands and a single-base per bit encoding strategy with a 4-base mismatch design. We automated the step of making DNA arrays for READOUT and have begun investigations to create arrays with gold films patterned on a silicon surface and also to create a patterned surface on silicon itself for a DNA array fabrication, as well as novel silicon modification chemistry for DNA attachment.

A Slide Show presentation of DNA computing on surfaces:

Wang, L., Q. Liu, A. Frutos, S. Gillmor, A. Thiel, T. Strother, A. Condon, R. Corn, M. Lagally, L. Smith, Surface-based DNA computing operations: DESTROY and READOUT, To appear in DIMACS Series in Discrete Mathematics and Theoretical Computer Science, ed. L. Kari, (1999).

Frutos, A.G; Smith, L.M. and Corn, R.M. "Enzymatic Ligation Reactions of DNA "Words" on Surfaces for DNA Computing" 1998, J. Am. Chem. Soc., 120, 10277-10282.

Q. Liu, A. G. Frutos, L. Wang, A. E. Condon, R. M. Corn, L. M. Smith, DNA Computing on Surfaces, 5th International Meeting on DNA Based Computers(DNA5), MIT, Cambridge, MA, (June, 1999). To appear in DIMACS Series in Discrete Mathematics and Theoretical Computer Science, ed. E. Winfree, (1999), submitted to Science, 1999.

Gillmor, S.D.; Liu, Q.; Thiel, A.J.; Condon, A.E.; Corn, R.M.; Smith, L.M. and Lagally, M.G. "Hydrophobic/Hydrophilic Patterned Surfaces to Create DNA Arrays" to be submitted (to Langmuir), 1999.

Liu, Q.; Wang, L. and Smith, L.M. "Identification of DNA Molecules on Surfaces by Array Hybridization for DNA Computing" (in preparation), 1999.

Strother, T.C.; Votruba, P.G.; Corn, R.M.; Hamers, R.J. and Smith, L.M. "Synthesis and Characterization of DNA-Modified Silicon(111) Surfaces" (in preparation), 1999.

Zhao, X.; Votruba, P.G.; Strother, T.C.; Ellison, M.D.; Smith, L.M. and Hamers, R.J. "Formation of Organic Films on Si(111) Surfaces via Photochemical Reaction" (in preparation), 1999.

Brockman, J.M.; Frutos, A.G. and Corn, R.M. "A Multi-Step Chemical Modification Procedure to Create DNA Arrays on Gold Surfaces for the Study of Protein-DNA Interactions with Surface Plasmon Resonance Imaging", (in preparation), 1999.

Frutos, A.G.; Weibel, S.G. and Corn, R.M. "Near Infrared Surface Plasmon Resonance Measurements of Ultrathin Films: Fourier Transform SPR Spectroscopy" (in preparation), 1999.

Developed and experimentally tested a RNA protocol for solving a SAT problem known as the "Knight Problem" on a 3 x 3 chess board using sequential RNase H digestions. Each configuration of knights on the chessboard was encoded on an RNA sequence. On each round we perform: selection, single bit operations, and destroying (using thermostable RNase H) RNA molecules which did not satisfy a criterion for this problem. The DNA oligonucleotides were removed by column chromatography, the eluates mixed and subjected to further rounds of selection and destruction. The remaining RNA pool was purified by PAGE after completion of the computation process. Isolated RNA was reverse transcribed, PCR amplified and cloned. The key advantage of this method is that it is scalable to well over 30 variables.

Most significantly, we have successfully refined the RNA ‘mark and destroy’ algorithm which we introduced last year, to solve a 9-bit instance of a Satisfiability (SAT) problem derived from Chess (a 3 x 3 version of the Knight problem). The method is general for any type of SAT problem. Using the enzyme Ribonuclease (RNase) H to specifically cleave targeted RNA strands, we demonstrated that this effectively allows creation of a universal RNA restriction endonuclease, which means that the method is inherently scalable. We have also carried out the design of a 25-bit RNA library with the specific aim of extending our experimental protocol to address larger, more challenging NP-complete problems.

Powerpoint Slideshow on RNA solutions to general SAT problems:

( paper describes RNA solutions to the Knight problem (placement of knights on a 3 x 3 board)

Faulhammer, D. , A. R. Cukras, R. J. Lipton, L. F. Landweber, When the Knight Falls: On Constructing an RNA Computer, 5th International Meeting on DNA Based Computers(DNA5), MIT, Cambridge, MA, (June, 1999).To appear in DIMACS Series in Discrete Mathematics and Theoretical Computer Science, ed. E. Winfree, (1999).

Landweber, L. F. , RNA Based Computing. In DNA Based Computers II, L. F. Landweber and E. B. Baum, eds. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, American Mathematical Society, 181-189, (1999).

Faulhammer, D., Lipton, R. J. and L. F. Landweber (in press) Counting DNA: Estimating the complexity of a test tube of DNA. In DNA Based Computers IV, L. Kari, ed. (199).

We developed experimental designs to decrease errors, including DNA word designs:

Designed and tested short DNA words that can be used to encode digital information and to enable DNA operations (for example, based on hybridization) to be executed robustly. We also tested a new RNA method for creating libraries of words and the construction of a 10-bit library by an innovative mix and split evolutionary method which optimized for word dissimilarity (e.g., Hamming distance). Our evolutionary method for creating libraries will enable us to design a 25-bit library, allowing scalability of the methods for RNA solutions to large SAT problems as reported above in 1.2B.

Streamlined Modular Construction of 10-, 25-, and N-Bit Combinatorial Libraries. We synthesized a DNA library encoding all strands of the ten-bit RNA library, as only two halves. The first half contained bits one through six, and the second half contained the complements of bits six through ten. To insert bits 11 through 25, we will synthesize three additional sub-libraries containing bits 10 - 15, the complements of bits 15 - 20, and bits 20 through 25, each in a single step. Note that this approach scales linearly to synthesize any n-bit library from n/5 or n/6 pieces by generating six or seven bits at a time (with one-position overlap). In order to construct each modular piece of the combinatorial library without synthesizing each strand individually, we devised a novel mix and split synthesis. Bit j set to 0 was synthesized on one column and bit j set to 1 was synthesized on another column. Both columns were then decrimped and their contents mixed. Then half of this pool was returned to each column and placed back on the DNA synthesizer. The partially synthesized molecules were further extended by synthesis of the spacer and the next bit set to 0 on one column, and the spacer and the next bit set to 1 on the other column, and the process repeated. In this way, linear mixing and splitting steps yield exponential increases in pool complexity. Primer overlap extension of the two halves created the full-length ten-bit library, since the pieces are complementary at bit position six. Direct DNA sequencing confirmed the expected degeneracy at each bit, and in vitro transcription of the DNA library yielded the RNA library. Similar annealing and extension of all five modular pieces will correspondingly generate the 25-bit library from these streamlined components.

Marathe, A., A. E. Condon, R. M. Corn , On Combinatorial DNA Word Design, 5th International Meeting on DNA Based Computers(DNA5), MIT, Cambridge, MA, (June, 1999).To appear in DIMACS Series in Discrete Mathematics and Theoretical Computer Science, ed. E. Winfree, (1999). submitted (to J. Comput. Biol.), 1999.

Analogs of natural evolution have been used in computation (Genetic Algorithms are examples) and in Molecular Biology (In Vitro Evolution is an example). There have been many calls in the literature to combine these two approaches to gain:

• Molecular computation robust against bio-laboratory errors
• A means to use few laboratory steps to improve upon billions of times more candidate solutions than is feasible with conventional computers.

We have carried out preliminary laboratory experiments demonstrating "selection according by fitness". This is the only example we know of physically separating a combinatorially encoded library of DNA strands according to global criteria.

Junghuei Chen, Eugene Antipov, Bertrand Lemieux, Walter Cedeno, and David Harlan Wood. DNA computing implementing genetic algorithms. In Laura Landweber, Erik Winfree, Richard Lipton, and Stephan Freeland, editors, Preliminary Proceedings DIMACS Workshop on Evolution as Computation, pages 39-49, DIMACS, Piscataway NJ, January . (1999).

Eugene Antipov. A Max 1s problem in DNA computing via genetic algorithms. In Wolfgang Banzhaf, A. E. Eiben, Max H. Garzon, Vasant Honavar, Mark Jakiela, and Robert E. Smith, editors, Late-Breaking Papers of the Genetic and Evolutionary Computation Conference, July 13-17, 1999, Orlando, Florida USA., San Francisco, 1999. Morgan Kaufman.

Chen, J., E. Antipov, B. Lemieux, W. Cedeno, D.H. Wood, In vitro Selection for a Max 1s DNA Genetic Algorithm, 5th International Meeting on DNA Based Computers(DNA5), MIT, Cambridge, MA, (June, 1999). To appear in DIMACS Series in Discrete Mathematics and Theoretical Computer Science, ed. E. Winfree, (1999). In Wolfgang Banzhaf, A. E. Eiben, Max H. Garzon, Vasant Honavar, Mark Jakiela, and Robert E. Smith, editors, GECCO-99: Proceedings of the Genetic and Evolutionary Computation Conference, July 13-17, 1999, Orlando, Florida USA., San Francisco, 1999. Morgan Kaufman.

graphics:

L. Kari, L. F. Landweber , Computational Power of Gene Rearrangement, 5th International Meeting on DNA Based Computers(DNA5), MIT, Cambridge, MA, (June, 1999).To appear in DIMACS Series in Discrete Mathematics and Theoretical Computer Science, ed. E. Winfree, (1999).

We plan to demonstrate that the Fredkin gates of our DNA implementation can be "wired together" to form elementary circuits such as one of AND, OR, NOT, NOR, or NAND. The design for such wiring was presented in references [3, 4] above. This will demonstrate a simple instance of massively parallel biomolecular computation providing fundamental building blocks of Boolean based computation.

We are significantly scaling up our solution and surface based experiments for DNA computer arithmetic and logic registers as well as for solution of NP search problems (in particular, the SAT problem). For DNA computer arithmetic and logic registers, we working to scale up to 8 to 16 bits. For the SAT problem, we intend to scale up to the range of 25 Boolean variables, demonstrating massively parallel DNA operations with 2^25 processing elements.

Scaling to larger computational problems requires an increase in the complexity and information density of DNA strands attached to solid supports and increased durability of the underlying chemistries for attachment. We are currently studying new attachment chemistries for gold thin films and Si(100) surfaces for better stability. New enzyme operations for multi-word and circuit SAT calculations are under investigation in order to enable solution of more complex computational problems. We are also creating arrays on silicon surfaces with feature sizes in the 10-50 micrometer range; these arrays are needed for identification of the solutions to larger computational problems.

Now that we have successfully demonstrated that we can use RNA based computing to find solutions to a representative 9-bit problem, our immediate goals are 1) to enhance the technology to the point at which we can choose specific solutions. For example, can we modify the protocol to select the board with the most knights. 2) We will try our approach with a slightly more challenging 9-bit problem, the related Queens problem. 3) We will then synthesize the designed 25-bit library and begin experiments to test our approach and this library on larger versions of the current SAT problems (placement of knights or queens on a 4 x 4 or 5 x 5 board, for example) to test the scalability of the RNA approach.

Demonstrations of Genetic Algorithms: We plan to implement "crossover", a customary operation in Genetic Algorithms. Preliminary techniques were presented in references [2, 5] above. Having both our current selection capability and the planned crossover, the essential components of Genetic Algorithms will be in place. They will be demonstrated using the classical Genetic Algorithms test problem called "Max 1s."