ECS 232: Theory of Molecular Computation
Fall 2023

Course announcement (PDF)

Instructor

Dave Doty
doty@ucdavis.edu
Office hour: Thursday 2:30-3:30
Office: Zoom link

Lectures

MWF, 12:10-1:00pm, Cruess 107

Course objective

To study the fundamental abilities and limits to the engineering of automated (i.e., computational) molecular systems, in a mathematically rigorous way.

Prerequisites

ECS 120 or equivalent (familiarity with Chapters 1,3,4,7 of Introduction to the Theory of Computation by Sipser), or permission of instructor

Prior experience with probability theory is useful; in particular, Chapters 1-2 of Probability and Computing: Randomization and Probabilistic Techniques in Algorithms and Data Analysis, by Mitzenmacher and Upfal.

Piazza

The Piazza page for the course can be used to ask questions about the course and homework. Use access code ecs232 to enroll. Please use Piazza instead of email unless the question is of a personal nature.

Slides

slides

Videos

I recorded videos of the lectures in Winter 2021.

Notes

lecture notes (these are not comprehensive since I often take material straight from a paper; they were used prior to Winter 2021, when I switched to slides, but they are more detailed in many proofs than the slides, while covering fewer total topics)

Homework

There is a Canvas page with the homework posted.

Project

Project ideas

Schedule

The exact dates we cover various topics may vary; here they are just listed in the order we will cover them. (One quarter the topics below were covered two per week on a Tuesday/Thursday lecture schedule, as an example of the pace.) See also the slides link above; we will go through those slides in order.

Algorithmic tile self-assembly

  1. Introduction to course, introduction to abstract Tile Assembly Model (aTAM)
    aTAM video introduction
    ISU TAS simulator
  2. tile complexity of assembling squares
    O(log n) tile types for assembling an n x n square
    Ω(log n / log log n) tile types necessary to assemble an n x n square
    paper: The Program-Size Complexity of Self-Assembled Squares,
    O(log n / log log n) tile types sufficient to assemble an n x n square
    paper: Running Time and Program Size for Self-assembled Squares
  3. formal definition of the aTAM
  4. simulation of Turing machine with a tile assembly system
    assembling scaled-up version of any finite shape from optimal number of tile types
    paper: Complexity of Self-Assembled Shapes,
    computable shape not strictly self-assembled by any TAS
    paper: Strict Self-Assembly of Discrete Sierpinski Triangles,
    computable set not weakly self-assembled by any TAS
    paper: Computability and Complexity in Self-Assembly
  5. concentration programming
    paper: Randomized self-assembly for exact shapes
    finite shape that requires more tile types to strictly self-assemble with a directed TAS than a non-directed TAS; NPNP-completeness of computing minimum tile set strictly self-assembling a shape
    paper: The Power of Nondeterminism in Self-Assembly
  6. kTAM for error analysis
    paper: Simulations of Computing by Self-Assembly
    proofreading for error-correction
    paper: Proofreading Tile Sets: Error Correction for Algorithmic Self-Assembly
Some other topics we didn't cover on algorithmic self-assembly:

Chemical reaction networks

  1. Introduction to chemical reaction networks (CRNs). Examples of stable predicate and function computation.
    paper (predicates): Computation in Networks of Passively Mobile Finite-State Sensors
    paper (functions): Deterministic Function Computation with Chemical Reaction Networks
  2. Formal definition of stable predicate/function computation.
    Characterizations of stable computation in terms of reachability, probability-1, and fair executions
    Feedforward CRNs.
  3. Non-competitive CRNs.
    Formal definition discrete chemical kinetic model (Gillespie model).
    paper: Exact stochastic simulation of coupled chemical reactions
  4. Derivation of expected completion times for some simple CRNs.
    time complexity analysis of computing functions/predicates with CRNs
    Definition of semilinear sets and functions, claim that only they can be stably computed.
  5. Every semilinear set/function can be stably computed by a CRN.
    paper (predicates): Computation in Networks of Passively Mobile Finite-State Sensors
    paper (functions): Deterministic Function Computation with Chemical Reaction Networks
  6. Only semilinear sets/functions can be stably computed by a CRN.
    paper (predicates): Stably Computable Predicates are Semilinear
    paper (functions): Deterministic Function Computation with Chemical Reaction Networks
  7. Statement (without proofs) of what is known about predicates/functions stably computable in sublinear time
    Brief overview of results under other modeling choices: Register machines.
    Turing-universality: simulation of register machines by CRNs with a small probability of error; statement of CRN time complexity lower bounds
    paper: Computation with Finite Stochastic Chemical Reaction Networks
    paper: Fast Computation by Population Protocols With a Leader

DNA strand displacement

  1. Introduction to DNA strand displacement.
    Visual DSD (simulation tool)
    papers:
  2. dual-rail logic for Boolean circuits. ABC for minimizing circuits.
    Leaks and error-prevention in DNA strand displacement.
    papers:

DNA sequence design

  1. DNA energy models
    polynomial-time algorithm for minimum free energy
    DNA sequence design for arbitrary constraints with stochastic local search
    papers:

Thermodynamic binding networks

  1. Thermodynamic binding networks
    Boolean circuits
    paper: Thermodynamic binding networks
  2. Thermodynamic binding networks
    Kinetic barriers
    Exponential size bound on stable polymers
    aTAM counter that is thermodynamically stable
    papers:

Project presentations

  1. Project presentations
  2. Project presentations