DNA Computation Ph.D thesis available

Martyn Amos M.Amos at csc.liv.ac.uk
Thu Sep 18 22:59:46 EST 1997

Dear colleagues,

The following Ph.D thesis is now available:

DNA Computation
Martyn Amos 


Submitted to the University of Warwick, UK, for the degree of Doctor of
Philosophy. Successully defended on August 6, 1997. 


This is the first ever doctoral thesis in the field of DNA computation.
The field has its roots in the late 1950s, when the Nobel laureate
Richard Feynman first introduced the concept of computing at a molecular level.
Feynman's visionary idea was only realised in 1994, when Leonard
Adleman performed the first ever truly molecular-level computation using
DNA combined with the tools and techniques of molecular biology.
Since Adleman reported the results of his seminal experiment, there has been
a flurry of interest in the idea of using DNA to perform 
computations. The potential benefits of using this particular
molecule are enormous: by harnessing the massive inherent parallelism of
performing concurrent operations on trillions of strands, we may one day
be able to compress the power of today's supercomputer into a single
test tube.

However, if we compare the development of DNA-based computers to that of
their silicon counterparts, it is clear that molecular computers are still
in their infancy. Current work in this area is concerned mainly with
abstract models of computation and simple proof-of-principle experiments.
The goal of this thesis is to present our contribution to the field, placing
it in the context of the existing body of work. Our new results concern a
general model of DNA computation, an error-resistant implementation of the
model, experimental investigation of the implementation and an assessment of
the complexity and viability of DNA computations.
We begin by recounting the historical background to
the search for the structure of DNA. By providing a detailed description of
this molecule and the operations we may perform on it, we lay down the
foundations for subsequent chapters. We then describe the basic models of
DNA computation that have been proposed to date. In particular, we describe
our parallel filtering model, which is the first to provide a
general framework for the elegant expression of algorithms for NP-complete
problems. The implementation of such abstract models is crucial to their
success. Previous experiments that have been carried out suffer from their
reliance on various error-prone laboratory techniques. We show for the first
time how one particular operation, hybridisation extraction, may be replaced
by an error-resistant enzymatic separation technique. We also describe
a novel solution read-out procedure that utilizes cloning, and is sufficiently
general to allow it to be used in any experimental implementation. The results
of preliminary tests of these techniques are then reported. Several
important conclusions are to be drawn from these investigations, and we report
these in the hope that they will provide useful experimental guidance in the
future. The final contribution of this thesis is a rigorous consideration
of the complexity and viability of DNA computations. We argue that existing
analyses of models of DNA computation are flawed and unrealistic. In order
to obtain more realistic measures of the time and space complexity of
DNA computations we describe a new strong model,
and reassess previously described algorithms within it. We review the search
for "killer applications": applications of DNA computing that will establish
the superiority of this paradigm within a certain domain.

We conclude the thesis with a description of several open problems in the field
of DNA computation.

The thesis is available via the WWW from


Thank you,

Martyn Amos
Martyn Amos - martyn at csc.liv.ac.uk ---- Complexity, Theory and Algorithmics 
http://www.csc.liv.ac.uk/~martyn/  ---- Group, Department of Computer Science
http://www.csc.liv.ac.uk/~ctag     ---- University of Liverpool, L69 7ZF, UK
******************** "Carp Diem" -- Fish of the day *************************

More information about the Comp-bio mailing list