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

            Fractals

            Spirals

            Memory chips?

 

Reversible self-assembly: a thermodynamic model

Entropy

Equilibria

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

 

 

Handouts

 

  1. Homework 1.

 

 

Grades

 

 

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 https://lists.stanford.edu

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