DIMACS Series in
Discrete Mathematics and Theoretical Computer Science

VOLUME Forty Eight
TITLE: "DNA Based Computers III"
EDITORS: Harvey Rubin and David Harlan Wood.

Ordering Information

This volume may be obtained from the AMS or through bookstores in your area.

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.

PREFACE

This volume presents the proceedings from the third DIMACS workshop on "DNA Based Computers" held at the University of Pennsylvania (Philadelphia). The workshop was part of the Special Year on Molecular Biology and the Special Year on DNA Computing. The focus of this proceedings volume is on the multidisciplinary nature of the workshop with emphasis on the interaction between biology and biochemistry on one hand and computer science and mathematics on the other.

TABLE OF CONTENTS


Foreword						    ix

Preface							    xi

Physical chemistry of nucleic acid hybridization
    J. G. Wetmur					     1

Thermodynamic simulation of deoxyoligonucleotide 
  hybridization for DNA computation
    A. J. Hartemink and D. K. Gifford			    25


The efficiency of sequence-specific separation of DNA 
  mixtures for biological computing
    J. Khodor and D. K. Gifford				    39

A new DNA separation technique with a low error rate
    J. Chen and D. H. Wood				    47

Towards parallel evaluation and learning of 
  Boolean $\mu$-formulas with molecules
    M. Hagiya, M. Arita, D. Kiga, K. Sakamoto, 
      and S. Yokoyama					    57

Wet splicing systems
    E. Laun and K. J. Reddy				    73

Parallel operations in DNA-based computation
    F. Guarnieri, M. Orlian, and C. Bancroft                85

Protein folding, spin glass and computational complexity
    A. S. Fraenkel					   101

Creating 3-dimensional graph structures with DNA
    N. Jonoska, S. A. Karl, and M. Saito		   123

DNA implementation of nondeterminism
    Y. Gao, M. Garzon, R. C. Murphy, J. A. Rose, 
      R. Deaton, D. R. Franceschetti, 
      and S. E. Stevens, Jr.				   137

Arithmetic and logic operations with DNA
    V. Gupta, S. Parthasarathy, and M. J. Zaki	           149

DNA2DNA computations: A potential "killer app?"
    L. F. Landweber, R. J. Lipton, and M. O. Rabin         161

Strategies for DNA computing
    A. D. Ellington, M. P. Robertson, K. D. James, 
      and J. C. Cox					   173

A surface-based DNA algorithm for minimal set cover
    T. L. Eng and B. M. Serridge                           185

Solid phase DNA solution to the Hamiltonian path problem
    N. Morimoto, M. Arita, and A. Suyama                   193

On molecular approximation algorithms for NP 
  optimization problem
    B. Fu and R. Beigel					   207

Local parallel biomolecular computation
    J. H. Reif						   217

DNA-based parallel computation by "counting"
    M. Ogihara and A. Ray				   255

Parallel computation on a DNA substrate
    A. J. Blumberg					   265

Design for a DNA conformational processor
    M. Conrad and K.-P. Zauner				   281

Linear DNA self-assembly with hairpins generates 
  linear context-free grammars
    T. L. Eng						   289

Watson-Crick finite automata
    R. Freund, Gh. Paun, G. Rozenberg, and A. Salomaa	   297

At the crossroads of DNA computing and formal languages: 
  Characterizing recursively enumerable languages 
  using insertion-deletion systems
    L. Kari, G. Paun, G. Thierrin, and S. Yu		   329

DNA-EC: A model of DNA-computing based on equality 
  checking
    T. Yokomori and S. Kobayashi			   347

Splicing on tree-like structures
    Y. Sakakibara and C. Ferretti			   361
Index Index of Volumes
DIMACS Homepage
Contacting the Center
Document last modified on October 28, 1998.