Erik's Molecular Computation page:

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 Sam Roweis.
• 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, Peter 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 Condon, Elton 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, Mitsunori 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!
• Richard Karp (U. of Washington), Claire Kenyon (Ecole Normale Superieure de Lyon), and Orli Waarts (Berkeley?) have written a paper on how to improve error rates in separation-based DNA computation. (TechRep.) (In SODA.)
• 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 with Alan 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 2nd Annual Workshop on DNA Based Computers. Ray Dassen also has a bibliography online (also in a searchable format).

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 Arita.
• Michael Conrad leads a Biocomputing group at Wayne State University. He and Klaus-Peter Zauner suggest using DNA physical conformation.
• Andy Ellington 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?

Send comments to