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

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.

Topics
            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)

• Overview slides for lecture 1
• An animation of the experiment of Wolkow et al.
• A press article about DNA tweezers
• A video clip of self-assembling robots
• Tiles for the 2-3-5 Chinese remainder counter and triangulation
• Overview slides for lectures 2 and 3
• Scribed notes for lecture 2
• Overview slides for lecture 4
• Homework 1 (handed out 1/20/08, due 1/31)
  
• Project suggestions
  
• Scribed notes for lecture 2
• Overview slides for lectures 5 and 6
• Scribed notes for lecture 6
• Overview slides for lecture 7

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.

Peng Yin, Hao Yan, Xiaoju G. Daniell, Andrew J. Turberfield, John H. Reif