COMPSCI 590.02: Molecular Assembly and Computation

Department of Computer Science

Duke University

John H. Reif
   Fall Semester, 2012

John H. Reif

         A. Hollis Edens Professor of Computer Science

         D223 LSRC Building

         E-mail: reif AT

         Phone: 919-660-6568

Detailed Description of Course Material: see Schedule


Lecture Times: 
                            Tuesday & Thursday 11:45AM – 1:00 PM (See Schedule for details)
Lecture Location:                        
Room: Social Sciences 107

Reif Office Hours:                             Tuesday & Thursday 1:00 PM – 2:00 PM  D223 LSRC Building


Summary Description of Course:

The course will cover the topics of Molecular Assembly, Molecular Computation, and Molecular Robotics. Special emphasis will be on DNA-based approaches, and the course will cover DNA nanostructures, DNA assemblies, and DNA-based robotic devices.

Course Synopsis:

0 Course Overview

1 Introduction to DNA structure, reactions and DNA nanostructures

1.1 Overview of DNA structure

- DNA Overview

- dsDNA secondary and tertiary structure

- Base Stacking

- DNA Hybridization & Duplex DNA

- Synthesis of ssDNA


1.2 Nonstandard DNA structures

- DNA Structure Transitions: DNA B-Z transitions

- DNA Triplex Conformations

- G Quadracomplexes


1.3 Modeling DNA

- Dependence on temperature, salinity, magnesium, crowding molecules

- Cartoon models of DNA

- Graph models for DNA and reactions

- Software for DNA structures


1.4 DNA Photonics

- Fluorescent labels

- Fluorescence resonance energy transfer (FRET)

- Quantum dots

- Optically-induced cutting of DNA


1.5 DNA Hybridization Reactions

- Hybridization reactions

- Toehold binding & Strand displacement

- Base stacking


1.6 DNA Enzyme reactions:

- Ligation

- Restriction enzymes

- Helicase enzymes

- Polymerization & Strand-displacing polymerases


1.7 Kinetics Modeling

- Introduction to Kinetics

- Stochastic Chemical Reaction Networks

- Kinetic Models of DNA Hybridization Reactions

- Kinetic Models of DNA Enzymic Reactions

- Kinetics simulation methods

- Probabilistic Model Checking & PRISM software


2 DNA Nanostructures

2.1 DNA Tiles

- DNA crossovers junctions: Holliday junctions

- DNA DX, TX and crossover tiles

2.2 DNA Lattices

- corrugation and symmetry techniques

- 2D DNA lattices

- 3D DNA lattices

2.3 DNA Origami

- 2D DNA Origami

- 3D DNA Origami

- Origami design software


3. Abstract Models of Tiling Assembly

3.1 Tiling Assembly Models

- Wang Tiling

- Other Tiling Assembly Models

3.2 Tiles via DNA Nanostructures

3.3 Tiling Computability & Undecidability

3.4 Tile Complexity of Assembled Shapes

- Tile Complexity of Assembled Squares

- Tile Complexity of General Shapes

3.5 Randomized Assembly

- Exact Shapes

- Approx Shapes

- Linear Structures


3.6 Temperature Programmed Assembly

3.7 Staged Assembly & Hierarchical Assembly

3.8 Assembly Error-Correction      

- Assembly Error-Correction via Proofreading

- Compact Assembly Error-Correction:

- Error-Correction Lower Bounds

- Self-Healing

- Invadable Self-Assembly

- Reversible Selfrepair

3.9 Tiles with State Changes


4. DNA Computation

4.1 Adleman’s Experiment

4.2 DNA Computation using Polymerase

- Autonomous DNA Computation via Polymerase Reactions: Whiplash PCR

- Isothermal Whiplash

4.3 Autonomous DNA Computation using Restriction Enzymes

- Shapiro's FSA Computations

- Yin's Devices

4.4 Autonomous Computation using DNAzymes

4.5 Autonomous DNA Computation using DNA Hairpins

- Seelig's Catalyzed Metastable DNA Fuel

- Turberfield's DNA Hairpin Fueling Devices

- Winfree's DNA Hairpin Hybridization Circuits

4.6 DNA Reaction Networks Fueled by Strand Displacement

- Winfree's Seesaw Gates

- Yurke's DNA Catalytic Cascades

- Zhang's DNA Reaction Networks and Allosteric DNA Catalytic Reactions

- Soloveichi's DNA Chemical Kinetics

- Cardelli's DNA Strand Algebra


5. Autocatalytic Hybridization Reactions for Detection:

- Pierce's Hybridization Chain Reaction

- Other Autocatalytic Hybridization Chain Reactions


6. Molecular Robotics

6.1 Natural Protein Molecular Motors

- Molecular Robotics Principals

- Brownian Ratchets & Quantum Ratchets

- Natural Protein Molecular Motors: Polymerase, Myosin & Kinesin

- Re-Engineered Protein Molecular Motors

6.2 Molecular Gears

6.3 DNA Robotics via External State Changes:

- Yurke-Tuberfield DNA Tweezers

- DNA Nanostructure Actuation using DNA B-Z transitions

- PX Nanomechanical Devices

- DNA Robotics using Duplex to Triplex Transitions

- DNA Walkers using external state changes 

6.3 Autonomous DNA Robotics using Enzymes

- Restriction Enzyme DNA Walker

- Molecular Robotics using Polymerase: Sahu's Polymerase DNA Transport

6.4 Autonomous DNA Robotics using DNAzyme

- Spiders: Autonomous Molecular Robotics using DNAzyme

- Mao's and Klavins DNAzyme Nanomotors

6.5 Autonomous DNA Robotics only using DNA Hybridization

- Turberfield's Autonomous DNA Walker:

- Seeman's Piped Walker

- Molecular Assembly Lines and Reaction Factories



There are no formal prerequisites for the course, except mathematical maturity.  However, it would help to have a working knowledge of Complexity Theory and Algorithms at the level of an undergraduate algorithms class.


(Tentative) There will be 4 homeworks (10% each, 40% total), , and a Final Project (60%) for the course. Also attendance and class interaction will provide an additional 10% of the total grade.

Homeworks: To be prepared using LATEX (preferred) or WORD.

Homework Rules:

·      Be sure to provide enough details to convince me, but try to keep your answers to at most one or two pages.

·      It is OK to answer a problem by stating it is open, but if so, please convincingly explain the reasons you believe this.

·      It is permitted to collaborate with your classmates, but please list your collaborators with your homework solution.

·      There is no credit given for homework past their due date.

Final Project:

·      The final project is a short (at most 12 pages) paper over viewing (definition of the problem and terminology, and the details of some part of the proof) a prior result in alternative computing modelsy.

·      The topic is of your choice, and the instructor will provide guidance on relevant literature.

·      Novel topics and/or new research may result, but is not necessarily required to still produce an excellent project paper.