ABSTRACT: In recent work, (Biosystems 52, 15-23, 1999 A biomolecular implementation of logically reversible computation with minimal energy dissipation. Klein JP, Leete TH, Rubin H) we demonstrated a biomolecular implantation of logically reversible computation using short strands of DNA as input and output lines of a Fredkin gate. We described how to connect these gates so that more complicated genetic networks could be created.

It is our thesis that in order to achieve the full potential of biomolecular computation, cis- and trans-acting network capabilities, including site-specific protein-protein and protein-nucleic acid interactions must be incorporated into the design. Our goal therefore is to extend our work on biomolecular Fredkin gates to utilize specific DNA binding proteins as control elements.

ABSTRACT: We have recently solved a small (4-bit) example of 3-SAT using a

surface-based approach. Scale-up to solve 16 bit and 36 bit examples is

projected, requiring respectively 128 and 768 oligonucleotides. Information will be encoded using multiple tandem words (4 and 6 respectively); this scale-up will also require the implementation of a multiple-word "Destroy-Unmarked" operation presently under development. The surface chemistry which has been developed for this project also has manifold applications in the fields of biotechnology. Highly reproducible DNA-modified surfaces have been engineered on gold and silicon (111) surfaces, with exquisite control of binding specificity achieved through

"programmable" surface chemistries.

ABSTRACT: We have expanded the field of "DNA Computers" to RNA and present a general approach for the solution of satisfiability (SAT) problems. As an example, we consider a variant of the "Knight problem", which asks generally what configurations of knights can one place on an n x n chess board such that no knight is attacking any other knight on the board. Using specific ribonuclease digestion to manipulate strands of a 10-bit binary RNA library, we developed a molecular algorithm and applied it to a 3 x 3 chessboard as a 9-bit instance of this problem. Here, the nine spaces on the board correspond to nine 'bits' or placeholders in a combinatorial RNA library. We recovered a set of 'winning' molecules that describe solutions to this problem. I will discuss the scalability and

limitations of this approach to molecular computing.

ABSTRACT: We propose to conduct a large scale computer simulation of the Boolean circuit evaluation methods we devised (Ogihara and Ray, 1997; Ogihara and Ray, 1998). In these method, each gate of a simulated Boolean circuit is assigned a unique single DNA strand, and the presence of the strand at any time of the reaction is regarded as the gate outputting 1. In the first method the strands corresponding to the outputs of gates are synthesized with human intervention (electrophoresis, restriction, etc.). In the latter they are synthesized by primer extension and cleavage by restriction enzymes. The strands from one level of the circuit become templates and trigger primer extension for the next level, and the extended patterns are cut out by restriction enzymes. Thus, the new method improves the previous methods by allowing one to conduct the whole computation in a single test tube without having to separate intermediate products. We term this the ``self-propagation'' method.

ABSTRACT: The process of gene unscrambling in hypotrichous ciliates represents one of nature’s ingenious solutions to the computational problem of gene assembly. With some essential genes fragmented in as many as 50 pieces, these organisms rely on a set of sequence and structural clues to detangle their coding regions. For example, pointer sequences present at the junctions between coding and noncoding sequences permit reassembly of the functional copy. As the process of gene unscrambling appears to follow a precise algorithm or set of algorithms, the question remains: what is the actual problem being solved? The first proposed step in gene unscrambling–alignment or combinatorial pattern matching–may involve searches through several possible matches, via either intramolecular or intermolecular strand associations. We have conjectured that this part could be similar to Adleman’s (1994) DNA solution of a directed Hamiltonian path problem. The second step–homologous recombination at aligned repeats–involves the choice of whether to retain the coding or the noncoding

segment between each pair of recombination junctions. This decision process could even be equivalent to solving an n-bit instance of a satisfiability problem, where n is the number of scrambled segments. We use our knowledge of the first step to

develop a model for the guided homologous recombinations and prove that such a model has the computational power of a Turing machine, the accepted formal model of computation. This indicates that, in principle, these unicellular organisms

may have the capacity to perform at least any computation carried out by an electronic computer.

