DNA Computing: 8th International Workshop on DNA-Based Computers, DNA8 Sapporo, Japan, June 10–13, 2002 Revised Papers

Phiset Sa-Ardyen, Nataša Jonoska, Nadrian C. Seeman (auth.), Masami Hagiya, Azuma Ohuchi (eds.)9783540005315, 3-540-00531-5

Biomolecular computing has emerged as an interdisciplinary ?eld that draws – gether chemistry, computer science, mathematics, molecular biology, and physics. Our knowledge on DNA nanotechnology and biomolecular computing increases exponentially with every passing year. The international meeting on DNA Based Computers has been a forum where scientists with di?erent backgrounds, yet sharing a common interest in biomolecular computing, meet and present their latest results. Continuing this tradition, the 8th International Meeting on DNA Based Computers (DNA8) focuses on the current theoretical and experimental results with the greatest impact. Papers and poster presentations were sought in all areas that relate to b- molecular computing, including (but not restricted to): algorithms and appli- tions, analysis of laboratory techniques/theoretical models, computational p- cesses in vitro and in vivo, DNA-computing-based biotechnological applications, DNA devices, error evaluation and correction, in vitro evolution, models of biomolecular computing (using DNA and/or other molecules), molecular – sign, nucleic acid chemistry, and simulation tools. Papers and posters with new experimental results were particularly encouraged. Authors who wished their work to be considered for either oral or poster presentation were asked to select from one of two submission “tracks”: – Track A – Full Paper – Track B – One-Page Abstract For authors with late-breaking results, or who were submitting their manuscript to a scienti?c journal, a one-page abstract, rather than a full paper, could be submitted in Track B. Authors could (optionally) include a preprint of their full paper, for consideration only by the program committee.

---

Table of contents :
Self-assembling DNA Graphs….Pages 1-9
DNA Nanotubes: Construction and Characterization of Filaments Composed of TX-tile Lattice….Pages 10-21
The Design of Autonomous DNA Nanomechanical Devices: Walking and Rolling DNA….Pages 22-37
Cascading Whiplash PCR with a Nicking Enzyme….Pages 38-46
A PNA-mediated Whiplash PCR-based Program for In Vitro Protein Evolution….Pages 47-60
Engineering Signal Processing in Cells: Towards Molecular Concentration Band Detection….Pages 61-72
Temperature Gradient-Based DNA Computing for Graph Problems with Weighted Edges….Pages 73-84
Shortening the Computational Time of the Fluorescent DNA Computing….Pages 85-94
How Efficiently Can Room at the Bottom Be Traded Away for Speed at the Top?….Pages 95-111
Hierarchical DNA Memory Based on Nested PCR….Pages 112-123
Binary Arithmetic for DNA Computers….Pages 124-132
Implementation of a Random Walk Method for Solving 3-SAT on Circular DNA Molecules….Pages 133-142
Version Space Learning with DNA Molecules….Pages 143-155
DNA Implementation of Theorem Proving with Resolution Refutation in Propositional Logic….Pages 156-167
Universal Biochip Readout of Directed Hamiltonian Path Problems….Pages 168-181
Algorithms for Testing That Sets of DNA Words Concatenate without Secondary Structure….Pages 182-195
A PCR-based Protocol for In Vitro Selection of Non-crosshybridizing Oligonucleotides….Pages 196-204
On Template Method for DNA Sequence Design….Pages 205-214
From RNA Secondary Structure to Coding Theory: A Combinatorial Approach….Pages 215-228
Stochastic Local Search Algorithms for DNA Word Design….Pages 229-241
NACST/Seq: A Sequence Design System with Multiobjective Optimization….Pages 242-251
A Software Tool for Generating Non-crosshybridizing Libraries of DNA Oligonucleotides….Pages 252-261
Splicing Systems: Regularity and Below ….Pages 262-268
On the Computational Power of Insertion-Deletion Systems….Pages 269-280
Unexpected Universality Results for Three Classes of P Systems with Symport/Antiport….Pages 281-290
Conformons-P Systems….Pages 291-301
Parallel Rewriting P Systems with Deadlock….Pages 302-314
A DNA-based Computational Model Using a Specific Type of Restriction Enzyme….Pages 315-325
Time-Varying Distributed H Systems of Degree 2 Can Carry Out Parallel Computations….Pages 326-336