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

Professor: Erik Winfree

Winter term teaching assistants: Andrés Ortiz-Muñoz, Tatiana Brailovskaya, and Gokul Gowri

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 2019, Kerckhoff B136, Tu & Th 10:30am-11:55am

**Office hours:**

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.

TAs (191a only): Mondays at 5pm and Tuesdays at 7pm in the Teaching Resource Room on the 9th floor of Millikan Library.

While the professor and TAs can be reached by email at cs191_ta * dna.caltech.edu if necessary, questions about homework and
other class issues should be addressed through Piazza (or in the office hours). Even if you know them, please do not use the TAs' personal email addresses; it is important that all TAs be kept in the loop on class-related issues.

Professor (Winter term only): Tuesdays 1:30-2:00pm in Moore 204. This is only for things that can't be handled by the TAs, such as administrative issues. Email is answered, though often not quickly, at winfree * caltech.edu.

**Textbook:**

None. Everything you need to know will be presented in class. The references suggested in the syllabus are optional further reading, but neither sufficient nor necessary.

**Lectures:**

Attending lectures is mandatory. There may be an in-class quiz from time to time.

**Syllabus for 191a:**

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. Prior to that, the topics and links may be revised.

- Introduction and overview -- 1 lecture
- Jan 8: inspiration from biology and the molecular programming vision

- Chemical reaction networks (CRNs) -- 9 lectures (tools:
Mathematica (download, tutorial) using the
CRN Simulator package.)
- Jan 10: continuous mass action model, kinetics, rate-independent stoichiometric analog computation.

[example Mathematica notebook for CRN Simulations. You might want to control-click this to download it rather than view it. It should have the extension ".nb".];

[optional refs on mass action, stoichiometric analog computation] - Jan 15: rate-dependent catalytic steady-state analog computation.

[optional ref on CRN programming] - Jan 17: mass action dynamical systems for oscillators, chaos, and everything.

