DIMACS Series in
Discrete Mathematics and Theoretical Computer Science

VOLUME Twenty Seven
TITLE: "DNA Based Computers"
EDITORS: Richard J. Lipton, Eric B. Baum
Published by the American Mathematical Society


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.



PREFACE


This volume constitutes the proceedings of the conference held April 4, 1995, at Princeton University. The subject of the meeting was the new area of DNA based computing.

The conference was sponsored by DIMACS and NSF. We thank them for their generous support.

The area of DNA based computing is the study of using DNA strands as individual computers. It was started by Len Adleman's initial paper in Science in November 1994.


TABLE OF CONTENTS

Foreward vii
Introduction ix
On constructing a molecular computer

    Leonard M. Adleman

1
A DNA associative memory potentially larger than the brain

    Eric B. Baum

23
A universal molecular computer

    Donald Beaver

29
Breaking DES using a molecular computer

    Dan Boneh, Christopher Dunworth, Richard J. Lipton

37
Speeding up computations via molecular biology

    Richard J. Lipton

67
A DNA and restriction enzyme implementation of Turing machines

    Paul Wilhelm Karl Rothemund

75
DNA computers in vitro and vivo

    Warren D. Smith

121
Complexity of restricted and unrestricted models of molecular computation

    Erik Winfree

187
On the computational power of DNA annealing and ligation

    Erik Winfree

199


Index Index of Volumes
DIMACS Homepage
Contacting the Center
Document last modified on October 28, 1998.