Erik's Molecular Computation
Some people who have published on molecular computation
There's been a recent wave of interest in using small molecules, such
as DNA, as the basis for new computing devices. Len Adleman (Science, Nov
11, 1994) sparked things off. A number of people have joined the fray since.
Here's a very non-inclusive list:
- At Caltech, we have myself (see below) and
- At USC we have
Leonard Adleman and his
Laboratory for Molecular Science.
(He also has a draft paper available
at this FTP site.)
(Todd Masco has been
kind enough to net-ify most of Len's
Science article as well as David Gifford's perspectives
essay from the same issue.) Paul
Rothemund, who designed a Turing Machine implementation based on restriction
enzymes, is now working in Len's lab.
- At Princeton, we have Richard
Lipton, and his (ex-)student Dan
Boneh (now at Stanford), who have cleaned up and augmented Adleman's
techniques formally, and demonstrated an application to cryptography. Laura
Landweber is now bringing her experience with in vitro evolution to
bear on DNA computation.
- At NEC Research Insitute,
we have Eric
Baum, who has looked into using DNA for associative memories, and Warren
Smith, who sees all of biology as computation, computation, everywhere.
- Now at the University of Pennsylvania,
but previously jointly at NEC and Rockefeller,
Kaplan has reproduced Adleman's original experiment and created a clean
4-bit library, helping ground the field in reality.
- Now at CMU, we have Don
Beaver, who has a nifty construction for parallel pointer jumping,
implementing the classic time-space tradeoff.
- At NYU, Nadrian
Seeman constructs DNA with novel geometry and topology. It's not computation,
really, but it's damn funky.
- At SUNY Binghamton, we have
Tom Head, who works
on a mathematical model called splicing systems, which provides another
basis for DNA computation. Although splicing systems have a longer history
(since 1987!) than most other approaches, as far as I know they have not
yet led to successful experimental demonstrations. Collaborators include
Elizabeth Laun and Kalluru (K.J.) Reddy.
- John Amenyo has posted a few
thoughts about engineering biocomputers, including his summaries of
the first three DIMACS workshops.
Most everyone above was at the DIMACS
Mini-workshop on DNA-Based Computers, held at Princeton, NJ on April 4,
1995. Articles based on the talks there have been collected into hardbound
proceedings. The 2nd
Annual Workshop on DNA Based Computers was held in June 1996, where
20 papers will be presented. Some other people
with interest in the field:
- At the University of Wisconsin, Madison,
Eric Bach, Anne
Glaser, and Celena Tanguay, have a paper on avoiding exhaustive search
for a few NP-complete problems. Anne Condon also collaborates with Max
G. Lagally, Lloyd
M. Smith and Robert
M. Corn, also at UoW, where they have launched an investigation into
surface-based approaches to DNA computing.
- Russell Deaton
and Max Garzon at the
University of Memphis have done interesting work on designing good DNA
sequences. Max Garzon is teaching a seminar.
- At the University of Delaware, we have David
Wood, who is running a seminar
series on DNA computing, and who is organizing the 3rd meeting on DNA
computing. Also see his paper
from the 2nd meeting, and this lab
blurb. He collaborates with Junghei Chen, an experimentalist.
- At the University of Rochester,
Ogihara has investigated better-than-brute-force-search DNA algorithms
for 3SAT, and also furthered the study of boolean circuit algorithms. With
Animesh Ray, he is actually exploring implementation issues!
Karp (U. of Washington),
(Ecole Normale Superieure de Lyon), and Orli Waarts (Berkeley?) have written
a paper on how to improve error rates in separation-based DNA computation.
- At the University of Chicago,
we have Stuart Kurtz,
who taught me logic. He's made some important observations concerning the
kinetics of Adleman's original experiment, and also has some stimulating
musings on ribosome-based computation.
- Now at the University of Liverpool,
we have Martyn Amos, working
Gibbons and David
Hodgson at the University of Warwick.
Martyn has written an intriguing paper on replacing Separation steps by
purely enzymatic steps. It's all in his PhD
Thesis, even including experimental investigations!
- At the University of Aarhus
we have Brian Mayoh
whose work relates graph grammars and pattern formation to DNA.
- At the University
of Würzburg, we have Diana
Rooß and Klaus Wagner, who have examined the paradigm of Adleman
and Lipton from a theoretical complexity class point of view.
- At Duke, John
Reif has written a paper on models of molecular computation for simulating
PRAM. More recently, he has shown how many computations can be performed
efficiently by self-assembly. I understand he and his collaborators are
now getting involved in actual experiments.
- At The University of Western Ontario,
we have Lila Kari, who
has worked considerably on the splicing system approach. There's a nice
reference page for her class CS
881 maintained by J. Blustein.
- Tom Schneider has
been thinking about the information content of molecules for a long time...
(He has a page
for molecular computation too.)
As I said, this list is non-inclusive... a few more authors & papers
are listed in the 20 papers presented at the
Workshop on DNA Based Computers. Ray Dassen also has a bibliography
online (also in a searchable
The 3rd Annual Workshop on
DNA Based Computers was held at the University of Pennsylvania in June,
1997. A few highlights from people not previously mentioned...
- Working with David Gifford at MIT, Julia
Khodor and Alexander
Harteminkvid have looked into sequence-specific separation, and hybridization
of DNA within the PCR reaction, exploring the intriguing possibilities
for computation therein.
- An impressive group
from several universities in Japan presented some very exciting theoretical
and experimental results. Takashi
Yokomori and colleagues have several theoretical models of computation
that they are beginning to experiment with in the lab. Masami
Hagiya, Shigeyuki Yokoyama,
and colleagues are developing a "one-pot" system that computes
using an aborted form of PCR. Akira Suyama and colleagues are developing
a solid-support system for DNA computing operations, and also have an impressive
sequence-specific separation technology. A running theme throughout many
of these projects is the graduate student Masanori
- Michael Conrad leads a Biocomputing
group at Wayne State University. He and Klaus-Peter Zauner suggest
using DNA physical conformation.
works on in-vitro selection and in-vitro evolution of RNA
and DNA that performs "enzymatic" functions. Check out his stuff
to warp your sense of the possible. He is interested in creating molecular
tools that would be useful for DNA computing. Any requests?
Here's a random assortment of people / labs who do somewhat related work:
Takashi Yokomori (genome analysis,
inductive inference, & formal languages), Masami
Hagiya (proofs, programs, & biology), Weizmann
Institute of Science, Foundations of CS, Bob
Austin at Princeton studies biophysics of DNA & stuff. Tom
Knight at MIT has some thoughts on "microbial engineering".
Cristian Calude studies
AIT. Michael Groves thinks about molecular
electronic circuits. Marcelo
Magnasco of the Rockefeller Institute takes a physics approach to chemical
Send comments to