DNA Computing

1. Front Matter

   Pages I-X

   PDF

2. Engineered communications for microbial robotics

   • Ron Weiss, Thomas F. Knight Jr.

   Pages 1-16

3. Successive state transitions with I/O interface by molecules

   • Ken Komiya, Kensaku Sakamoto, Hidetaka Gouzu, Shigeyuki Yokoyama, Masanori Arita, Akio Nishikawa et al.

   Pages 17-26

4. Solution of a satisfiability problem on a gel-based DNA computer

   • Ravinderjit S. Braich, Cliff Johnson, Paul W. K. Rothemund, Darryl Hwang, Nickolas Chelyapov, Leonard M. Adleman

   Pages 27-42

5. Diophantine equations and splicing: A new demonstration of the generative capability of H systems

   • Pierluigi Frisco

   Pages 43-52

6. About time-varying distributed H systems

   • Maurice Margenstern, Yurii Rogozhin

   Pages 53-62

7. String tile models for DNA computing by self-assembly

   • Erik Winfree, Tony Eng, Grzegorz Rozenberg

   Pages 63-88

8. From molecular computing to molecular programming

   • Masami Hagiya

   Pages 89-102

9. Graph replacement chemistry for DNA processing

   • John S. McCaskill, Ulrich Niemann

   Pages 103-116

10. DNA and circular splicing?

    • Paola Bonizzoni, Clelia De Felice, Giancarlo Mauri, Rosalba Zizza

    Pages 117-129

11. Molecular computing with generalized homogeneous P-systems

    • Rudolf Freund, Franziska Freund

    Pages 130-144

12. Computationally inspired biotechnologies: Improved DNA synthesis and associative search using Error-Correcting Codes and Vector-Quantization?

    • John H. Reif, Thomas H. LaBean

    Pages 145-172

13. Challenges and applications for self-assembled DNA nanostructures?

    • John H. Reif, Thomas H. LaBean, Nadrian C. Seeman

    Pages 173-198

14. A space-efficient randomized DNA algorithm for k-SAT

    • Kevin Chen, Vijay Ramachandran

    Pages 199-208

15. A DNA-based random walk method for solving k-SAT

    • Sergio Díaz, Juan Luis Esteban, Mitsunori Ogihara

    Pages 209-220

16. Solving computational learning problems of Boolean formulae on DNA computers

    • Yasubumi Sakakibara

    Pages 220-230

17. The fidelity of annealing-ligation: A theoretical analysis

    • John A. Rose, Russell J. Deaton

    Pages 231-246

18. DNA implementation of a Royal Road fitness evaluation

    • Elizabeth Goode, David Harlan Wood, Junghuei Chen

    Pages 247-262

19. Steady flow micro-reactor module for pipelined DNA computations

    • John S. McCaskill, Robert Penchovsky, Marlies Gohlke, Jörg Ackermann, Thomas Rücker

    Pages 263-270

20. Back Matter

    Pages 271-271

    PDF

The papers in this volume were presented at the 6th International Meeting on DNA Based Computers, organized by the Leiden Center for Natural Computing and held from June 13 to June 17, 2000 at The Lorentz Center, University of Leiden, Leiden, The Netherlands. DNA Computing is a novel and fascinating development at the interface of computer science and molecular biology. It has emerged in recent years, not simply as an exciting technology for information processing, but also as a catalyst for knowledge transfer between information processing, nanotechnology, and biology. This area of research has the potential to change our understanding of the theory and practice of computing. The call for papers and poster presentations sought contributions of original research and technical expositions in all areas of bio-computation. A total of 33 abstracts were submitted of which 16 were accepted for presentation and included in the proceedings. The papers were selected by the program committee based on originality and quality of research and on relevance to the bio-computing eld. Invited talks were given by Masami Hagiya (Tokyo University), Laura La- weber (Princeton University), John Reif (Duke University), Thomas Schmidt (Leiden University), and Lloyd M. Smith (University of Wisconsin). Invited - pers based on the talks by Hagiya and Reif are included in this volume, along with the contributed papers. Additional tutorials were held on the rst and last days of the conference.

• Biocomputing
• Bioinformatics
• DNA Algorithms
• DNA computing
• DNA-Based Computers
• DNA-Computing
• Fitness Evaluation
• Molecular Biology
• Molecular Computing
• Molecular Programming
• Robotics
• Self-Assembly
• algorithms
• biology
• algorithm analysis and problem complexity

• Department of Computer Science, University of British Columbia, Vancouver, Canada

  Anne Condon

• Leiden Institute of Advanced Computer Science (LIACS), Leiden University, Leiden, The Netherlands

  Grzegorz Rozenberg

Policies and ethics