DNA Computing: 10th International Workshop on DNA Computing, DNA10, Milan, Italy, June 7-10, 2004, Revised Selected Papers(Theoretical Computer Science and General Issues)

Biomolecular computing has emerged as an interdisciplinary ?eld that draws - getherchemistry,computerscience,mathematics,molecularbiology,andphysics. Our knowledge of DNA nanotechnology and biomolecular computing increases dramatically with every passing year. The International Meeting on DNA C- puting has been a forum where scientists with di?erent backgrounds, yet sh- ing a common interest in biomolecular computing, meet and present their latest results. Continuing this tradition, the 10th International Meeting on DNA C- puting(DNA10)focusedonthecurrentexperimentalandtheoreticalresultswith the greatest impact. The meeting took place at the University of Milano-Bicocca, Milan, Italy, from June 7 to June 10, 2004, and it was organized by the University of Milano- Bicocca and the Department of Informatics of the University of Milano-Bicocca. Papersandposterpresentationsweresoughtinallareasthatrelatetobiomole- lar computing, including (but not restricted to): demonstrations of biomolecular computing (using DNA and/or other molecules), theoretical models of biomol- ularcomputing,biomolecularalgorithms,computationalprocessesinvitroandin vivo, analysis and theoretical models of laboratory techniques, biotechnological and other applications of DNA computing, DNA nanostructures, DNA devices such as DNA motors, DNA error evaluation and correction, in vitro evolution, molecular design, self-assembled systems, nucleic acid chemistry, and simulation tools. Authors were asked to choose between two di?erent tracks: Track A - Full paper, for authors who wished to submit a full paper for presentation at DNA10 (oral or poster), and publication in the conference p- ceedings. Track B - One-page abstract, for authors submitting experimental results, and who planned to submit their manuscript to a scienti?c journal, rather than publish it in the conference proceedings.

Table of Contents:
Computing by Observing Bio-systems: The Case of Sticker Systems.- DNA-Based Computation Times.- Computing Beyond the Turing Limit Using the H Systems.- Biomolecular Implementation of Computing Devices with Unbounded Memory.- Characterization of Non-crosshybridizing DNA Oligonucleotides Manufactured In Vitro.- Error Free Self-assembly Using Error Prone Tiles.- On the Computational Complexity of P Automata.- A Weighted Insertion-Deletion Stacked Pair Thermodynamic Metric for DNA Codes.- DNA Extraction by XPCR.- A Method of Error Suppression for Self-assembling DNA Tiles.- Using Automated Reasoning Systems on Molecular Computing.- Parallelism in Gene Assembly.- Splicing Systems for Universal Turing Machines.- Application of Mismatch Detection Methods in DNA Computing.- Bond-Free Languages: Formalizations, Maximality and Construction Methods.- Preventing Undesirable Bonds Between DNA Codewords.- Testing Structure Freeness of Regular Sets of Biomolecular Sequences.- Minimum Basin Algorithm: An Effective Analysis Technique for DNA Energy Landscapes.- Efficient Initial Pool Generation for Weighted Graph Problems Using Parallel Overlap Assembly.- Partial Words for DNA Coding.- Accepting Hybrid Networks of Evolutionary Processors.- Building the Components for a Biomolecular Computer.- Methods for Manipulating DNA Molecules in a Micrometer Scale Using Optical Techniques.- From Cells to Computers: Membrane Computing – A Quick Overview.- The Capacity of DNA for Information Encoding.- Compact Error-Resilient Computational DNA Tiling Assemblies.- Toward “Wet” Implementation of Genetic Algorithm for Protein Engineering.- Programmable Control of Nucleation for Algorithmic Self-assembly.- DNA Hybridization Catalysts and Catalyst Circuits.- Complexity of Self-assembled Shapes.-Aqueous Computing with DNA Hairpin-Based RAM.- A Programmable Molecular Computer in Microreactors.- Combinatorial Aspects of Minimal DNA Expressions.- A Design for Cellular Evolutionary Computation by Using Bacteria.- An Inexpensive LED-Based Fluorometer Used to Study a Hairpin-Based DNA Nanomachine.- Designs of Autonomous Unidirectional Walking DNA Devices.- Design of an Autonomous DNA Nanomechanical Device Capable of Universal Computation and Universal Translational Motion.- A Clocked DNA-Based Replicator.- A Bayesian Algorithm for In Vitro Molecular Evolution of Pattern Classifiers.