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

Professor: Erik Winfree

Winter term teaching assistants: Joseph Berleant, Paul Dieterle, Robert Johnson, and Nicholas Schiefer

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 2015, Annenberg 105, Tu & Th 10:30am-11:55am

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

**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 8pm and Tuesdays at 7pm in Annenberg 106.

TAs can also be reached by email at (preferred:) cs191_ta * dna.caltech.edu or (less likely to be answered promptly:)
jberlean@caltech.edu and pauldieterle * gmail.com and rfjohnso * caltech.edu and nschiefer * caltech.edu.
Please note that non-trivial questions should be deferred to and answered at the office hours.

Prof: Wednesdays from 2-3pm in Moore 204 (but 3-4pm Jan 28 only). This is for issues that can't be handled by the TA only. Email is answered, though often not quickly, at winfree * caltech.edu.

**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 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 6: computation in the cell and the promise of molecular programming.

- Chemical reaction networks (CRNs) -- 6 lectures (tools: GEC)
- Jan 8: continuous mass action model, kinetics, analog computation.

[example LBS file for analog computation]; [optional refs on mass action, analog computation] - Jan 13: digital circuits using mass action, signal loss and restoration, digital abstraction, logic gates. (part 1)

[optional refs on digital circuits and an alternative design] - Jan 15: digital circuits using mass action, signal loss and restoration, digital abstraction, logic gates. (part 2)

[example LBS file for digital computation] - Jan 20: mass action dynamical systems for oscillators, chaos, and everything.

[optional refs on dual-rail linear and general dynamical systems, and Korzuhin's Theorem.] - Jan 22: discrete stochastic model, kinetics and probabilities, computing with counts (part 1).

[optional refs on stochastic, computing, more computing, and even more computing.] - Jan 27: discrete stochastic model, kinetics and probabilities, computing with counts (part 2).

- Jan 8: continuous mass action model, kinetics, analog computation.
- Biochemistry & combinatorial CRNs -- 4 lectures (tools: DACCAD)
- Jan 29: the central dogma and enzymes of molecular biology, computing with strings, gene regulatory networks introduction.

[optional refs on the central dogma (classic paper), example biochemical computing machines, a general CS formalism for biochemistry.] - Feb 3: engineering synthetic gene regulatory networks, bistable memories and oscillators.

[optional refs on a genetic bistable switch, a genetic ring oscillator, the PURE system, transcription/translation circuits.] - (not covered in 2015): cell-free transcription-degradation circuits.

[optional refs on experimental bistable circuit and experimental oscillator circuits.] - Feb 5: winner-take-all computation with cell-free polymerase-exonuclease-nickase circuits.

[optional refs on an oscillator, a memory circuit, a pattern recognition design, and the DACCAD design simulator.] - Feb 10: neural network computation and biochemical networks.

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

- Jan 29: the central dogma and enzymes of molecular biology, computing with strings, gene regulatory networks introduction.
- Nucleic acid circuits -- 3 lectures (tools: DSD and NUPACK)
- Feb 12: NO CLASS: STUDENT-FACULTY CONFERENCE.

- Feb 17: 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 19: 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.] - Feb 24: implementing efficient algorithmic behavior: stack machines with DNA strand displacement cascades.

[optional refs on stack machines and even more]

- Feb 12: NO CLASS: STUDENT-FACULTY CONFERENCE.
- Passive self-assembly -- 2 lectures (tools: xgrow and ISU TAS)
- (not covered in 2015): 1D self-assembly combinatorics, kinetics, and thermodynamics in open and closed systems.

[optional refs on DNA computing & linear self-assembly.] - (not covered in 2015): 2D tile self-assembly equilibrium, kinetics, and the nucleation barrier.

[optional refs on nucleation theory.] - Feb 26: abstract Tile Assembly Model (aTAM), error rates and phase diagram, algorithmic patterns and shapes.

[optional refs on simulation, DNA experiments for Sierpinski patterns and copying and counting from a seed, and a review paper.] - Mar 3: growing arbitrary algorithmic shapes with few tile types.

