Laboratory Work

We are currently working on incorporating the programmed mutagenesis technique into DNA computing.

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 programed 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 r_i is meant to be applied to a strand of DNA representing state s_i, producing a strand representing state s_i+1 to produce a strand representing s_i+2, it should be the case that r_i+1 cannot be applied to s_i+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 s_i to the state representing s_i+2 by first passing through s_i+1, with each rewrite rule being applied in sequence, thereby capturing the notion of programmatic computation.

Limited forms of programmed mutagenic unary counters have been built in the laboratory and the technique is believed to be generally extensible.

Computer Software

• BIND
  Nearly every model of DNA computation proposed to date depends upon sequence-specific hybridization operations. In order to better predict the binding specificity of arbitrary deoxyoligonucleotides, a simulator named bind is implemented. Bind operates on a single template DNA sequence and a number of shorter primer sequences. For each primer sequence, bind calculates a theoretical melting temperature at every position of the primer along the template, yielding a measure of binding specificity between each primer and the template. The simulator differs from previous melting temperature programs in that it is intended to be used with oligonucleotides, is designed to handle mismatched base pairs, makes use of the latest thermodynamic parameters, and provides features with DNA computation expressly in mind. This paper describes how bind is implemented, provides corroborating evidence as to its accuracy, and offers instances of its usefulness to a range of DNA computing applications.
• SCAN
  We present techniques for automating the design of computational systems built using DNA, given a set of high-level constraints on the desired behavior and performance of the system. We have developed a program called scan that exploits a previously implemented computational melting temperature primitive to search a \nucleotide space" for sequences satisfying a pre-specified set of constraints, including hybridization discrimination, primer 5' end and 3' end stability, secondary structure reduction, and prevention of oligonucleotide dimer formation. The first version of SCAN utilized 24 hours of compute time to search a space of over 7.5 billion unary counter designs and found only 9 designs satisfying all of the pre-specified constraints. One of SCAN's designs has been implemented in the laboratory and has shown a marked performance improvement over the products of previous attempts at manual design. We conclude with some novel ideas for improving the overall speed of the program that offer the promise of an efficient method for selecting optimal nucleotide sequences in an automated fashion.
• CYBERCYCLER
  A general purpose tool for simulating thermocycled biological reactions such as those used to increment our unary counter. For more information, see our BioSim page.