Discrete Mathematics and Theoretical Computer Science

TITLE: "DNA Based Computers V"

EDITORS: Erik Winfree and David K. Gifford

To order through AMS contact the AMS Customer Services Department, P.O. Box 6248, Providence, Rhode Island 02940-6248 USA. For Visa, Mastercard, Discover, and American Express orders call 1-800-321-4AMS.

You may also visit the
AMS Bookstore and
order directly from there.
DIMACS ** does not** distribute or sell these books.

This proceedings volume presents the talks from the Fifth Annual Meeting on DNA Based Computers held at MIT. The conference brought together researchers and theorists from many disciplines who shared research results in biomolecular computation.

Two styles of DNA computing were explored at the conference: 1) DNA computing based on combinatorial search, where randomly created DNA strands are used to encode potential solutions to a problem, and constraints induced by the problem are used to identify DNA strands that are solution witnesses; and 2) DNA computing based on finite-state machines, where the state of a computation is encoded in DNA, which controls the biochemical steps that advance the DNA-based machine from state to state.

Featured articles include discussions on the formula satisfiability problem, self-assembly and nanomachines, simulation and design of molecular systems, and new theoretical approaches.

Foreword vii Introduction ix When the Knight falls: On constructing an RNA computer D. Faulhammer, A. R. Cukras, R. J. Lipton, and L. F. Landweber 1 Solution to 3-SAT by breadth first search H. Yoshida and A. Suyama 9In vitroselection for a OneMax DNA evolutionary computation D. H. Wood, J. Chen, E. Antipov, B. Lemieux, and W. Cedeno 23 Liposome mediated biomolecular computation B. Bloom and C. Bancroft 39 Error correction in DNA computing: Misclassification and strand loss K. Chen and E. Winfree 49 DNA analog vector algebra and physical constraints on large-scale DNA-based neural network computation A. P. Mills, Jr., B. Yurke, and P. M. Platzman 65 On combinatorial DNA word design A. Marathe, A. E. Condon, and R. M. Corn 75 Soft molecular computing M. Garzon, R. J. Deaton, and J. A. Rose 91 A study on the hybridization process in DNA computing M. Yamamoto, J. Yamashita, T. Shiba, T. Hirayama, S. Takiya, K. Suzuki, M. Munekata, and A. Ohuchi 101 Simulating biological reactions: A modular approach A. J. Hartemink, T. S. Mikkelsen, and D. K. Gifford 111 Experimental progress in computation by self-assembly of DNA tilings T. H. LaBean, E. Winfree, and J. H. Reif 123 2D DNA self-assembly for satisfiability M. G. Lagoudakis and T. H. LaBean 141 YAC: Yet another computation model of self-assembly T. Yokomori 155 DNA hybridization catalysts and molecular tweezers A. J. Turberfield, B. Yurke, and A. P. Mills, Jr. 171 Designing and selecting components for nucleic acid computers M. P. Robertson, J. Hesselberth, J. C. Cox, and A. D. Ellington 183 Forbidding and enforcing A. Ehrenfeucht, H. J. Hoogeboom, G. Rozenberg, and N. van Vugt 195 Computational power of gene rearrangement L. Kari and L. F. Landweber 207 Membrane computing based on splicing G. Paun and T. Yokomori 217 DNA-based cryptography A. Gehani, T. H. LaBean, and J. H. Reif 233

Index of Volumes

DIMACS Homepage

Contacting the Center

Document last modified on January 5, 2001.