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
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.