John H. Reif
Fall Semester, 2012
Instructor: John H. Reif
A. Hollis Edens Professor of Computer Science
D223 LSRC Building
E-mail: reif AT cs.duke.edu
Phone: 919-660-6568
Detailed Description of Course Material: see Schedule
Lectures:
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
Prerequisites:
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.
Grading:
(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.