Organizer:

Jan Mulawka

Institute of Electronics Fundamentals

Warsaw University of Technology

ul. Nowowiejska 15/19

00-665 Warsaw, Poland

Phone: (+48 22) 660 53 19; Fax: (+48 22) 825 23 00

jml@ipe.pw.edu.pl

http://www.ipe.pw.edu.pl/~gair

1. Towards a System for Simulating DNA Computing Using Secondary Structure

Akio Nishikawa, Masami Hagiya

University of Tokyo, Japan

nisikawa@is.s.u-tokyo.ac.jp

Whiplash PCR is a useful method for analyzing DNA. For example, state transitions can be implemented by this method. In normal PCR, extension is guided by the annealed complementary DNA sequence. Whiplash PCR is a modification of normal PCR in which the 3'-end of the target single-stranded DNA molecule is extended by polymerase when it anneals to a complementary sequence in the target DNA molecule, so that the secondary structure of the target single-stranded DNA forms the guiding sequence. When the annealed sequences are extended by PCR, the guiding sequence and the composition of the PCR reaction buffer control termination. If the PCR buffer lacks T and the guiding sequence contains an AAA sequence, the PCR extension will stop at the sequence AAA. In Whiplash PCR, like normal PCR, the molecule is subsequently denatured by high temperature, the guiding sequence re-anneals when the temperature is lowered for the next extension step and the cycle repeats. Whiplash PCR is a very powerful technique for solving certain types of problems, but the feasibility of using it in a specific instance should be carefully considered. The target molecule must form a secondary structure by annealing to itself, and it must be capable of melting and reforming a similar secondary structure. To implement this, the sequences must be carefully designed. The simulation system we are constructing checks whether the sequences can form such secondary structures by examining the nucleotide sequence. It also simulates sequence extension by ligation, PCR and whiplash PCR, mishybridization, affinity separation, and restriction enzyme digests. By combining all these types of reaction simulations, it can simulate a series of DNA computing processes, which will aid the designers of DNA computing reactions. We are now constructing such simulation software based on sequence comparison, and will report our current stage of development. In addition to developing the simulation methods based on sequence comparison, we have investigated possible enhancements of our system. Simply using a method based on sequence comparison to examine the feasibility of DNA computing using secondary structures is inadequate. We plan to enhance our system in two ways. First, it will check the conditions for each reaction step with reaction parameters such as the PH, temperature, and makeup of the PCR reaction buffer. Second, it will calculate and examine the physico-chemical parameters affecting the secondary structure necessary for whiplash PCR. In other words, the sequences can form such secondary structures by examining the nucleotide sequence. It also simulates sequence extension by ligation, PCR and whiplash PCR, mishybridization, affinity separation, and restriction enzyme digests. By combining all these types of reaction simulations, it can simulate a series of DNA computing processes, which will aid the designers of DNA computing reactions. We are now constructing such simulation software based on sequence comparison, and will report our current stage of development. In addition to developing the simulation methods based on sequence comparison, we have investigated possible enhancements of our system. Simply using a method based on sequence comparison to examine the feasibility of DNA computing using secondary structures is inadequate. We plan to enhance our system in two ways. First, it will check the conditions for each reaction step with reaction parameters such as the PH, temperature, and makeup of the PCR reaction buffer. Second, it will calculate and examine the physico-chemical parameters affecting the secondary structure necessary for whiplash PCR. In other words, it will check the feasibility from a physico-chemical perspective. We would like to discuss these enhancements and the feasibility of our simulation system. Furthermore, if possible, we would like to compare the results of our simulation system with in vitro experiments.

2. PNA-enhanced DNA Computing

J. Miro-Julia, F. Rossello

UIB University, Spain

joe@ipc4.uib.es

Since Adleman's seminal paper, DNA computing is emerging as a very promising alternative to electronic computing. It s massive parallelism, its low energy needs, even its possible ability of breaking the NP barrier make its study irresistible. But for all its promise DNA computing has few results to show. This is in because there are many biochemical problems in handling DNA that are still to be solved. Peptyde Nucleic Acid (PNA) is a new class of informational biomolecule, a nucleic acid analogue with a backbone consisting of a peptide-like chain formed of glycine units to which the usual nucleobases are attached. DNA molecules have some properties, relevant to the area of computation with biomolecules, unique among nucleic acids: among others, they hybridize to both complementary DNA and RNA with higher affinity that DNA itself. They can be used to enhance PCR amplification, and they can be used to restrict the action of restriction enzymes on DNA strands. The goal of this paper is to introduce PNA in the area of computation with biomolecules, and to discuss its possible role in overcoming some of the drawbacks that appear with DNA.

