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
Index of Volumes
DIMACS Homepage