[optional refs on self-assembling squares and arbitrary shapes.] [extra-optional refs on self-healing and proofreading.]

- (not covered in 2015): 1D self-assembly combinatorics, kinetics, and thermodynamics in open and closed systems.
- Active self-assembly and molecular robots -- 0 lectures (tools: TBA)
- (not covered in 2015): Experimental molecular robots and the theoretical NUBOT model.

[optional refs TBA] - (not covered in 2015): Capabilities of the NUBOT model: fast algorithmic developmental growth.

[optional refs TBA]

- (not covered in 2015): Experimental molecular robots and the theoretical NUBOT model.
- Amorphous computing and synthetic biology -- 2 lectures (tools: gro)
- Mar 5: cell growth and genetic regulatory circuits, cell-cell communication, and pattern formation.

[optional refs for simulation, and genetic networks] - Mar 10: developmental programs, reaction-diffusion systems, and amorphous computing.

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

- Mar 5: 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 other Thursday, and due by email as a single PDF file before 11:59pm on Wednesday 13 days thereafter. I expect to assign six homework sets.

**Grading Policy for 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. 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
.

**Accompanying Files for Homework:**

For homework 4: stack_machine.dna, stack_species.pdf, stack_machine.pdf.

For homework 5:
"xgrow" used to be a breeze to install and run. It still is, on Linux. On Mac OS X, it is a breeze if you have installed
XQuartz and
XCode and are comfortable with the command-line compiler. If that's you, just download the xgrow tarball, unpack, compile, and run.

Otherwise, it may be easiest to use a pre-compiled version of xgrow on a virtual machine. For this, you still need to do some work, for which a fast internet connection is an absolute necessity. You will need the following:
compressed VirtualBox disk image (1.3 GB!!! could take an hour to download),
software such as
7-zip or
Keka that is capabale of unpacking the compressed image,
and
VirtualBox itself.
After you unpack the disk image, you will get a directory "be191-xgrow" that will contain the 4.5GB file "be191-xgrow.vdi".
To use that disk image, you must start VirtualBox.app, click on "new"
to create a new virtual machine, use any name you want, Microsoft
Windows / Windows XP (64 bit), and other defaults until you get to the
choice of "hard drive", at which point you should select
"be191-xgrow.vdi". Then create the machine and power it up.
There is a README on the Desktop, and xgrow is pre-compiled in a subdirectory of the same name.
Click on the menu in the upper left to start a Terminal Emulator. To verify that xgrow runs, type "cd xgrow", hit return, then type "./xgrow tilesets/BinaryTree.tiles", and hit return. A simulation should run, and you can hit "quit" in that window when it's done. Other example commands can be found in the text file "example-runs".

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

**Description for 191b:**

In the spring term, we will begin by reading and discussing classic
and contemporary research papers on biomolecular computation.
Simultaneously, you will formulate and explore a mini-project (theory
or simulation) of your own choosing. Each week you will hand in a
written critique of the reading and a summary of your research
progress (1 page each). At the end of the class, you will hand in a
5-10 page report on your research project.

**Selected reading list for BE/CS 191b, and schedule of presentations:**

- To be determined...

**Optional reading list for BE/CS 191b:**

- On schemes of combinatorial transcription logic
- Framework for Engineering Finite State Machines in Gene Regulatory Networks
- Designing sequential transcription logic: a simple genetic circuit for conditional memory
- Active Self-Assembly of Algorithmic Shapes and Patterns in Polylogarithmic Time
- DNA Self-Assembly For Constructing 3D Boxes (pdf)
- The Complexity of Self-Assembled Shapes (pdf
- Deterministic function computation with chemical reaction networks
- Space and Energy Efficient Computation with DNA Strand Displacement Systems (pdf)
- Self-healing tile sets (pdf)
- Amorphous Computing
- Designing modular reaction-diffusion programs for complex pattern formation
- Universal Computation and Optimal Construction in the Chemical Reaction Network-Controlled Tile Assembly Model (pre-publication draft!)
- The Design of a Genetic Muller C-Element
- Rate-Independent Constructs for Chemical Computation
- A simple DNA gate motif for synthesizing large-scale circuits