ABSTRACT: Programmed mutagenesis is a technique for programmatically rewriting DNA sequences by incorporating sequence-specific oligonucleotides into newly manufactured strands of DNA. Three significant advantages to using programmed mutagenesis for DNA computation are: i. The pool of oligonucleotide rewrite rules can be designed to cause sequence-specific programmed changes to occur, including the propagation of programmed changes up and down a DNA molecule and the evolution of a programmed sequence of changes over the course of future replication events. Thus, sequential computations with programmatically evolving state can be carried out, resulting in constructive computation, as contrasted with selective computation which requires all possible solutions to a problem to be present ab initio. ii. The sequence specificity of the oligonucleotide rewrite rules allows multiple rules to be present at each step of the reaction, with only a fraction of them being active during each cycle. This reduces human effort since it permits the computation to be carried forward by thermocycling the reactants in the presence of thermostable polymerase and ligase. Ideally, there is no need for human (or robotic) intervention between computational cycles. iii. All of the components necessary to implement programmed mutagenesis are present in vivo. Therefore it may eventually be possible to harness the internal workings of the cell for computation, thereby capitalizing on the cell's homeostatic capabilities to ensure that the computation takes place in a stable and well-regulated environment. The salient point regarding programmed mutagenesis is that it relies on the binding specificity of its rewrite rules to ensure that the template strand of DNA is being rewritten in a systematic way. For example, if rewrite rule ri is meant to be applied to a strand of DNA representing state si, producing a strand representing state si+1 to produce a strand representing si+2, it should be the case that ri+1 cannot be applied to si+1. If this condition is satisfiable, then both of the rewrite rules can be present in the reaction and yet the system can only evolve from the state representing si to the state representing si+2 by first passing through si+1, with each rewrite rule being applied in sequence, thereby capturing the notion of programmatic computation.

ABSTRACT: Each of our computations begins with a volume of water (buffer) in which a vast number of identical molecules is dissolved, each of which serves as a memory register on which bits can be 'written' at a prescribed set of locations. Many molecules can be considered for use as memory registers and many physico-chemical means of writing can be conceived. At this early stage we are using a double stranded DNA circular plasmid as memory register. Computations are being carried out on this basis in laboratories at Leiden University and Binghamton University. Solutions of instances of the maximal independent set problem and the minimal vertex cover problem have been completed and a solution of an instance of Boolean satisfiability is near completion. At least one of these laboratory computations will be briefly reported with a confirming gel photo. As the next step we propose to continue using DNA plasmids, but to 'write' on them with methyases. At a longer time scale we propose to use our experience with plasmids to attack plasmid borne bacterial virulence.

ABSTRACT: In vitro selection can be used to identify nucleic acids with a wide range of novel binding and catalytic properties. Most recently, it has proven possible to combine binding and catalysis by designing and selecting allosteric ribozymes, also known as aptazymes. We have appended aptamers that bind small effectors to a selected ribozyme ligase. The resultant aptazymes sense the presence of ligands in solution and ligate oligonucleotides to themselves. The activities of aptazymes are up-regulated one two to three orders of magnitude by their effectors. The simplicity of the design principles involved allows simple logic gates to be constructed. Because a variety of reporters can be ligated to aptazymes, from fluors to enzymes, these new reagents can be thought of as generalized signal transducers. In particular, we are investigating whether an aptazyme can catalyze the effector-dependent ligation of an oligonucleotide conjugated to horseradish peroxidase to itself. If so, then the immobilization of the aptazyme on an electrode surface would allow the concomitant, effector-dependent immobilization of a strong electron generator, and thus would facilitate the transduction of molecular recognition to an electronic signal. It is hoped that the generalizable molecular recognition abilities of aptamers coupled with a similarly generalizable signal transduction reagent will enhance efforts to ‘digitize’ biology. To further enhance these efforts, we suggest that the biological world be seeded with nucleic acid taggants that can be readily sensed by reagents such as aptazymes.

