Theoretical and Experimental DNA Computation

This book provides a broad overview of the entire field of DNA computation, tracing its history and development. It contains detailed descriptions of all major theoretical models and experimental results to date, which are lacking in existing texts, and d

  • PDF / 1,756,125 Bytes
  • 180 Pages / 439.37 x 666.142 pts Page_size
  • 40 Downloads / 307 Views

DOWNLOAD

REPORT


Advisory Board: S. Amari G. Brassard K.A. De Jong C.C.A.M. Gielen T. Head L. Kari L. Landweber T. Martinetz ° Z. Michalewicz M.C. Mozer E. Oja G. Paun J. Reif H. Rubin A. Salomaa M. Schoenauer H.-P. Schwefel C. Torras D. Whitley E. Winfree J.M. Zurada

Martyn Amos

Theoretical and Experimental DNA Computation With 78 Figures and 17 Tables

123

Martyn Amos Department of Computer Science School of Engineering, Computer Science and Mathematics University of Exeter Harrison Building Exeter EX4 4QF United Kingdom [email protected] http://www.dcs.ex.ac.uk/~mramos Series Editors G. Rozenberg (Managing Editor) [email protected] Th. Bäck, J.N. Kok, H.P. Spaink Leiden Center for Natural Computing Leiden University Niels Bohrweg 1 2333 CA Leiden, The Netherlands A.E. Eiben Vrije Universiteit Amsterdam The Netherlands Library of Congress Control Number: 2004116588

ACM Computing Classification (1998): F.1–2, G.2.1–2, J.3 ISBN-10 3-540-65773-8 Springer Berlin Heidelberg New York ISBN-13 978-3-540-65773-6 Springer Berlin Heidelberg New York This work is subject to copyright. All rights are reserved, whether the whole or part of the material is concerned, specifically the rights of translation, reprinting, reuse of illustrations, recitation, broadcasting, reproduction on microfilm or in any other way, and storage in data banks. Duplication of this publication or parts thereof is permitted only under the provisions of the German Copyright Law of September 9, 1965, in its current version, and permission for use must always be obtained from Springer. Violations are liable for prosecution under the German Copyright Law. Springer is a part of Springer Science+Business Media springeronline.com © Springer-Verlag Berlin Heidelberg 2005 Printed in Germany The use of general descriptive names, registered names, trademarks, etc. in this publication does not imply, even in the absence of a specific statement, that such names are exempt from the relevant protective laws and regulations and therefore free for general use. Cover Design: KünkelLopka, Werbeagentur, Heidelberg Typesetting: by the Author Production: LE-TEX Jelonek, Schmidt & Vöckler GbR, Leipzig Printed on acid-free paper 45/3142/YL – 5 4 3 2 1 0

This book is dedicated to the memory of Charlton Hall Amos.

Preface

DNA computation has emerged in the last ten years as an exciting new research field at the intersection (and, some would say, frontiers) of computer science, biology, engineering, and mathematics. Although anticipated by Feynman as long ago as the 1950s [59], the notion of performing computations at a molecular level was only realized in 1994, with Adleman’s seminal work [3] on computing with DNA. Since then the field has blossomed rapidly, with significant theoretical and experimental results being reported regularly. Several books [120, 39] have described various aspects of DNA computation, but this is, to the author’s best knowledge