Laboratory for Molecular Science

From Rothemund PNAS 2000 see below

Papers From LMS

DNA Computation

Leonard Adleman: Molecular computation of solutions to combinatorial problems. Science, 266:1021-1024. (Nov. 11). 1994.The tools of molecular biology were used to solve an instance of the directed Hamiltonian path problem. A small graph was encoded in molecules of DNA, and the "operations" of the computation were performed with standard protocols and enzymes. This experiment demonstrates the feasibility of carrying out computations at the molecular level.
Postscript version  PDF version- netified by Todd Masco without diagrams

Postscript version  PDF version

Leonard Adleman: On constructing a molecular computer, DNA Based Computers, Eds. R. Lipton and E. Baum, DIMACS: series in Discrete Mathematics and Theoretical Computer Science, American Mathematical Society. 1-21(1996)

It has recently been suggested that under some circumstances computers based on molecular interactions may be a viable alternative to computers based on electronics. Here, some practical aspects of constructing a molecular computer are considered.

Postscript version  PDF version- early draft

Sam Roweis, Erik Winfree, Richard Burgoyne, Nickolas Chelyapov, Myron Goodman, Paul Rothemund, Leonard Adleman: A sticker based architecture for DNA computation. 2nd annual workshop on DNA Computing, Princeton University. Eds. L. Landweber and E. Baum, DIMACS: series in Discrete Mathematics and Theoretical Computer Science, American Mathematical Society. 1-29 (1999).A new representation for encoding bits in DNA is presented and examined, and generally applicable methods for decreasing separation error rates are discussed. (in DIMACS #2) A shorter version of this paper (without the discussion of decreasing errors) appears in the Journal of Computational Biology (1998).
Postscript version  PDF version

Leonard Adleman, Paul W. K. Rothemund, Sam Roweis, Erik Winfree: On applying molecular computation to the Data Encryption Standard. 2nd annual workshop on DNA Computing, Princeton University, Eds. L. Landweber and E. Baum, DIMACS: series in Discrete Mathematics and Theoretical Computer Science, American Mathematical Society. 31-44 (1999).

Recently, Boneh, Dunworth, and Lipton described the potential use of molecular computation in attacking the United States Data Encryption Standard (DES). Here, we provide a description of such an attack using the sticker model of molecular computation. Our analysis suggests that such an attack might be mounted on a table-top machine, using approximately a gram of DNA and might succeed even in the presence of a large number of errors.

This paper also appears in the Journal of Computational Biology (1999).

Postscript Version  PDF version

Leonard Adleman: Computing with DNA. Scientific American, 279(2):54--61, August 1998.

An account of DNA computation intended as an introduction.


The manipulation of DNA to solve mathematical problems is redefining what is meant by "computation".
PDF version- approximately 13megs

Paul Rothemund: Using lateral capillary forces to compute by self-assembly, PNAS, February 1, 2000

Experiments using a macroscopic self-assembly system to explore the possibility of performing computation using self-assembly.

An image related to the paper was selected for the cover of PNAS
.

PDF version  Additional Image 1  Additional Image 2

Ravinderjit S. Braich, Clifford Johnson, Paul W.K. Rothemund, Darryl Hwang, Nickolas Chelyapov and Leonard M. Adleman: Solution of a satisfiability problem on a gel-based DNA computer, proceedings of the 6th International Conference on DNA Computation in the Springer-Verlag Lecture Notes in Computer Science series.
We have succeeded in solving an instance of a 6-variable 11-clause 3-SAT problem on a gel based DNA computer. Separations were performed using probes covalently bound to polyacrylamide gel. During the entire computation, DNA was retained within a single gel and moved via electrophoresis. The methods used appear to be readily automatable and should be suitable for problems of a significantly larger size.

PDF version

Self-assembly

Leonard Adleman: Toward a mathematical theory of self-assembly, USC Tech Report, January 2000.
An attempt to initiate a theory of self-assembly which combines aspects of thermodynamics with aspects of computational complexity.Since this report considerable changes to the theory have been made.

Postscript version  PDF version

Paul Rothemund and Erik Winfree: The program size complexity of self-assembled squares. STOC 2000.
Postscript version  PDF version

Leonard Adleman, Qi Cheng, Ashish Goel, Ming-Deh Huang and Hal Wasserman: Linear Self-Assemblies: equilibria, entropy, and convergence rates.Abstract Draft April 2000.

Over the last few decades, much of the emphasis in computer science has been on building computers that are more complex and correspondingly more powerful. Recently, however, there has been an increasing awareness of the need for alternative models of computation, quantum computation and DNA computing being two notable examples. The latter necessitates the development of a theory of self-assembly. Winfree proved that self-assembling tile systems in a plane are capable of doing universal computation, and when restricted to a line are exactly as powerful as discrete finite automata. Rothemund and Winfree studied the program size complexity of tile systems needed to produce nxn squares. Both of the above works considered irreversible self-assemblies. In this paper we study reversible linear tile systems.

Postscript version  PDF version

Paul Rothemund: Using lateral capillary forces to compute by self-assembly, PNAS, February 1, 2000

Experiments using a macroscopic self-assembly system to explore the possibility of performing computation using self-assembly.

An image related to the paper was selected for the cover of PNAS

PDF version  Additional Image 1  Additional Image 2

Leonard Adleman, Qi Cheng, Ashish Goel, Ming-deh-Huang, David Kempe, Pablo Moisset, Paul Rothemund: Combinatorial Optimization Problems in Self Assembly.

PDF Format  Postscript Format