Molecular Self-Assembly: Models and Algorithms
(Register for MS&E 319/CS 369X: Research Topics in Optimization)
Spring 2003-04, Stanford University

TTh 4:15-5:30, Building 540, Room 103


* Instructor: Ashish Goel (Office Hours: Tue 1-2)

* Essential Class Information: Syllabus, Grading policy, Timetable etc.

* Handouts

*Slides from lectures

* Grades

* Reading List

* Announcements Archive


Announcements: HW 1 is now online. Also, there is no class on Thu, Apr 22nd. Please use this time to do the background work mentioned in HW1.


Class Information


Description: Self-assembly is the ubiquitous process by which objects autonomously assemble into complexes. Nature provides many examples: Atoms react to form molecules. Molecules react to form crystals and supramolecules. Cells coalesce to form organisms. Precisely controlled molecular self-assembly has the potential to be a whole new engineering paradigm, much like the engine and the semiconductor. It will enable nano-machines, computation at the molecular level, fractal antennas, and molecular circuits, among other things.


DNA is a natural candidate for molecular self-assembly. It has the right size, its functionality is determined largely by its combinatorics rather than geometry, and nature offers a "proof of concept" for DNA self-assembly.


In this class, we will develop models and algorithms to facilitate efficient and robust self-assembly at the nano scale. We will study self-assembly from combinatorial, optimization, and stochastic viewpoints. We will point out the broad topics where further mathematical research is urgently needed. We will also describe some of the recent experimental advances in DNA self-assembly, and the applications which motivate these experiments.


Detailed Syllabus


Grading: There will be four homework assignments, one of which will be an open-ended research project and another will be a take-home midterm. It is expected that most of the students will register for this class using the P/NC option. For these students, there will be no final exam your grade will be determined by class participation and your performance on the homework assignments. If you are signed up for a letter grade, please let me know in advance you will be given an extra take home exam.


Collaboration Policy: No collaboration is allowed on any of the homework assignments unless explicitly permitted.


Prerequisites: Students must have taken one class (or have an equivalent background) from each of the following categories:

  1. CS 161 or MS&E 212
  2. MS&E 121 or STATS 217
  3. Basic calculus



Detailed Syllabus


Motivating examples


What is molecular self-assembly?


An abstract combinatorial model for DNA self-assembly


Universal computation using self-assembly


Assembly time and design complexity of self-assembled systems


Constructing counters using self-assembly the difference between natural and engineered self-assembly


Efficient construction of fixed sized squares using self-assembly upper and lower bounds


Techniques for analyzing assembly time


Optimization problems in self-assembly


Some interesting self-assembled patterns



Memory chips?


Reversible self-assembly: a thermodynamic model



Convergence rates


Why errors happen


Approaches to make self-assembling systems robust: coding theory for natural systems


Step-wise self-assembly: trading design complexity for experiment complexity


State of the art a review of recent experimental progress


Self-assembly at larger scales:

Ant colony optimization

Algorithms for assembling tiny robots





  1. Homework 1.






Reading List


Self-Assembled Circuit Patterns by Matthew Cook, Paul W.K. Rothemund, and Erik Winfree


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


Running time and program size for self-assembled squares by Adleman, Cheng, Goel, and Huang


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


Combinatorial optimization problems in self-assembly. By Adleman, Cheng, Goel, Huang, Kempe. Moisset, and Rothemund. Read the first three sections.


Slides for error-correction.


Invadable self-assembly.


Proof-reading for error-correction: Initial paper, Snaked proofreading.





Announcements Archive


* 3/31/04. Note to auditors: Please subscribe to the email list msande319-spr0304-guests using

* 4/20/04. HW 1 is now online. Due 4/30.

* 4/20/04. There will be no class on Thu, 4/22. Please use this time to do the background work mentioned in HW1.