dfdIn vitro selection can be used to identify nucleic acids with a wide range of novel binding and catalytic properties. Most recently, it has proven possible to combine binding and catalysis by designing and selecting allosteric ribozymes, also known as aptazymes. We have appended aptamers that bind small effectors to a selected ribozyme ligase. The resultant aptazymes sense the presence of ligands in solution and ligate oligonucleotides to themselves. The activities of aptazymes are up-regulated one two to three orders of magnitude by their effectors. The simplicity of the design principles involved allows simple logic gates to be constructed. Because a variety of reporters can be ligated to aptazymes, from fluors to enzymes, these new reagents can be thought of as generalized signal transducers. In particular, we are investigating whether an aptazyme can catalyze the effector-dependent ligation of an oligonucleotide conjugated to horseradish peroxidase to itself. If so, then the immobilization of the aptazyme on an electrode surface would allow the concomitant, effector-dependent immobilization of a strong electron generator, and thus would facilitate the transduction of molecular recognition to an electronic signal. It is hoped that the generalizable molecular recognition abilities of aptamers coupled with a similarly generalizable signal transduction reagent will enhance efforts to ‘digitize’ biology. To further enhance these efforts, we suggest that the biological world be seeded with nucleic acid taggants that can be readily sensed by reagents such as aptazymes.

ABSTRACT: In our laboratory, we have constructed a preliminary prototype of a universal DNA chip that can read out arbitrary graphs. Graphs include ordered schedules of tasks such as Traveling Salesman tours. When multiple answers are simultaneously present, a divide and conquer algorithm using the universal chip can isolate individual answers. DNA computing techniques are desirable for Evolutionary Computation because they process, in parallel, populations billions of times larger than is usual for conventional computers. However, it is challenging to physically separate DNA strands according to a programmed "fitness criterion." We have designed and carried out preliminary laboratory demonstrations of "separation by fitness" using 2-dimensional Denaturing Gradient Gel Electrophoresis.

ABSTRACT: A basic module for molecular computers can be used to assemble a complex nanostructure (Cayley graph) with a high computational payoff (perhaps super Turing power). Complex biomolecular structures are hard to design, but certain Cayley graphs can be assembled from basic building blocks (protocells) evolved in vitro. The evolutionary process exploits what biomolecules do best, respond and adapt to each other and their environment. Fit protocells must be capable of interconnecting to form the graph in a self-regulating and synergistic way. The final assembly will make possible a new paradigm for molecular computing in which solutions are simply looked up on pre-computed, complex memory structures (Cayley graphs).

ABSTRACT: We first discuss the USA Collaborative Project in BMC: CONSORTIUM FOR BIOMOLECULAR COMPUTING AND ITS APPLICATIONS funded by a Joint DARPA/NSF grant: Prototyping Biomolecular Computing, with PI John Reif. We discuss various CANADIAN Projects in BMC, including that of Lila Kari, University of Western Ontario, ON, Canada. We then discuss the EUROPEAN Collaborative Project in BMC: THE EUROPEAN MOLECULAR COMPUTING CONSORTIUM (EMCC) which is funded by: European Community, and is lead by G. Rozenberg. Finally, we discuss the JAPANESE Collaborative Project in BMC: JSPS PROJECT ON MOLECULAR COMPUTING, which is funded by: Japan Society for Promotion of Science (JSPS), Research for the Future Program, Biocomputing Field and is lead by a group of Japanese including Masami Hagiya.

ABSTRACT: DNA nanotechnology is the assembly of target molecules and materials from unusual motifs of DNA, particularly branched molecules. These branched motifs constitute a convenient system for the tractable assembly of objects, knots and links on the nanometer scale. The addition of sticky ends to branched DNA molecules converts them to convenient valence clusters with addressable ends. In the past, we have assembled molecules whose edges have the connectivities of a cube and a truncated octahedron by using this approach. The assembly of periodic matter from these components is a key goal of DNA nanotechnology. The minimal requirements for components of designed crystals are [1] programmable interactions, [2] predictable local intermolecular structures and [3] rigidity. The sticky-ended association of DNA molecules fulfills the first two criteria, because it is both specific and diverse, and because it results in the formation of B-DNA. Stable branched DNA molecules permit the formation of networks in principle, but simple branches are too flexible. Antiparallel DNA double crossover (DX) molecules can provide the necessary rigidity, so we can use these components to tile the plane. It is possible to include DNA hairpins that act as topographic labels for this 2-D crystalline array, because they protrude out of the plane. By altering the sticky ends, it is possible to change the topographic features, and to detect these changes by means of AFM. We can modify the array by restricting hairpins or by adding them to the array. Although simple 4-arm branched junctions are too flexible to be used as lattice components, parallelograms containing four single-crossover molecules are sufficiently rigid that they can be used to produce 2D arrays with tunable cavities. A third motif leading to 3D entails the use of triple crossover molecules.

