DNA Computing: 8th International Workshop on DNA Based Computers, DNA8, Sapporo, Japan, June 10-13, 2002, Revised PapersMasami Hagiya, Azuma Ohuchi 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. |
Contents
Selfassembling DNA Graphs | 1 |
Construction and Characterization of Filaments Composed of TXtile Lattice | 10 |
Walking and Rolling DNA | 22 |
Cascading Whiplash PCR with a Nicking Enzyme | 38 |
A PNAmediated Whiplash PCRbased Program for In Vitro Protein Evolution | 47 |
Towards Molecular Concentration Band Detection | 61 |
Temperature GradientBased DNA Computing for Graph Problems with Weighted Edges | 73 |
Shortening the Computational Time of the Fluorescent DNA Computing | 85 |
A PCRbased Protocol for In Vitro Selection of Noncrosshybridizing Oligonucleotides | 196 |
On Template Method for DNA Sequence Design | 205 |
A Combinatorial Approach | 215 |
Stochastic Local Search Algorithms for DNA Word Design | 229 |
A Sequence Design System with Multiobjective Optimization | 242 |
A Software Tool for Generating Noncrosshybridizing Libraries of DNA Oligonucleotides | 252 |
Regularity and Below | 262 |
On the Computational Power of InsertionDeletion Systems | 269 |
How Efficiently Can Room at the Bottom Be Traded Away for Speed at the Top? Extended Abstract | 95 |
Hierarchical DNA Memory Based on Nested PCR | 112 |
Binary Arithmetic for DNA Computers | 124 |
Implementation of a Random Walk Method for Solving 3SAT on Circular DNA Molecules | 133 |
Version Space Learning with DNA Molecules | 143 |
DNA Implementation of Theorem Proving with Resolution Refutation in Propositional Logic | 156 |
Universal Biochip Readout of Directed Hamiltonian Path Problems | 168 |
Algorithms for Testing That Sets of DNA Words Concatenate without Secondary Structure | 182 |
Unexpected Universality Results for Three Classes of P Systems with SymportAntiport | 281 |
ConformonsP Systems | 291 |
Parallel Rewriting P Systems with Deadlock | 302 |
A DNAbased Computational Model Using a Specific Type of Restriction Enzyme | 315 |
TimeVarying Distributed H Systems of Degree 2 Can Carry Out Parallel Computations | 326 |
| 337 | |
Other editions - View all
DNA Computing: 8th International Workshop on DNA Based Computers ..., Volume 8 Masami Hagiya,Azuma Ohuchi No preview available - 2003 |
Common terms and phrases
adjacency matrix algorithm alphabet annealing antiport applied barcode base pairs binary biochip biomolecular clause combinatorial complementary Computer Science configuration conformons constraints construct contains corresponding covering code deadlock defined denaturation denoted DIMACS DNA Based Computers DNA computing DNA molecules DNA sequences DNA strands DNA-based DNA8 duplex edge efficient encoding experimental Figure finite fluorescent free energy fuel strand GC content genetic graph Hagiya hairpin Hamming distance hybridization implementation initial input integer k-SAT labeled length ligation LNCS loop membrane method mismatches Molecular computation multiset NACST/Seq non-crosshybridizing nonterminal NPMM oligonucleotides operation optimal output parallel performed polymerase primer problem protein PWPCR Q-dot random reaction readout recursively enumerable languages restriction enzyme RNA secondary structure rules satisfy secondary structure Section Seeman simulation solution splicing systems Springer-Verlag ssDNA step string symport template Theorem thermodynamic tube variable version space vertex Watson-Crick word sets WPCR