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

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.