ABSTRACT: DNA based computation relies on using molecular biology techniques to construct mathematically structured libraries of DNA molecules. It is imperative to develop techniques wherein complex libraries can be constructed in relatively few laboratory steps -- ideally one or a constant number. Self-assembly of DNA is an attractive approach, because multiple hybridization events can occur in sequence in a single reaction. Winfree previously developed a model of computation by self-assembly of DNA in which the computation proceeds by hybridization of DNA molecules into larger complexes, and ligation of strands in the resulting complexes produces a combinatorial library of DNA sequences. The possible output languages (regular, context-free, recursively enumerable) can be classified according to the type of DNA structures used (linear duplex, dendrimer, 2D lattice), thus showing a parallel between molecular self-assembly and the classic Chomsky hierarchy of formal languages. These results establish that any computable function can be computed by self-assembly. The central argument showed how to map the mathematics of Wang tiles onto Seeman's double-crossover (DX) molecules. Future research will apply these results to particular problems, such as addition and multiplication, and will analyze the efficiency of self-assembly for generating combinatorial libraries. Ongoing work (with Grzegorz Rozenberg of Leiden University and Tony Eng of MIT, in preparation) examines computational self-assembly where the topological routing of DNA strands -- rather than just the arrangement of units -- helps determine the output. This work has already led to a promising approach for arithmetic in DNA computation that is being tested experimentally (LaBean et al, DNA Based Computers V, 1999). An important goal is to evaluate the speed and error rates of the various types of self-assembly reactions. Exploring the use of algorithmic self-assembly as a bottom-up approach for the fabrication of complex nanostructures, we are studying the program-size complexity of self-assembled shapes (with Paul Rothemund, in preparation). These theoretically-motivated assembly reactions will then be prototyped experimentally.

ABSTRACT: Our research in DNA self-assembly exploits the exquisite specificity of nucleic acid polymers in annealing to their complementary sequences for the construction of algorithmic lattices. We are utilizing self-assembly to perform computations directly through design and assembly of computational lattices. We are currently implementing massively parallel n-bit addition using a "string tile" design, in which a reporter strand traces several times through the computational assembly and can be used to easily readout the input and output values. We also have begun studies aimed at the use of structural lattices as patterning templates upon which nano-wire and eventually circuits can be constructed. Structural lattices have been created with surface features such as extra loops or arms to which gold nano-spheres can be attached. Under proper chemical conditions, additional gold can be induced to adhere to the immobilized nano-spheres causing them to increase in size and fuse with neighboring spheres. Given a suitable DNA lattice to "seed" gold spheres at critical positions, we should be able to grow nano-scale wires and more complicated structures including circuits.

ABSTRACT: One would like to invent a technology in which very large-scale integrated (VLSI) structures with molecular-scale features could be assembled molecule by molecule through molecular recognition. To keep the assembly times and error rates sufficiently low it would be desirable to carry out such assembly away from thermodynamic equilibrium. To this end, we are studying DNA systems in which the hybridization of a pair of complementary strands can be catalytically controlled by other DNA strands. We are also devising DNA structures that can perform thermodynamic work.

ABSTRACT: We describe computational methods using three dimensional (3D) DNA structures (knots and graphs) possibly made with the aid of other molecules such as RNA, PNA and enzymes (e.g. topoisomerases and recombinases). Understanding of when, how and what three dimensional DNA structures can be constructed and used leads to (1) a more profound understanding of natural processes in vivo, in particular in processes of gene activation and (2) potentially developing a new method of computation with three dimensional structures (knots or graphs) unavailable with our electronic computers. It is shown, theoretically, that building blocks of k-armed branched junction molecules can be used to form graphs and solve several NP-complete problems [JKS,JKS2,J].

ABSTRACT: The Laboratory for Molecular Science is engaged in several projects including: DNA computation, exquisite detection and molecular

