DNA Computation  

  

Head '87

Tom Head. "Formal Language Theory and DNA: An Analysis of the Generative Capacity of Specific Recombinant Behaviors." Bulletin of Mathematical Biology 49:737-759, 1987.

Introduced splicing systems, an abstract, formal-language style model of recombinant DNA manipulations.

  

Denninghoff & Gatterdam '87

K. L. Denninghoff and R. W. Gatterdam. "On the undecidability of splicing systems." Intern. J. Computer Math., 27:133-145, 1989.

Early paper showing how a Turing machine can be embedded in a "splicing system," an abstract (and somewhat idealized) model of recombination.

  

Heller & Tullis '91

Michael J. Heller and Richard H. Tullis. "Self-organizing molecular photonic structures based on functionalized synthetic nucleic acid (DNA) polymers." Nanotechnology 2:165-171, 1991.

  

Seeman '91

Nadrian C. Seeman. "The use of branched DNA for nanoscale fabrication." Nanotechnology 2:149-159, 1991.

  

Adleman '94

Leonard M. Adleman. "Molecular computation of solutions to combinatorial problems." Science 266:1021-1023, Nov. 11, 1994.

The original paper that made the field of DNA computation take off. Describes an experiment in which a 7-node instance of the directed Hamiltonian path problem was solved using oligonucleotide ligation followed by isolation of the correct path. Suggested encoding TM configurations in DNA.

  

Gifford '94

David K. Gifford. "On the path to computation with DNA." Science 266:993-994, Nov. 11 1994.

Points out that Adleman's technique is not universal and suggests the goal of building a universal computer using DNA.

  

Kolata '94

Gina Kolata. "Novel kind of computing: Calculation with DNA." New York Times, Nov. 22, 1994.

First appearance of DNA computation in the news. Describes Adleman's paper for the layperson.

  

Lipton '94

Richard J. Lipton. "Speeding up computations via molecular biology." Unpushlished report, December 1994.

Shows how to solve SAT with DNA manipulations. These ideas were later published as a paper in Science.

  

Beaver '94

Donald Beaver. "Factoring: The DNA Solution," or "Computing With DNA." Journal of Computational Biology, to appear Spring 1995. Draft available on the World-Wide Web at URL http://www.cse.psu.edu/~beaver/research/publications/bc.ps.

"How to factor and compute NP functions using DNA, using a novel procedure for site-directed mutagenesis."
-- Don's publications web page.

  

Adleman '95

Leonard M. Adleman. "On constructing a molecular computer (draft)." Unpublished draft report, Jan. 8, 1995.

Starts with abstract model from Lipton's paper. Defines restricted model lacking "amplify" operator. Solves 3-colorability. Discusses practical implementation of operators. Combinatorial chemistry.

  

Beaver '95

Donald Beaver. "A Universal Molecular Computer," or "Molecular Computing." Technical Report CSE-95-001, Penn State University, 1995. Available on the World-Wide Web at URL http://www.cse.psu.edu/~beaver/research/publications/TR95-001.ps.

"How to build and operate a Turing machine consisting of a single DNA molecule. How to compute NP and PSPACE functions using a molecular computer."
-- Don's publications web page.

This design requires a different symbol encoding for every position on the tape, and separation of strands according to the rewrite that is to be applied.

  

Smith & Schweitzer '95

Warren D. Smith and Allan Schweitzer. "DNA computers in vitro and vivo." Technical report, NECI, 4 Independence Way, Princeton NJ 08544, March 20, 1995. Patent Pending.

Describes a universal DNA computer based on restriction enzymes. Also contains speculations about other several possible computational mechanisms in existing biological systems.

  

Gonick '95

Larry Gonick. "The Solution." Discover, April 1995.

Cute cartoon describing Adleman's experiment.

  

Kolata '95

Gina Kolata. "A vat of DNA may become fast computer of the future." New York Times, April 11, 1995, page C1.

News summary of the DIMACS Mini Workshop on DNA Based Computers (held Tuesday, April 4, 1995 at Princeton University).

  

Pool '95

Robert Pool. "A Boom in Plans for DNA Computing," Science 268:498-499, April 28, 1995.

  

Linial et al. '95

Michael Linial and Nathan Linial; Y.-M. D. Lo, K. F. C. Yiu, and S. L. Wong; Barry Bunow; and Leonard M. Adleman. "On the Potential of Molecular Computing." Letters to the editor, Science 268:481-484, April 28, 1995.

  

Lipton '95

Richard J. Lipton. "DNA Solution of Hard Computational Problems." Science 268:542-545, April 28, 1995.