BE/CS/CNS/Bi 191ab: Biomolecular Computation
Professor: Erik Winfree
Winter term teaching assistants: Robert Johnson, Andrés Ortiz-Muñoz, and Tyler Ross
This page is archival for Winter 2018. The previous incarnation was Winter 2017.
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 2018, Moore B270, Tu & Th 10:30am-11:55am
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): Annenberg 107 Mondays at 7pm and Annenberg 243 Tuesdays at 4pm. Note that different days have different rooms.
For simple and quick questions, TAs can also be reached by email at cs191_ta * dna.caltech.edu, but may not be available to answer substantial questions in a timely manner. Non-trivial questions should be deferred to and answered at 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-2pm 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.
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.
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.
Biochemistry & combinatorial CRNs -- 2 lectures (tools: reaction schema simulator for Mathematica)
- Introduction and overview -- 1 lecture
- Jan 4: computation in the cell and the promise of molecular programming.
- Chemical reaction networks (CRNs) -- 7 lectures (tools:
Mathematica (download, tutorial) using the
CRN Simulator package.)
- Jan 9: continuous mass action model, kinetics, 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, analog computation]
- Jan 11: 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 16: digital circuits using mass action, signal loss and restoration, digital abstraction, logic gates. (part 2)
[example Mathematica notebook for digital circuits.]
- Jan 18: mass action dynamical systems for oscillators, chaos, and everything.
[optional refs on dual-rail linear and
general dynamical systems, and
- Jan 23: discrete stochastic model, kinetics and probabilities, computing with counts (part 1).
[optional refs on stochastic simulations.]
- Jan 25: discrete stochastic model, kinetics and probabilities, computing with counts (part 2).
[example Mathematica notebook for stochastic CRNs.]
- Jan 30: discrete stochastic model, kinetics and probabilities, computing with counts (part 3).
[optional refs on stochastic computing,
more computing, and
even more computing.]
Nucleic acid circuits -- 5 lectures (tools: Visual DSD and NUPACK)
- Feb 1: the central dogma and enzymes of molecular biology, computing with strings.
[optional refs on
the central dogma (classic paper),
example biochemical computing machines, a
general CS formalism for biochemistry.]
- Feb 6: 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,
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
genetic regulatory networks, and
Passive self-assembly -- 4 lectures (tools: Tile Asssembly Simulator in Mathematica)
Active self-assembly and molecular robots -- 0 lecture (tools: TBA)
- Feb 8: DNA reassociation kinetics, biophysics, and DNA strand displacement cascades (part 1).
[optional refs on
4-way branch migration including
toeholds, also secondary structure
thermodynamics, and finally abstract
- Feb 13: DNA reassociation kinetics, biophysics, and DNA strand displacement cascades (part 2).
- Feb 15: implementation of arbitrary circuits and CRNs using domain-level DNA strand displacement systems (part 1).
[optional refs on
small logic cascades,
large logic cascades,
neural networks, and
- Feb 20: implementation of arbitrary circuits and CRNs using domain-level DNA strand displacement systems (part 2).
[example Visual DSD code for cascades and
- Feb 22: implementing efficient algorithmic behavior: stack machines with DNA strand displacement cascades.
[optional refs on
stack machines and
[example Visual DSD code for stack machines.]
Amorphous computing and synthetic biology -- 0 lectures (tools: gro)
Note: reference links may require a Caltech IP address.
- (not covered in 2018): Experimental molecular robots and the theoretical NUBOT model. fast algorithmic developmental growth.
[optional refs TBA]
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 exam per se.
Homeworks: Homeworks will be graded on a 0-10 scale for each problem.
Late policy: 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 linearly per hour, accumulating 10% per day, until a 9 day late
homework's score is multiplied by 0.1, and a 10 day late homework gets
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, 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 less likely
to merit an extension, since starting and completing homework early should be an option.
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
For more detail and discussion, see
the nice write-up for CS11 or this more recent
Accompanying Notes and Files for Homework:
For homework 1: AnnotatedExamples.nb provides some useful hints for how
to use the CRN Simulator package in Mathematica. Note that some
browsers will download the package as AnnotatedExamples.nb.txt, in
which case you will need to rename it after download.
Homework 1 will be accepted with no late penalty if submitted before midnight Friday, January 12.
- 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
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 2018 by demand only, by at least 5 students. UPDATE: Part b *will* be taught in 2018.