3. Efficient DNA Computation of Spanning Trees

Martyn Amos, Shinichiro Yoshii, Paul E. Dunne and Alan Gibbons

University of Liverpool, UK

martyn@csc.liv.ac.uk

In this paper we demonstrate the translation of a high-level algorithm down to the level of molecular operations on DNA. For DNA computation to be a viable and competitive paradigm, we need algorithms that require viable resources (time and volume). We describe a translation of a parallel algorithm for the computation of spanning trees on graphs that is resource-efficient.

4. The Analysis of a Simple Programmed Mutagenesis System.

Julia Khodor and David K. Gifford

Laboratory for Computer Science, MIT, USA

Jkhodor@MIT.EDU

We present the experimental results of the advanced cycles of string rewrite system based on programmed mutagenesis, a technique for rewriting DNA strands according to programmed rules. We have previously shown that formation of the second-cycle product depends on successful completion of the first cycle, and demonstrated that two oligonucleotides annealing to the template next to each other can ligate and extend to form the correct product. We now report our findings on the behavior of the advanced cycles of the system. We discuss several factors influencing the behavior of the system, such as the choice of enzymes, temperatures, and concentrations. The efficiency of the system and the potential significance of the results to the field of DNA-computing are also discussed.

5. Executing Parallel Logical Operations with DNA

Mitsunori Ogihara and Animesh Ray

University of Rochester, USA

ogihara@cs.rochester.edu

DNA computation investigates the potential of DNA as a massively parallel computing device. Research is focused on designing parallel computation models executable by DNA-based chemical processes and on developing algorithms in the models. In 1994 Leonard Adleman initiated this area of research by presenting a DNA-based method for solving the Hamilton Path Problem. That contribution raised the hope that parallel computation by DNA could be used to tackle NP-complete problems which are thought of as intractable. The current realization, however, is that NP-complete problems may not be best suited for DNA-based (more generally, molecule-based) computing. A better subject for DNA computing could be large-scale simulation of parallel computation models. Several proposals have been made in this direction. We overview those methods, discuss technical and theoretical issues involved, and present some possible applications of those methods.

6. Aspects of Evolutionary DNA Computing

Thomas Baeck , Joost Kok, and Grzegorz Rozenberg

Leiden University, The Netherlandes

baeck@icd.de

Evolutionary Computation focuses on probabilistic search and optimization methods gleaned from the model of organic evolution. Genetic algorithms, evolution strategies and evolutionary programming are three independently developed representatives of this class of algorithms, with genetic programming and classifier systems as additional paradigms in the field. After giving a general introduction to evolutionary algorithms and demonstrating their practical usefulness as heuristics for finding good solutions in combinatorial and continuous problem domains with a few application examples, the presentation emphasizes on certain features of genetic algorithms and evolution strategies: Namely, the mutation and recombination operators from genetic algorithms and the selection operator from evolution strategies are discussed in more detail. Furthermore, some theoretical results concerning the convergence velocity of certain variants of genetic algorithms are presented, and in particular the question for optimal mutation rates in genetic algorithms is discussed. Based on this detailed background information about evolutionary algorithms, it is then outlined how these algorithms relate to DNA based computing.

7. The Inference via DNA Computing

J. Mulawka, P. Wasiewicz, and A. Plucienniczak

Warsaw University of Technology, Poland

jml@ipe.pw.edu.pl

Most of research on DNA computing concerns solving NP-complete problems, programming in logic as well as purely mathematical consideration of splicing theory. There is no doubt that these works have given new impetus to find another areas for DNA computing. In proposed paper we show that self-assembly of DNA strands may be applied to implement the inference process. The ability of such an application was provided for the first time by J.J. Mulawka et al. At the International Conference on Evolutionary Computation in Anchorage, 1998. In this paper we would like to report another achievements in this field. The inference process can be implemented either by backward or forward chaining. We have developed new methods of inference based on another concept of genetic engineering. The primary objective of our paper is to describe these methods and procedures. After short introduction to the subject an overview of the problem will be provided. It will be shown how knowledge can be structured, and stored by means of DNA strands. Next, we describe an implementation of DNA inference engine. Such system can store knowledge for a narrowly defined subject area and solve problems by making logical deductions. The inference mechanism performs these tasks by manipulating on DNA strands. It provides the problem-solving methods by which the rules are processed. Our approach uses standard operations of genetic engineering. To check correctness of our method a number of laboratory tests have been carried out. The results of these experiments as well as concluding remarks will be provided in final version of the paper.

8. Byoun-Tak Zhang from Korea

9. H. Rubin rubinh@mail.med.upenn.edu

10. T. Head tom@math.binghamton.edu