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

Professor: Erik Winfree

Winter term: Guest lecturer, class #1: David Doty. Teaching assistant: Constantine Evans

Description from the course catalog:

BE/CS/CNS/Bi 191 ab. Biomolecular Computation. 9 units (3-0-6) second term; (2-4-3) third term. Prerequisite: none. Recommended: ChE/BE 163, 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.

**Time & Place:**

BE/CS 191a: Winter 2013, Annenberg 107, Tu & Th 10:30am-11:55am

BE/CS 191b: Spring 2013, Annenberg 106, Th 7:30-9:55pm

**Office hours:**

TA: Friday January 11th from 3-4pm in the Moore 204 conference room, and
every Friday thereafter at the same time.
Please start your homework set early, and come to the first relevant TA session.
The homework will usually be too much to do at the last minute, and planning for this is your responsibility.

Prof: Thursdays from 3-4pm in Moore 204. This is for issues that can't be handled by the TA only.

**Textbook:**

None. Please attend class. Everything you need to know should be presented there. The references suggested below are optional further reading, but neither sufficient nor necessary.

**Syllabus:**

The syllabus as presented gives you a rough idea of what will be in
the class, but it is subject to change in detail. The topics and
references should be considered final only on the day of the lecture,
and after.

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

- Chemical reaction networks (CRNs) -- 5 lectures (tools: GEC)
- Jan 10: continuous mass action model, kinetics, steady-state, equilibrium -- illustrated via chemotaxis circuitry. [optional refs on mass action, a bacterial chemotaxis example]
- Jan 15: mass action dynamical systems for amplifiers, switches, and memories. [optional ref with sample CRNs.]
- Jan 17: mass action dynamical systems for oscillators, chaos, and everything. [optional ref on Korzuhin's Theorem.]
- Jan 22: digital circuits using mass action, signal loss and restoration, digital abstraction, logic gates. [optional refs on digital circuits and an alternative design]
- Jan 24: discrete stochastic model, kinetics and probabilities; computing with counts. [optional refs on stochastic, computing, more computing, and even more computing.]

- Biochemistry & combinatorial CRNs -- 3 lectures
- Jan 29: the central dogma and enzymes of molecular biology, example systems with infinite sets of species. [optional refs on restriction enzymes], and general formalisms for biochemistry.]
- Jan 31: classes of programmable biochemical circuits in vitro (TX/TL, TX, PNE) [optional refs on the PURE system, transcription/translation circuits, and transcription circuits, and polymerase/nickase/exonuclease circuits.]
- Feb 5: neural network associative memories with cell-free transcription circuits [optional refs on neural networks, and transcription circuit theory.]

- Nucleic acid circuits -- 4 lectures (tools: DSD and NUPACK)
- Feb 7: DNA reassociation kinetics, secondary structure, energetics, 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.]
- Feb 12: domain-level models for DNA strand displacement cascades and implementation of arbitrary circuits and CRNs. [optional refs on domain-level programming, logic cascades, catalytic cycles, more logic cascades, and neural networks.]
- Feb 14: Cancelled due to student-faculty conference.
- Feb 19: implementing efficient algorithmic behavior: stack machines with DNA strand displacement cascades. [optional refs on CRNs and stack machines (even more)]
- Skipped: compiling domain-level implementations to DNA sequences. [optional refs on sequence design.]

- Passive self-assembly -- 4 lectures (tools: xgrow and ISU TAS)
- Feb 21: introduction to experimental and theoretical systems for tile-based self-assembly. [lecture slides in .ppt] [optional refs on experiments on DNA computing & linear self-assembly, Sierpinski in DNA, and copying and counting from a seed]
- Feb 26: algorithmic patterns & and growing squares -- aTAM programming [optional refs on squares, and review paper]
- Feb 28: computation & growing algorithmic shapes -- aTAM programming [optional refs on arbitrary shapes]
- Mar 5: errors and error-correction -- self-healing, kinetics, thermodynamics, proofreading, nucleation -- kTAM simulations [optional refs on self-healing, simulation, proofreading, nucleation, and

- Amorphous computing and synthetic biology -- 2 lectures (tools: gro)
- Mar 7: cell growth and genetic regulatory circuits, cell-cell communication, and pattern formation [optional refs for simulation, and genetic networks]
- Mar 12: reaction-diffusion systems, development, and amorphous computing [optional refs for reaction-diffusion patterns, and amorphous computing]

Homeworks

Typically, homework will be handed out in class every other Tuesday, and due by email as a single PDF file before 11:59pm on Monday 13 days thereafter. There will be five homework sets.

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

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

**Accompanying Files for Homework:**

For problem set 3, stack_machine.dna.

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