| | DIMACS: Series in Discrete Mathematics and Theoretical Computer Science
1999; 275 pp; hardcover
ISBN-13: 978-0-8218-0756-9 List Price: US$75
Member Price: US$60
Order Code: DIMACS/44
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.
Co-published with the Center for Discrete Mathematics and Theoretical Computer Science beginning with Volume 8. Volumes 1-7 were co-published with the Association for Computer Machinery (ACM).
Graduate students and research and applied mathematicians working in biology and other natural sciences; molecular biologists, computer scientists; chemical and electrical engineers.
Table of Contents
- S. Roweis, E. Winfree, R. Burgoyne, N. V. Chelyapov, M. F. Goodman, P. W. K. Rothemund, and L. M. Adleman -- A sticker based model for DNA computation
- L. M. Adleman, P. W. K. Rothemund, S. Roweis, and E. Winfree -- On applying molecular computation to the data encryption standard
- T. H. Leete, M. D. Schwartz, R. M. Williams, D. H. Wood, J. S. Salem, and H. Rubin -- Massively parallel DNA computation: Expansion of symbolic determinants
- G. Păun -- Universal DNA computing models based on the splicing operation
- E. B. Baum and D. Boneh -- Running dynamic programming algorithms on a DNA computer
- N. Jonoska and S. A. Karl -- A molecular computation of the road coloring problem
- P. D. Kaplan, G. Cecchi, and A. Libchaber -- DNA based molecular computation: Template-template interactions in PCR
- F. Guarnieri and C. Bancroft -- Use of a horizontal chain reaction for DNA-based addition
- J. S. Oliver -- Computation with DNA: Matrix multiplication
- Q. Liu, Z. Guo, Z. Fei, A. E. Condon, R. M. Corn, M. G. Lagally, and L. M. Smith -- A surface-based approach to DNA computation
- J.-T. Amenyo -- Mesoscopic computer engineering: Automating DNA-based molecular computing via traditional practices of parallel computer architecture design
- M. Amos, A. Gibbons, and D. Hodgson -- Error-resistant implementation of DNA computations
- D. Boneh, C. Dunworth, R. J. Lipton, and J. Sgall -- Making DNA computers error resistant
- S. A. Kurtz, S. R. Mahaney, J. S. Royer, and J. Simon -- Active transport in biological computing
- L. F. Landweber -- RNA based computing: Some examples from RNA catalysis and RNA editing
- E. Winfree, X. Yang, and N. C. Seeman -- Universal computation via self-assembly of DNA: Some theory and experiments
- 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 -- The perils of polynucleotides: The experimental gap between the design and assembly of unusual DNA structures
- E. B. Baum -- DNA sequences useful for computation
- K. U. Mir -- A restricted genetic alphabet for DNA computing
- R. Deaton, R. C. Murphy, M. Garzon, D. R. Franceschetti, and S. E. Stevens, Jr. -- Good encodings for DNA-based solutions to combinatorial problems
- R. J. Lipton -- DNA computations can have global memory
- R. M. Williams and D. H. Wood -- Exascale computer algebra problems interconnect with molecular reactions and complexity theory