BE/CS/CNS/Bi 191ab: Biomolecular Computation

Professor: Erik Winfree

Guest lecturers & TAs: Nadine Dabby, David Doty, Constantine Evans, Jongmin Kim, Lulu Qian, Joseph Schaeffer, Niranjan Srinivas, Damien Woods

Description from the course catalog:

BE/CS/CNS/Bi 191 ab. Biomolecular Computation. 9 units (3-0-6) first term; (2-4-3) third term. Prerequisite: ChE/BE 163. Recommended: CS 21, CS 129 ab, or equivalent. This course investigates computation by molecular systems, emphasizing models of computation based on the underlying physics, chemistry, and organization of biological cells. We will explore programmability, complexity, simulation of and reasoning about abstract models of chemical reaction networks, molecular folding, molecular self-assembly, and molecular motors, with an emphasis on universal architectures for computation, control, and construction within molecular systems. If time permits, we will also discuss biological example systems such as signal transduction, genetic regulatory networks, and the cytoskeleton; physical limits of computation, reversibility, reliability, and the role of noise, DNA-based computers and DNA nanotechnology. Part a develops fundamental results; part b is a reading and research course: classic and current papers will be discussed, and students will do projects on current research topics. Instructor: Winfree. 191b is not offered in 2011-2012.

**Time & Place:**

BE/CS 191a: First term, 2011, Annenberg 107, Tu & Th 10:30am-11:55am

BE/CS 191b: Will not be offered in the 2011-2012 academic year.

**Office hours:**

Wednesday October 12, 2-3pm, Moore 204 conference room.

Monday October 17, 2-3pm, Moore 204 conference room.

Monday October 24, 3-4pm, Moore 204 conference room.

Thursday October 27, 3-4pm, Moore 204 conference room.

Monday October 31, 3-4pm, Moore 204 conference room.

Tuesday November 8, 4-5pm, Moore 204 conference room.

Thursday November 10, 3-4pm, Moore 204 conference room.

Monday November 14, 4-5pm, Moore 204 conference room.

Thursday November 17, 3-4pm, Moore 204 conference room.

Tuesday November 22, 4-5pm, Moore 204 conference room.

Tuesday November 29, 4-5pm, Moore 204 conference room.

Monday Dec 5, 4-5pm, Moore 204 conference room.

Wednesday Dec 7, 4-5pm, Moore 204 conference room.

**Syllabus (subject to change):**

- Introduction and overview -- 1 lecture
- Sep 27: computation in the cell and the promise of molecular programming.

