DIMACS Series in
Discrete Mathematics and Theoretical Computer Science

VOLUME Forty Four
TITLE: "DNA Based Computers II"
EDITORS: Laura Landweber and Eric Baum

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.


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 
    L. M. Adleman, P. W. K. Rothemund, S. Roweis, and 
    E. Winfree							 31

Massively parallel DNA computation: Expansion of symbolic 
    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 
    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 Index of Volumes
DIMACS Homepage
Contacting the Center
Document last modified on October 28, 1998.