Molecular Algorithms, CME
Winter 2007-08, Stanford University
Instructor: Ashish Goel
MW 2:15-3:30, BRAUNLEC (we will stick to this original time and not
Auditors, please subscribe to cme352-win0708-guests at http://mailman.stanford.edu
We are used to thinking of DNA as a biological molecule. However, DNA,
its cousin the RNA, and other associated molecules such as enzymes, are
also engineering building blocks. Think of them as combinatorial
"legos" which fit together and inter-operate not just by mechanics and
geometry but also using the chemical sequence imprinted on them. This
is a new and exciting engineering primitive, with many revolutionary
potential applications. In this class, we will study algorithms which
can be implemented using these molecules, either to assemble a shape or
to perform an action or a computation. The focus of the class will be
algorithmic and mathematical, but we will discuss many real life
properties of these molecules and potential applications.
The prerequisites are an understanding of basic probability and
basic algorithms. An understanding of bio-chemistry is not required,
but a healthy curiosity will be useful. The class will be taught out of
research papers. A preliminary reading list is attached below and will
be updated as the class progresses. There is an optional project
(compulsory if you are taking the class for a letter grade) and some
homeworks. Please download and install xgrow
on your computer.
You can also use the shared installation on rabi.stanford.edu . I have
emailed the login and the password to the class email list -- you can
ask for it over email if you like. To use this installation, you must
be comfortable with linux and ssh/putty and also have an X-server
running on your host. Also, X will be really slow if you are doing it
from outside the Stanford network.
correction in self-assembly
use of bio-chemical mechanisms
machines and molecular computation
Links (will be updated)
list (will be updated)
Computation Of Solutions To Combinatorial. Problems.
Leonard M. Adleman.
Program-Size Complexity of Self-Assembled Squares.
Paul W. K. Rothemund and Erik Winfree.
time and program size for self-assembled squares
L. Adleman, Q. Cheng, A. Goel, and M.-D. Huang.
Self-Assembly: Combining Robustness with Efficiency
for Generalized Models of Self-Assembly
- Gagan Aggarwal, Michael H. Goldwasser, Ming-Yang Kao and Robert
self-assembly of counters at temperature two.
- Q. Cheng, A. Goel, and P. Moisset
DNA to create nanoscale shapes and patterns
- Paul W. K. Rothemund
optimization problems in self-assembly.
- L. Adleman, Q. Cheng, A. Goel, M.-D. Huang, D. Kempe, P. Moisset
de espanes, and P. W. K. Rothemund.
H. Chen, Q. Cheng, A. Goel, M.-D.Huang, and P. Moisset.
Proofreading Tile Sets: Error Correction for Algorithmic Self-Assembly.
Erik Winfree and Renat Bekbolatov
Free Self-Assembly with Error Prone Tiles.
H. Chen and A. Goel.
Compact Error-Resilient Computational DNA Tiling Assemblies
John H. Reif, Sudheer Sahu, Peng Yin.
Complexity of Compact Proofreading for Self-Assembled Patterns.
David Soloveichik and Erik Winfree.
Self-Healing Tile Sets
Tile Systems that Heal from Small Fragments.
H. Chen, A. Goel, C. Luhrs, and E. Winfree.
Augmentation and Combinatorial Criteria for Efficient Error-resistant
H. Chen, A. Goel, and C. Luhrs
DNA-fuelled molecular machine made of DNA
B. Yurke, A.J. Turberfield, A.P. Mills, Jr., F.C. Simmel and J.L.
Autonomous DNA Nanomotor.
J. Bishop and
Peng Yin, Hao Yan, Xiaoju G. Daniell, Andrew J. Turberfield, John H.