- Chemical reaction networks (CRNs) -- 4 lectures (tools: GEC)
- Sep 29: mass action model, kinetics & equilibrium [optional refs on mass action, with sample CRNs]
- Oct 4: stochastic model, kinetics and probabilities [optional ref on stochastic]
- Oct 6: digital circuits --> CRNs (digital abstraction, latches & recursion); stochastic to mass action [optional refs on digital circuits and an alternative design]
- Oct 11: computing with counts (stochastic) & ODEs --> CRNs (mass action) [optional refs on computing, and more computing, and even more computing, and then Korzuhin's Theorem.]

- Biochemistry & combinatorial CRNs -- 2 lectures
- Oct 13: the central dogma and enzymes of molecular biology, example systems with infinite sets of species [lecture slides in .pptx, .pdf] [optional ref on restriction enzymes.]
- Oct 18: classes of programmable biochemical circuits in vitro (TX/TL, TX, PNE) [lecture slides in .pptx, .pdf] [optional refs on the PURE system, transcription/translation circuits, and transcription circuits, and polymerase/nickase/exonuclease circuits.]

- Nucleic acid circuits -- 5 lectures (tools: DSD and NUPACK)
- Oct 20: secondary structure, energetics, kinetics, 3-way and 4-way branch migration, toeholds [optional refs on 3-way and 4-way branch migration including mismatches and toeholds, also secondary structure kinetics and thermodynamics.]
- Oct 25: domain-level models for DNA strand displacement cascades [lecture slides in .pdf] [optional refs on domain-level programming.]
- Oct 27: circuits built using strand displacement cascades [lecture slides in .pdf] [optional refs on logic cascades, catalytic cycles, more logic cascades, and neural networks.]
- Nov 1: implementing arbitrary CRNs and stack machines with DNA strand displacement cascades [lecture slides in .pdf] [optional refs on CRNs and stack machines (even more).]
- Nov 3: compiling domain-level implementations to DNA sequences [lecture slides available upon request] [optional refs on sequence design.]

- Passive self-assembly -- 3 lectures (tools: xgrow and ISU TAS)
- Nov 8: introduction to experimental and theoretical systems [lecture slides in .ppt and in .odp] [optional refs on DNA computing & linear self-assembly, and self-assembled squares.]
- Nov 10: aTAM programming -- algorithmic patterns & shapes & computation & repair [optional refs on arbitrary shapes, self-healing.]
- Nov 15: kTAM simulations -- kinetics, thermodynamics, proofreading, nucleation [lecture notes in .pdf] [optional refs on simulation, proofreading, nucleation, and experiments on Sierpinski DNA, and copying and counting from a seed.]

- Active self-assembly and molecular robotics -- 3 lectures
- Nov 17: molecular motors & DNA walkers & molecular robotics olympics [lecture notes in .pdf] [optional refs for caterpillar walker, spiders on origami, and true DNA walker.]
- Nov 22: triggered self-assembly & disassembly: HCR, insertional polymerization, hairpin motif [optional refs on hybridization chain reaction, insertional polymerization, assembly & disassembly.]
- Nov 29 and Dec 1: fast fabrication of objects with molecular robots: active self-assembly [slides in .pdf]

- Amorphous computing and synthetic biology -- 1 lecture (tools: gro)
- Dec 1: reaction-diffusion, pattern formation, and amorphous computing, genetic regulatory circuits, cell growth, and development [optional refs for reaction-diffusion patterns, and genetic networks.]

Homeworks

- Homework set #1 was handed out October 4th and is due by email October 17th (Monday) before 11:59pm.
- Homework set #2 was handed out October 18th and is due by email October 31th (Monday) before 11:59pm.
- Homework set #3 was handed out November 1st and is due by email November 14th (Monday) before 11:59pm.

[HW had wrong due date, so Nov 15 will also be accepted.]

Accompanying files: scheme1_oscillator.dna, scheme2_circuit.dna, stack_machine.dna - Homework set #4 was handed out November 15th and is due by email December 1st (Thursday) before 11:59pm. Happy Thanksgiving!

Accompanying files: collisions1.tiles, collisions2.tiles - Homework set #5 was handed out December 1st and is due by email December 9th (Friday) before 11:59pm.

Accompanying files: ring.gro,

**Grading Policy for BE 191a:**

There will be roughly one problem per class lecture, with homework sets due roughly every other week. There is no midterm or final.

__Homeworks:__ Homeworks will be graded on a 0-10 scale for each problem.
For each homework set, an exemplary student solution will be chosen
and handed out in class (with the name hidden).

__Late policy:__ Late homework up to 24 hours late will be
penalized by 10%, i.e. the score will be multiplied by 0.9 after
grading. For two-day late HW (i.e up to 48 hours), the penalty will
be 20%. The penalty increases by 10% per day, until a 9 day late
homework's score is multiplied by 0.1, and a 10 day late homework gets
no credit.
*The homework sets are hard, but ample time is given. Start as soon as they are handed out.*

__Grade composition:__ Your class grade will be based on homeworks only.

__Collaboration policy:__ For all problem sets, you may discuss
problems with other students prior to writing anything down, but what
you turn in must be entirely written by you, by yourself, including
any program code.

**Helpful background:**

- Python, Matlab, or Mathematica programming
- Digital AND OR NOT circuits
- Finite State Machines and Regular Languages
- Turing machines & Register machines
- Cellular automata
- Chemical reaction networks; mass-action and stochastic kinetics and thermodynamics
- Basic molecular biology, central dogma enzymes, cytoskeleton
- DNA secondary structure, folding kinetics and thermodynamics, hybridization & dissociation rates, toeholds, 3-way & 4-way branch migration