Time & Place: 
BE/CS 191a: Winter 2014, Annenberg 107, Tu & Th 10:30am-11:55am
BE/CS 191b: Spring 2014, Annenberg 106, Th 7:30pm-10:00pm

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): Every Sunday from 7-8pm and every Wednesday from 9-10pm in the Moore 204 conference room. TAs can also be reached by email at rfjohnso * caltech.edu and jkishi * caltech.edu, although complex questions may be better answered at and deferred to the office hours.
Prof: Thursdays from 2-3pm in Moore 204. 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 7: computation in the cell and the promise of molecular programming. [Lecture slides available in pdf.]
• Chemical reaction networks (CRNs) -- 5 lectures (tools: GEC)
  • Jan 9: continuous mass action model, kinetics, steady-state, equilibrium [optional refs on mass action]
  • Jan 14: mass action dynamical systems for amplifiers, switches, and memories. [optional ref with sample CRNs.]
  • Jan 16: digital circuits using mass action, signal loss and restoration, digital abstraction, logic gates. [optional refs on digital circuits and an alternative design]
  • Jan 21: mass action dynamical systems for oscillators, chaos, and everything. [optional ref on Korzuhin's Theorem.]
  • Jan 23: discrete stochastic model, kinetics and probabilities; computing with counts. [optional refs on stochastic, computing, more computing, and even more computing.]
• Biochemistry & combinatorial CRNs -- 4 lectures (tools: DACCAD)
  • Jan 28: the central dogma and enzymes of molecular biology, engineering synthetic gene regulatory networks [optional refs on the central dogma (classic paper), a general CS formalism for biochemistry, a genetic bistable switch, and a genetic ring oscillator.]
  • Jan 30: cell-free transcription-degradation circuits [optional refs on the PURE system, transcription/translation circuits, transcription circuits.]
  • Feb 4: neural network associative memories with cell-free transcription-degradation circuits [optional refs on neural networks, and transcription circuit theory.]
  • Feb 6: 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.]
• Nucleic acid circuits -- 3 lectures (tools: DSD and NUPACK)
  • Feb 11: 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 13: 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 18: implementing efficient algorithmic behavior: stack machines with DNA strand displacement cascades. [optional refs on stack machines and even more]
• Passive self-assembly -- 4 lectures (tools: xgrow and ISU TAS)
  • Feb 20: self-assembly combinatorics, kinetics, and thermodynamics of 1D polymers in open and closed systems. [optional refs on DNA computing & linear self-assembly.]
  • Feb 25: 2D tile self-assembly, equilibrium, kinetics, and the nucleation barrier. [optional refs on nucleation theory.]
  • Feb 27: 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 4: 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.]
• Active self-assembly and molecular robots -- 0 lectures (tools: TBA)
  • (not covered in 2014): Experimental molecular robots and the theoretical NUBOT model [optional refs TBA]
  • (not covered in 2014): Capabilities of the NUBOT model: fast algorithmic developmental growth [optional refs TBA]
• Amorphous computing and synthetic biology -- 2 lectures (tools: gro)
  • Mar 6: cell growth and genetic regulatory circuits, cell-cell communication, and pattern formation. [optional refs for simulation, and genetic networks]
  • Mar 11: developmental programs, reaction-diffusion systems, and amorphous computing. [optional refs for reaction-diffusion patterns, programming reaction-diffusion patterns, and amorphous computing.]

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. For more detail and discussion, see the nice write-up for CS11, which applies here for both program code and mathematical derivations, and in spirit applies to other aspects of your class work.

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

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:

• April 24: NS presents the paper; JB gives research update.
  Zhang, D. Y., Hariadi, R. F., Choi, H. M. T. and Winfree, E. Integrating DNA strand-displacement circuitry with DNA tile self-assembly. Nat Comms 4, (2013). (pdf)
• May 1: EP presents the paper; NS gives research update.
  Coore, D., Nagpal, R., and Weiss, R. Paradigms for structure in an amorphous computer. MIT tech report (1997). (pdf)
• May 8: JB presents the paper; EP gives research update.
  Soloveichik, et al. DNA as a universal substrate for chemical kinetics. PNAS 107: pp 5393-5398 (2010). (pdf)
• May 15: EP presents the paper; JB gives research update.
  Erik Winfree and Renat Bekbolatov. Proofreading Tile Sets: Error Correction for Algorithmic Self-Assembly. Lecture Notes in Computer Science Volume 2943, pp 126-144 (2004). (pdf)
• May 22: NS presents the paper; EP gives research update.
  Barish, R. D., Schulman, R., Rothemund, P. W. K. and Winfree, E. An information-bearing seed for nucleating algorithmic self-assembly. Proceedings of the National Academy of Sciences 106, 6054–6059 (2009). (pdf) *
• May 29: JB presents the paper; NS gives research udpate.
  Li, Wei, et al. Three-Input Majority Logic Gate and Multiple Input Logic Circuit Based on DNA Strand Displacement. Nano letters 13.6, pp 2980-2988 (2013). (pdf)
• June 5: final research presentations by JB, EP, and NS.
  

