The web page of last year's meeting is at http://www.cis.udel.edu/~dna3.

The Third Annual DIMACS Workshop on DNA Based Computers was held at the University of Pennsylvania June, 1997. was held at The University of Pennsylvania from Monday, June 23 through Wednesday, June 25, 1997. In order to set the stage for the multidisciplinary nature of the conference, two tutorial sessions were held on Sunday, June 22. Dr. David Wood reviewed some basic concepts in computation for the biologists and biochemists and Dr. Laura Landweber reviewed ideas and concepts in molecular biology for the computer scientists and mathematicians.

The morning of the first day of the conference was devoted to the first of two sessions that addressed Making it Work in the Lab and was chaired by Len Adleman. The first paper was an invited lecture delivered by James Wetmur on the physical chemistry of nucleic acids that discussed in detail the thermodynamics and kinetics of polynucleotide and oligonucleotide association and dissociation and reviewed the proper mathematical handling of hybridization parameters. This talk was followed by a paper from the MIT group describing a simulator designed to predict the binding specificity of arbitrary deoxy-oligonucleotides. The MIT group then presented a paper on the efficiency of sequence specific separation techniques including solution based annealing of bead bound probes to target molecules followed by magnetic separation of the annealed probe-target complexes from solution. They stressed the need for a standard set of benchmarks for key primitive operations and volunteered to make their probes available to the research community. The morning session was concluded with a lecture from the Univ. of Delaware group presenting a new DNA separation technique according to the DNA substrings based on circular single strands of DNA that become "marked" by virtue of hybridization to a primer followed by treatment with DNA polymerase generating a double strand. Marked and unmarked registers can then be operated upon in a highly efficient fashion using various enzymes with signal or double stranded specificities.

The afternoon of the first day was devoted to Proposed Applications and was chaired by Erik Winfree. An invited paper by the Princeton group lead off with a novel idea for using DNA computation to operate on unknown pieces of DNA. This would have applications in DNA sequencing, DNA fingerprinting, detection of mutations in populations. They call this DNA2DNA computation. The trick to this technique is in the recoding of naturally occurring DNA into one that contains a prechosen redundant code and then carrying out any of the techniques associated with DNA computation, but on unknown DNA. Then an approach to DNA computation was presented by Andrew Ellington in which DNA, acting as an allosteric effector can activate ribozyme ligase thereby serving as an operator--transforming one nucleic acid sequence into another sequence--i.e., the ligated product. Eng and Serridge from MIT then presented a surface based algorithm for the minimal set cover problem that has the nice property of not requiring separation steps which are error prone. This was followed by a presentation by the University of Tokyo group proposing a solid phase DNA solution to the Hamiltonian Path problem The first day's program was rounded out by a presentation by Fu and Beigel from Yale and U. Maryland that described a general technique for constructing molecular based approximation algorithm for NP optimization problems.

Making it Work in the Lab Part II was the theme of the first session of the second day, and was chaired by Ned Seeman. The first lecture was an invited talk by Hagiya and Arita from The University of Tokyo on the advantage of the inherent parallelism in DNA computation. They introduced a molecular method for parallel evaluation of multiple m formulas in which all possible m formulas are randomly generated and only formulas satisfying the given variable assignments are selected in a single test tube in polynomial time. This was followed by a paper by Laun and Reddy from Binghamton University on extending the work of Tom Head from dry splicing systems which generate a splicing language to wet splicing systems. They presented a simple example of such a wet splicing system that generates in vitro a splicing language corresponding to the theory of the dry system. Next, Kaplan, Thaler and Libchaber presented a method to generate a pool of DNA molecules containing paths through a directed graph using a parallel overlap assembly method. The Mount Sinai School of Medicine group then presented work that followed up on their original bit-flipping DNA operations by showing how horizontal chain reaction can be used to solve simple graph problems thereby showing that it is possible to run a primer extension reactions in parallel. They also a showed that the judicious use of restriction sites in the input DNA can result in a robust readout system. The morning session was rounded out by a presentation from the University of Pennsylvania group in which a DNA based method of bit flipping with the new twist was presented where the result of the operation is of the same molecular form as the input allowing iterated operations, including the possibility of reversing the computation.

The afternoon session with the theme of Proposed Algorithmic Approaches, chaired by Richard Lipton on Tuesday started with an invited talk by Aviezri Fraenkel from the Weizmann Institute of Science, Israel, He presented a theoretical discussion of the relationship between the protein folding problem and NP complete problems. He related protein folding to finding the ground state of spin glasses. This lead him to suggest that it might be possible to synthesize specific proteins to solve arbitrary instances of the spin glass problem. This was followed by a paper by the University of South Florida group that took off into space, suggesting that 3 dimensional graphs could be constructed using DNA. This could be a more efficient computational tool than mere linear constructs. The University of Memphis then presented an exploration of the feasibility, reliability and efficiency of DNA based computation by grappling with the ability of DNA to implement nondeterminism as a native mode of computation. Gupta, Parthasarathy and Zaki from the University of Rochester then addressed the theoretical possibility of carrying out arithmetical and logic operations with DNA. A poster session was held during the afternoon and carried over into the last day of the conference.

The last day of the conference started with a session devoted to Models of DNA Computers and was chaired by Lila Kari. John Reif delivered an invited lecture in which he strongly advocated the development of local parallelism (LP) in biomolecular computation as opposed to the more generally understood distributed parallelism (DP). He pointed out that all LP operations could be used in combination with DP methods. This was followed by a paper by Ogihara and Ray entitled DNA-based parallel computation by "counting". Next Andrew Blumberg from MIT presented a theoretical paper on parallel computation using DNA substrates and addressed specifically the problem of sharing information between strands--a key element in any successful application of parallel computation. He discussed a model which simulates a message routing architecture. Conrad and Zauner from Wayne State University then discussed the design for a DNA conformational processor based on the capacity of DNA to switch from the B form to the Z form in response to methylation of cytosine residues. Eng from MIT then showed in a theoretical sense how the self assembly of linear duplexes with hairpins generates sequences that are equivalent to linear context-free languages. The last session of the conference entitled Computability Using DNA was chaired by John Reif and started with an invited lecture from the multinational group of Freund (Austria), Paun (Romania), Rozenberg (Netherlands) and Salomaa (Finland), delivered by Freund. They related automata theory and biomolecular computation, proposing machines similar to finite automata that handle inputs and outputs in a fashion that ensures universality. This was followed by a paper by Kari, Paun, Thierrin and Yu, delivered by Kari, on characterizing recursively enumerable (RE) languages using insertion/deletion systems. They showed the nexus between insertion and deletion in DNA--a common biological phenomenon and generating RE languages by inserting and deleting words according to their contexts. Yokomori and Kobayashi from The University of Electro-communications in Japan presented a paper on DNA computation based on a principle of equality checking where the task of equality checking of two memories represented by a string of symbols is isomorphic to a completely hybridized double stranded DNA sequence. The final paper of the conference by Sakakibara (Tokyo Denki University) and Ferretti (University of Milan) extended the notion of splicing systems on strings to splicing systems on tress and showed how splicing systems on trees with finite sets of axioms and finite sets of rules generates the class of context free languages without the need of multiplicity constraints.