Computing with Bio-Molecules: Theory and Experiments
Search in google:
Molecular computing (especially DNA computing) means using bio-molecules as a support for computations and devising computers. This is in contrast to the current opposite direction of research, the classic one, where computers are used in studying molecules (especially DNA), a field now commonly termed the science of bioinformatics. Using DNA as a "chip" or support for computation is not a new idea, and has been speculated upon since the 1950's. Adleman's 1994 report on solving the Hamiltonian Path Problem in a graph, using only biochemical laboratory techniques, was the revolutionary turning point in making possible the construction of large computers of huge parallelism, which are able to incorporate the features of matching, splicing (cross-over), insertion, deletions, etc., of data structures (strings and languages) - all features typical of the living DNA molecule. DNA computing is a domain of clear interdisciplinary work, and is definitely a field in rising expansion. Still, a lot of work has to be done, both from a mathematical and a biochemical point of view. This book brings together over 20 international contributions on the theoretical and experimental works of scientists in search of the bio-computer. The style of the contributions are that of research papers and surveys. Being one of the first volumes of its type in this new exciting field, this book will be of equal interest to computer scientists, mathematicians, and biochemists alike.
PrefaceLanguage at the Crossroad of Computation and Biology1String Rewriting and Metabolism: A Logical Perspective36A Molecular Abstract Machine61Hamiltonian Paths and Double Stranded DNA80Graph Structures in DNA Computing93Circuit Evaluation: Thoughts on a Killer Application in DNA Computing111Boolean Transitive Closure in DNA127Thermodynamic Constraints on DNA-based Computing138A Note on DNA Representation of Binary Strings153Silicon or Molecules? What's the Best for Splicing?158Bidirectional Sticker Systems and Representations of RE Languages by Copy Languages182Universality Results for Finite H Systems and for Watson-Crick Finite Automata200Simulating Turing Machines by Extended mH Systems221Controlled and Distributed H Systems of a Small Diameter239The Power of H Systems: Does Representation Matter?255Splicing Languages Generated with One Sided Context269Self Cross-over Systems283Some Results on Array Splicing295Splicing on Routes and Recognizability314Algebraic Properties of DNA Operations327Modeling DNA Recombinant Behavior with Fixed-Point Equations340