[optional refs on dual-rail linear and general dynamical systems, and Korzuhin's Theorem.] [example Mathematica notebook for dynamical systems.] - Jan 22: CRNs that solve systems of equations and optimize cost functions.

[example Mathematica notebook for problem solving.] - Jan 24: digital circuits using mass action, signal loss and restoration, digital abstraction, logic gates.

[optional refs on digital circuits and an alternative design] [example Mathematica notebook for digital circuits.] - Jan 29: discrete stochastic model, kinetics and probabilities.

[optional refs on stochastic simulations.] [example Mathematica notebook for stochastic CRNs.] - Jan 31: perspectives on stochastic CRNs: noisy kinetics, distributions, reachability.

- Feb 5: perspectives on stochastic CRNs: 0 vs 1, exploiting reachability and extinction with search.

- Feb 7: perspectives on stochastic CRNs: 0 vs 1, computing with counts, register machines.

[optional refs on stochastic computing, more computing, and even more computing.]

- Jan 10: continuous mass action model, kinetics, rate-independent stoichiometric analog computation.
- Biochemistry & combinatorial CRNs -- 2 lectures (tools: reaction schema simulator for Mathematica)
- Feb 12: the central dogma and enzymes of molecular biology, computing with strings, reaction schema.

[optional refs on the central dogma (classic paper), example biochemical computing machines, a general CS formalism for biochemistry.] - Feb 14: Efficient Turing-universal computation with polymer-modifying enzymes.

[example Mathematica notebook for reaction schemata.] - (not covered in 2018): engineering synthetic gene regulatory networks (part 1), model, digital abstraction, and feedforward circuits.

- (not covered in 2018): engineering synthetic gene regulatory networks (part 2), iterative sequential circuits, bistable memories, latches, and oscillators.

[optional refs on a genetic bistable switch, a genetic ring oscillator.]

[Mathematica notebook for this week's lectures.] - (not covered in 2018): cell-free transcription-translation (TX-TL) circuits, transcription-degradation (TX) circuits, and polymerase-exonucleate-nickase (PEN) circuits.

[optional refs on the PURE system, TX-TL circuits, bistable TX circuit and oscillatory TX circuits, oscillatory PEN circuit, bistable PEN circuit, a pattern recognition design, and the DACCAD design simulator.] - (not covered in 2018): neural network computation and biochemical networks.

[optional refs on neural networks, genetic regulatory networks, and transcription-degradation circuits.]

- Feb 12: the central dogma and enzymes of molecular biology, computing with strings, reaction schema.
- Nucleic acid circuits -- 3 lectures (tools: Visual DSD and NUPACK)
- Feb 19: DNA reassociation kinetics, biophysics, and DNA strand displacement cascades.

[optional refs on 3-way and 4-way branch migration including mismatches and toeholds, also secondary structure kinetics and thermodynamics, and finally abstract domain-level programming.] - Feb 21: implementation of arbitrary circuits and CRNs using domain-level DNA strand displacement systems.

[optional refs on small logic cascades, catalytic cycles, large logic cascades, neural networks, and CRN-to-DNA compilation.]

[example Visual DSD code for cascades and oscillators.] - Feb 26: implementing efficient algorithmic behavior: stack machines with DNA strand displacement cascades.

[optional refs on stack machines and even more] [example Visual DSD code for stack machines.]

- Feb 19: DNA reassociation kinetics, biophysics, and DNA strand displacement cascades.
- Passive self-assembly -- 4 lectures (tools: Tile Asssembly Simulator in Mathematica)
- (not covered in 2018): Introduction to DNA self-assembly [lecture slides, 71 MB] [optional refs on DNA experiments for Sierpinski patterns and copying and counting from a seed] [alternative simulators: xgrow or ISU TAS]
- Feb 28: 1D & 2D tile self-assembly: thermodynamics and kinetics, nucleation, error rates and phase diagram.

[optional refs on simulation, nucleation theory, proofreading.] - Mar 5: The abstract Tile Assembly Model (aTAM), algorithmic patterns, and programming self-assembly of shapes.

[optional refs on DNA computing & linear self-assembly, and self-assembling squares.] - Mar 7: Turing universality of the abstract Tile Assembly Model (aTAM) for computation and for shapes.

[optional refs on self-assembling arbitrary shapes, and a review paper.] - Mar 12: Program transformations for self-assembly: self-healing growth.

[optional refs on self-healing.]

[Mathematica notebook for the Tile Assembly Simulator.]

- Active self-assembly and molecular robots -- 0 lecture (tools: TBA)
- (not covered in 2018): Experimental molecular robots and the theoretical NUBOT model. fast algorithmic developmental growth.

[optional refs TBA]

- (not covered in 2018): Experimental molecular robots and the theoretical NUBOT model. fast algorithmic developmental growth.
- Amorphous computing and synthetic biology -- 0 lectures (tools: gro)
- (not covererd in 2018): cell growth and genetic regulatory circuits, cell-cell communication, and pattern formation.

[optional refs for simulation, and genetic networks] - (not covered in 2018): developmental programs, reaction-diffusion systems, and amorphous computing.

[optional refs for reaction-diffusion patterns, programming reaction-diffusion patterns, and amorphous computing.]

- (not covererd in 2018): cell growth and genetic regulatory circuits, cell-cell communication, and pattern formation.

Homeworks

The expectation is that homework will be handed out in class every Thursday, and due by submission online (instructions in the homework handout) before 11:59pm on Wednesday 6 days thereafter. I expect to assign 10 homework sets.

**Grading Policy for 191a:**

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

__Homeworks:__ Homeworks will be graded on a 0-10 scale for each problem.

__Late policy:__ To accommodate tought weeks, travel, being sick, and other vicissitudes of life,
you are each allocated 10 free "late days". It is your responsibility to keep track of them. One "late day" is
used if the homework is turned in within 24 hours of the due date, two if within 48 hours, etc.
After your free late days are used up, late homework will be
penalized by 10% per day, e.g. if turned in 24 hours late, the score will be multiplied by 0.9 after
grading, and if turned in 48 hours late, the penalty will
be 20%. The penalty increases in steps at 24 hour boundaries, accumulating 10% per day, until a 9 day late (i.e. 8.000001 to 9.000000 days 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.*

__Extension policy:__ Extensions may be granted by the professor only, at his discretion and only after "late days" have been used up,
for interfering situations that cannot be planned for, e.g. a health problem with a doctor's note, last-minute
travel for interviews, etc. Travel that can be planned well in advance (e.g. a sports competition) is not likely
to merit an extension, since starting and completing homework early should be an option, or could be accommodated using "late days".

__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. That is to say, the "50 foot rule" applies here explicitly for both program code and
mathematical derivations, and in spirit applies to other aspects of your
class work.
For more detail and discussion, see
the nice write-up for CS11 or this more recent
flier
.

**Helpful background:**

- Python, Matlab, or Mathematica programming
- Digital circuits, finite state machines, 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

**Description for 191b:**

In the spring term, I have sometimes taught a class that begins by reading and discussing classic
and contemporary research papers on biomolecular computation, and also includes a mini research project.
*This second term will be taught in 2019 by demand only, by at least 4 students, and then only if I am still in town.*