VOLUME Fifty Four
TITLE: "DNA Based Computers V"
EDITORS: Erik Winfree and David K. Gifford

Ordering Information

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.

• 1. Preface
• 2. Table of Contents

PREFACE

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.

TABLE OF CONTENTS

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                                  9 

In vitro selection 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