COMPSCI 590.02: Molecular Assembly and Computation

Department of Computer Science

Duke University

John H. Reif
Spring Semester, 2020

John H. Reif

         A. Hollis Edens Professor of Computer Science

         D223 LSRC Building

         E-mail: reif AT

         Phone: 919-660-6568

Reif Office Hours:                            

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

TA:   Ming Yang

         D124 LSRC Building

         E-mail: myang AT

         Phone: 919-660-6578

TA Office Hours:                            

Monday & Wedesday 1:30 PM – 2:30 PM at FFSC 3245


Detailed Description of Course Material: see Schedule


Lecture Times:                             Tuesday & Thursday 11:45AM – 1:00 PM
Lecture Location:                         Room: LSRC A155


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.



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



Kenneth Douglas, DNA Nanoscience: From Prebiotic Origins to Emerging Nanotechnology, CRC Press, Edition 1,  (2016) ISBN 9781498750127


Nadrian Seeman, Structural DNA Nanotechnology, CRC Press, Edition 1,  (2016), ISBN  9780521764483



(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 overviewing a chosen topic in Molecular Assembly and Computation

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



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

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 Synthesis and Purification of ssDNA

1.5 DNA Photonics

- Fluorescent labels

- Fluorescence resonance energy transfer (FRET)

- Quantum dots

- Optically-induced cutting of DNA

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 Introduction to DNA Reactions

 1.4 DNA Hybridization Reactions

- Hybridization reactions

- Toehold binding & Strand displacement

3.1 DNA Enzyme reactions:

- Ligation

- Restriction enzymes

- Polymerization & Strand-displacing polymerases

- Helicase enzymes

3.2 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


4. Hybridization Reactions for DNA Computation and Detection

4.1 Adleman’s Experiment

4.2 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

4.3 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.4. Catalytic and Autocatalytic Hybridization Reactions for Detection:

- Pierce's Catalytic Hybridization Chain Reaction

- Autocatalytic Hybridization Chain Reactions

5. Enzymic Reactions for DNA Computation and Detection

5.1 DNA Amplification using Polymerase


- Strand-Displacement PCR

5.1 DNA Computation using Polymerase

- Autonomous DNA Computation via Polymerase Reactions: Whiplash PCR

- Isothermal Whiplash

5.3 Autonomous DNA Computation using Restriction Enzymes

- Shapiro's FSA Computations

- Yin's Devices

5.4 Autonomous DNA Computation using DNAzymes

6 Analog Molecular Computations

- sinusoidal signals

- arithmetic operations

- log-transforms

- Analog-to-digital and digital-to-analog transformations

7. Molecular Robotics

7.1 Natural Protein Molecular Motors

- Molecular Robotics Principals

- Brownian Ratchets & Quantum Ratchets

- Natural Protein Molecular Motors: Polymerase, Myosin & Kinesin

- Re-Engineered Protein Molecular Motors

7.2 Molecular Gears

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

7.4 Autonomous DNA Robotics using Enzymes

- Restriction Enzyme DNA Walker

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

7.4 Autonomous DNA Robotics using DNAzyme

- Spiders: Autonomous Molecular Robotics using DNAzyme

- Mao's and Klavins DNAzyme Nanomotors

7.5 Autonomous DNA Robotics only using DNA Hybridization

- Turberfield's Autonomous DNA Walker:

- Seeman's Piped Walker

7.6 Molecular Assembly Lines and Reaction Factories

8. Abstract Models of Tiling Assembly

8.1 Tiling Assembly Models

- Wang Tiling

- Other Tiling Assembly Models

8.2 Tiles via DNA Nanostructures

8.3 Tiling Computability & Undecidability

8.4 Tile Complexity of Assembled Shapes

- Tile Complexity of Assembled Squares

- Tile Complexity of General Shapes

8.5 Randomized Assembly

- Exact Shapes

- Approx Shapes

- Linear Structures


8.6 Temperature Programmed Assembly

8.7 Staged Assembly & Hierarchical Assembly

8.8 Assembly Error-Correction      

- Assembly Error-Correction via Proofreading

- Compact Assembly Error-Correction:

- Error-Correction Lower Bounds

- Self-Healing

- Invadable Self-Assembly

- Reversible Selfrepair

8.9 Tiles with State Changes