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.
The fledgling field of DNA computers began in 1994 when Leonard Adleman surprised the scientific community by using DNA molecules, protein enzymes, and chemicals to solve an instance of a hard computational problem. This volume presents results from the second annual meeting on DNA computers held at Princeton only one and one-half years after Adleman's discovery. By drawing on the analogy between DNA computing and cutting-edge fields of biology (such as directed evolution), this volume highlights some of the exciting progress in the field and builds a strong foundation for the theory of molecular computation.
DNA computing is a radically different approach to computing that brings together computer science and molecular biology in a way that is wholly distinct from other disciplines. This book outlines important advances in the field and offers comprehensive discussion on potential pitfalls and the general practicality of building DNA based computers.
Foreword vii Introduction ix Acknowledgements xi A sticker based model for DNA computation S. Roweis, E. Winfree, R. Burgoyne, N. V. Chelyapov, M. F. Goodman, P. W. K. Rothemund, and L. M. Adleman 1 On applying molecular computation to the data encryption standard L. M. Adleman, P. W. K. Rothemund, S. Roweis, and E. Winfree 31 Massively parallel DNA computation: Expansion of symbolic determinants T. H. Leete, M. D. Schwartz, R. M. Williams, D. H. Wood, J. S. Salem, and H. Rubin 45 Universal DNA computing models based on the splicing operation G. Paun 59 Running dynamic programming algorithms on a DNA computer E. B. Baum and D. Boneh 77 A molecular computation of the road coloring problem N. Jonoska and S. A. Karl 87 DNA based molecular computation: Template-template interactions in PCR P. D. Kaplan, G. Cecchi, and A. Libchaber 97 Use of a horizontal chain reaction for DNA-based addition F. Guarnieri and C. Bancroft 105 Computation with DNA: Matrix multiplication J. S. Olive 113 A surface-based approach to DNA computation Q. Liu, Z. Guo, Z. Fei, A. E. Condon, R. M. Corn, M. G. Lagally, and L. M. Smith 123 Mesoscopic computer engineering: Automating DNA-based molecular computing via traditional practices of parallel computer architecture design J.-T. Amenyo 133 Error-resistant implementation of DNA computations M. Amos, A. Gibbons, and D. Hodgson 151 Making DNA computers error resistant D. Boneh, C. Dunworth, R. J. Lipton, and J. Sgall 163 Active transport in biological computing S. A. Kurtz, S. R. Mahaney, J. S. Royer, and J. Simon 171 RNA based computing: Some examples from RNA catalysis and RNA editing L. F. Landweber 181 Universal computation via self-assembly of DNA: Some theory and experiments E. Winfree, X. Yang, and N. C. Seeman 191 The perils of polynucleotides: The experimental gap between the design and assembly of unusual DNA structures N. C. Seeman, H. Wang, B. Liu, J. Qi, X. Li, X. Yang, F. Liu, W. Sun, Z. Shen, R. Sha, C. Mao, Y. Wang, S. Zhang, T.-J. Fu, S. Du, J. E. Mueller, Y. Zhang, and J. Chen 215 DNA sequences useful for computation E. B. Baum 235 A restricted genetic alphabet for DNA computing K. U. Mir 243 Good encodings for DNA-based solutions to combinatorial problems R. Deaton, R. C. Murphy, M. Garzon, D. R. Franceschetti, and S. E. Stevens, Jr. 247 DNA computations can have global memory R. J. Lipton 259 Exascale computer algebra problems interconnect with molecular reactions and complexity theory R. M. Williams and D. H. Wood 267