Optional reading list for BE/CS 191b:

• Demaine, E. D. et al. Staged self­-assembly: nanomanufacture of arbitrary shapes with O(1) glues. Nat Comput 7, 347-370 (2008). (pdf) (See also the earlier and more eccentric "Molecular tinkertoys and how to assemble them" (pdf) by Warren D. Smith in 1997.)
• Schulman, R. and Winfree, E. Programmable Control of Nucleation for Algorithmic Self-Assembly. SIAM J. Comput. 39, 1581-1616 (2010). (pdf)
• Mohammed, A. M. and Schulman, R. Directing Self-Assembly of DNA Nanotubes Using Programmable Seeds. Nano Lett. 13, 4006-4013 (2013). (pdf) *
• Wilner, O. I. et al. Self-assembly of DNA nanotubes with controllable diameters. Nat Comms 2, 540- (2011). (pdf)
• LaBean, T. and Park, S. H. Self-assembled DNA Nanotubes. in Nanotechnologies for the Life Sciences (2007) (pdf)
• Patitz, M. J. An introduction to tile-based self-assembly and a survey of recent results. Nat Comput (2013). (pdf)
• Turk, Greg. Generating textures on arbitrary surfaces using reaction-diffusion. Computer Graphics, Vol. 25. No. 4. ACM (1991). (pdf)
• Srinivas, N., et al., On the biophysics and kinetics of toehold-mediated DNA strand displacement. Nucleic Acids Research 41(22): p. 10641-10658 (2013). (pdf)
• SantaLucia, John, Hatim T. Allawi, and P. Ananda Seneviratne. Improved nearest-neighbor parameters for predicting DNA duplex stability. Biochemistry 35.11. pp 3555-3562 (1996). (pdf)
• Seunghee S. Jang, Kevin T. Oishi, Robert G. Egbert, and Eric Klavins. Specification and Simulation of Synthetic Multicelled Behaviors. ACS Synth. Biol., 1 (8), pp 365–374 (2012). (pdf)
• David Sprinzak, et al. Cis-interactions between Notch and Delta generate mutually exclusive signaling states. Nature 465, 86-90 (2010). (pdf)
• Barry M Gumbiner. Cell Adhesion: The Molecular Basis of Tissue Architecture and Morphogenesis. Cell. 84(3):345-57 (1996). (pdf)
• Chia Hung, et al. Escherichia coli Biofilms Have an Organized and Complex Extracellular Matrix Structure. mBio 4(5):e00645-13. doi:10.1128/mBio.00645-13. (pdf)
• Yonggang Ke, et al. Scaffolded DNA Origami of a DNA Tetrahedron Molecular Container. Nano Lett., 9 (6), pp 2445–2447 (2009). (pdf)
• Zhao Zhao, Yan Liu, and Hao Yan. Organizing DNA Origami Tiles Into Larger Structures Using Pre-formed Scaffold Frames. Nano Lett., 11 (7), pp 2997–3002 (2011). (pdf)
• Dominic Scalise and Rebecca Schulman. Designing modular reaction-diffusion programs for complex pattern formation. Technology 02, 55 (2014). DOI: 10.1142/S2339547814500071. (pdf)
• Julien O. Dubuis, et al. Positional information, in bits. PNAS, vol. 110 no. 41, pp. 16301-16308 (2013). (pdf)
• P. Stoodley, K. Sauer, D. G. Davies, and J. W. Costerton. Biofilms as complex differentiated communities. Annual Review of Microbiology. Vol. 56: 187-209 (2002). (pdf)
• Kenichi Fujibayashi, Rizal Hariadi, Sung Ha Park, Erik Winfree, Satoshi Murata. Toward Reliable Algorithmic Self-Assembly of DNA Tiles: A Fixed-Width Cellular Automaton Pattern. Nano Lett., 8 (7), pp 1791–1797 (2008). (pdf)
• Ho-Lin Chen and David Doty. Parallelism and time in hierarchical self-assembly. SODA, pages 1163-1182 (2012). (pdf)
• Peng Yin, et al. Programming DNA Tube Circumferences. Science. Vol. 321 no. 5890 pp. 824-826 (2008). (pdf)
• Harold Abelson, et al. Amorphous computing. Communications of the ACM, Vol. 43 No. 5, Pages 74-82 (2000). (pdf)
• M. Zuker, D. H. Mathews, D. H. Turner. Algorithms and Thermodynamics for RNA Secondary Structure Prediction: A Practical Guide. RNA Biochemistry and Biotechnology. NATO Science Series Volume 70, pp 11-43 (1999). (pdf)
• I. L. Hofacker, W. Fontana, P. F. Stadler, L. S. Bonhoeffer, M. Tacker, P. Schuster. Fast folding and comparison of RNA secondary structures. Monatshefte für Chemie / Chemical Monthly. Volume 125, Issue 2, pp 167-188 (1994). (pdf)
• A. L. Mackay. Generalised Crystallography. Izvjestaj Jugoslavenskog centra za kristalografiju (Proceedings of the Yugoslav Centre of Crystallography). Volume 10, pp 15-36 (1975). (pdf)