self-assembly. All of our projects involve the control and manipulation of the molecular world. We appear to have the tools necessary to carry out a ‘substantial’ DNA computation on a ‘semi-automated’ device. We expect to undertake an approximately 20 variable SAT computation in the near future. Much progress has been made in exquisite detection. Our assay for Reverse Transcriptase, our ‘testbed’ protein, detects as few as 1 molecule on a background of 10^20 other molecules - approximately 10^5 more sensitive that existing commercial assays. We are considering general methods for the exquisite detection of large classes of substances.

ABSTRACT: The talk is based upon a paper that appeared this summer: Clelland, C.T., Risca, V., and C. Bancroft (1999). "Hiding Message in DNA Microdots" Nature 399:533-534. Steganography is a form of cryptography in which a secret message is hidden among many similar objects. In our doubly steganographic technique, a DNA-encoded message is first camouflaged within the enormous complexity of human genomic DNA. The message is flanked with primer sequences known only to the sender and intended recipient, permitting only the intended recipient to employ polymerase chain reaction to amplify and thus read the message. In the second steganographic procedure, the message is further concealed by confining this sample to a microdot the size of a period, which is then pasted over a period in an innocuous letter. We believe that it would be extremely difficult for an adversary to detect and read a message hidden according to our technique.

ABSTRACT: Recent research has considered DNA as a medium for ultra-scale computation and for ultra-compact information storage. One potential key application is DNA- based, molecular cryptography systems. We present some procedures for DNA-based cryptography based on one-time-pads that are in principle unbreakable. Practical applications of cryptographic systems based on one-time-pads are limited in conventional electronic media, by the size of the one-time-pad; however DNA provides a much more compact storage media, and an extremely small amount of DNA suffices even for huge one-time-pads. We detail procedures for two DNA one-time-pad encryption schemes: (i) a substitution method using libraries of distinct pads, each of which defines a specific, randomly generated, pair-wise mapping; and (ii) an XOR scheme utilizing molecular computation and indexed, random key strings. These methods can be applied either for the encryption of (appropriately recoded) natural DNA, and also for the encryption of DNA encoding binary data. In the latter case, we also present a novel use of chip-based DNA micro-array technology for 2D data input and output. Finally, we examine a class of DNA steganography systems, which secretly tag the input DNA and then disguise it (without further modifications) within collections of other DNA. We consider potential limitations of these steganography methods, showing that with some assumptions on the information theoretic entropy of the plaintext messages, certain DNA steganography systems may not be cryptographically secure, and can be broken. We also discuss various modified DNA steganography systems which appear to have improved security.

ABSTRACT: We discuss a method for doing large scale neural network computation via DNA computation. An example application for associative retrieval of images is described.

ABSTRACT: The goal of our project is to construct cellular computers for process control (Microbial Robotics). Potential applications for this technology include embedded intelligence in materials, sensor/effector arrays, drug and biomaterial manufacturing, smart medicine, and nanoscale fabrication. In the first phase, we are implementing in-vivo logic circuits by harnessing existing genetic regulatory mechanisms of repression and transcription. Logic signals are represented by the concentration of cytoplasmic DNA binding proteins. Gates are constructed from promoter/operator regions that are regulated by input proteins, fused with structural genes that code for output proteins. We are now in the process of characterizing several gates built in our laboratory. Once the behavior of these gates is quantified, they will be combined in a modular fashion to build simple circuits, including an RS-Latch ("flip flop") and a ring oscillator.

ABSTRACT: The talk is based upon a paper in press: Bloom, B., and C. Bancroft. "Liposome Mediated Biomolecular Computation". Proceedings of the Fifth Annual Conference on DNA-Based Computers, Massachusetts Institute of Technology, June 14-15, 1999. Scale-up and automation of many of the current algorithms for DNA-based computation will probably require the use of a large number of very small test tubes, connected via valves, switches, etc. We propose that this type of architecture could be based upon the use of biochemical structures termed liposomes. These structures might serve as biological test tubes with built-in valves, because they possess the following properties. Liposomes are spherical structures formed from phospholipids, with an aqueous cavity that can contain DNA in solution. Liposomes can fuse, merging their (DNA) content, and different types of liposomes can be made to fuse by varying simple environmental parameters such as pH, calcium concentration, etc. We thus propose that controlled fusion of liposomes containing different species of DNA will prove useful in carrying out DNA-based computations, especially those that require massively parallel processing.