Discrete Mathematics and Theoretical Computer Science

TITLE: "DNA Based Computers III"

EDITORS: Harvey Rubin and David Harlan Wood.

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 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.

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 DNA^{2}DNA 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 of Volumes

DIMACS Homepage

Contacting the Center

Document last modified on October 28, 1998.