DNA image

Molecular Algorithms, CME 352
Winter 2007-08, Stanford University
Instructor: Ashish Goel
MW 2:15-3:30, BRAUNLEC (we will stick to this original time and not change it)
Auditors, please subscribe to cme352-win0708-guests at http://mailman.stanford.edu

DNA image

Course Description

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.

Administrative information

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.

            Algorithmic self-assembly
            Error correction in self-assembly
            Algorithmic use of bio-chemical mechanisms
            Molecular machines and molecular computation
            Open problems
            Example applications

Links (will be updated)

Reading list (will be updated)

Molecular Computation Of Solutions To Combinatorial. Problems.
Leonard M. Adleman.

The Program-Size Complexity of Self-Assembled Squares.
Paul W. K. Rothemund and Erik Winfree.

Running time and program size for self-assembled squares.
L. Adleman, Q. Cheng, A. Goel, and M.-D. Huang.
Complexities for Generalized Models of Self-Assembly
Gagan Aggarwal, Michael H. Goldwasser, Ming-Yang Kao and Robert T. Schweller

Optimal self-assembly of counters at temperature two.
Q. Cheng, A. Goel, and P. Moisset

Folding DNA to create nanoscale shapes and patterns 
Paul W. K. Rothemund

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

Invadable Self-Assembly: Combining Robustness with Efficiency.
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

Error 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
Erik Winfree

Self-Assembling Tile Systems that Heal from Small Fragments.
H. Chen, A. Goel, C. Luhrs, and E. Winfree.

Dimension Augmentation and Combinatorial Criteria for Efficient Error-resistant DNA Self-Assembly
H. Chen, A. Goel, and C. Luhrs

A DNA-fuelled molecular machine made of DNA
B. Yurke, A.J. Turberfield, A.P. Mills, Jr., F.C. Simmel and J.L. Neumann.

An Improved Autonomous DNA Nanomotor.
J. Bishop and E. Klavins.

A Unidirectional DNA Walker That Moves Autonomously along a Track
Peng Yin, Hao Yan, Xiaoju G. Daniell, Andrew J. Turberfield, John H. Reif

Design of an Autonomous DNA Nanomechanical Device Capable of Universal Computation and Universal Translational Motion.
Peng Yin, Andrew J. Turberfield, Sudheer Sahu, John H. Reif, 

Towards programmable molecular machines
H. Chen, A.De, and A. Goel
Unpublished manuscript; please do not distribute.

The Computational Power of Benenson Automata.
David Soloveichik and Erik Winfree.

Computation with Finite Stochastic Chemical Reaction Networks.
David Soloveichik, Matt Cook, Erik Winfree, and Shuki Bruck.

Engineering Entropy-Driven Reactions and Networks Catalyzed by DNA.
David Yu Zhang, Andrew J. Turberfield, Bernard Yurke, and Erik Winfree.