Theoretical and Experimental DNA Computation

Author: Martyn Amos

Publisher: Springer Berlin Heidelberg

Book Series : Natural Computing Series

Part of: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

About this book

DNA computation has emerged in the last ten years as an exciting new - search ?eld at the intersection (and, some would say, frontiers) of computer science,biology,engineering,andmathematics.AlthoughanticipatedbyFe- man 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 ?eld has blossomed rapidly, with signi?cant theoretical and experimental results being reported regularly. Several books [120, 39] have described various aspects of DNA compu- tion, but this is, to the author’s best knowledge, the ?rst to bring together descriptions of both theoreticaland experimentalresults.The targetaudience is intentionally broad, including students as well as experienced researchers. We expect that users of the book will have some background in either c- puter science, mathematics, engineering, or the life sciences. The intention is that this book be used as a tutorial guide for newcomers to the ?eld as well as a reference text for people already working in this fascinating area. To this end, we include two self-contained tutorial chapters (1 and 2), which convey only those aspects of computer science and biology that are required to understand the subsequent material.

Frontmatter

Introduction

1. DNA: The Molecule of Life

1.5 Summary

We described here the basic structure of DNA and the methods by which it may be manipulated in the laboratory. These techniques owe their origin to, and are being constantly improved by, the wide interests of molecular biologists working in modern areas such as the Human Genome project and genetic engineering. In Chap. 5 we show how these techniques allow us to implement a computation. Although other molecules (such as proteins) may be used as a computational substrate in the future, the benefit of using DNA is that this wide range of manipulation techniques is already available for use.

2. Theoretical Computer Science: A Primer

2.8 Summary

In this chapter we provided an introduction to the theory of computer science. We described the fundamental “building blocks” of computers, logic gates, and showed how they may be pieced together to perform computations. We then considered the nature of computation itself, and introduced the concept of an algorithm. This motivated the study of machine models, or models of computation. We introduced several such models (the finite-state automaton, the Turing machine, and the Random Access Machine), and described their features, strengths, and weaknesses. We then considered the implementation of algorithms within these models, introducing the organization of information into data structures. We examined a simple data structure, the array, before considering a more complex structure, the graph. We then highlighted the fact that different algorithms require different resources, introducing the key concept of computational complexity. We described the importance of this idea, and showed how to calculate the complexity of algorithms. This then motivated a discussion of how to choose an algorithm for a particular problem. We concluded with a description of complexity classes, and introduced the NP-complete problems, for which no fast algorithms yet exist.

3. Models of Molecular Computation

3.6 Summary

In this chapter we categorized models of molecular computation into one of four types (filtering, splicing, constructive, and membrane). Abstract models of each type were described, as well as a selection of algorithms within them. We payed particular attention to the filtering algorithms, especially those of Adleman, Lipton, and Amos et al.

4. Complexity Issues

4.13 Summary

In this chapter we have emphasized the rôle that complexity considerations are likely to play in the identification of “killer applications” for DNA computation. We have examined how time complexities have been estimated within the literature. We have shown that these are often likely to be inadequate from a realistic point of view. In particular, many authors implicitly assume that arbitrarily large numbers of laboratory assistants or robotic arms are available for the mechanical handling of tubes of DNA. This has often led to serious underestimates of the resources required to complete a computation.

We have proposed a so-called strong model of DNA computation, which we believe allows realistic assessment of the time complexities of algorithms within it. This model, if the splice operation is trivially included, not only provides realistic estimates of time complexities, but is also Turing-complete. We have also demonstrated how existing models of computation (Boolean circuits and the P-RAM) may be effectively simulated in DNA.

We believe that success in the search for “killer applications” is the only means by which there will be sustained practical interest in DNA computation. Success is only a likely outcome if DNA computations can be described that will require computational resources of similar magnitude to those required by conventional solutions. If, for example, we were to establish polylogarithmic time computations using only a polynomial volume of DNA, then this would be one scenario in which “killer applications” might well ensue. In this case, we might imagine that the vast potential for parallelisation may finally be effectively harnessed.

5. Physical Implementations

5.10 Summary

In this chapter we have described in depth the experimental realization of some of the abstract models of DNA computation described in Chap. 2. We described Adleman's seminal experiment, as well as a potential implementation of the parallel filtering model, which laid the foundations for important later work on destructive algorithms. We also described some key contributions to the laboratory implementation of computations, and highlighted some late-breaking results.

6. Cellular Computing

6.6 Summary

In this chapter we have introduced the notion of computing with and inside living cells and reviewed several models for the assembly of genes in ciliates. Although the fundamental molecular mechanisms underlying the operations within these models are still not well-understood, they do suggest possible areas of experimental enquiry. Looking further ahead, it may well be that in the future these mechanisms may even be exploited by using ciliates as prototype cellular computers. This engineering process has already begun, and we have cited several successful examples of the genetic modification of organisms for computational purposes.

Backmatter

Title: Theoretical and Experimental DNA Computation
Author: Martyn Amos
Publisher: Springer Berlin Heidelberg
Electronic ISBN: 978-3-540-28131-3
Print ISBN: 978-3-540-65773-6
DOI: https://doi.org/10.1007/3-540-28131-2

Springer Professional