BIRS Workshop Lecture Videos

Banff International Research Station Logo

BIRS Workshop Lecture Videos

Overview talk - An introduction to molecular programming with Stochastic CRNs Condon, Anne


Stochastic Chemical Reaction Networks (CRNs) can be viewed as programs whose instructions are reactions; these instructions execute asynchronously and in parallel to produce a number of output molecules that is a function of the initial counts of molecular species in a well-mixed solution. For example, the simple program "X + Y --> Z + Z", executing in a solution that initially contains copies of two molecular species X and Y, eventually produces a number of copies of molecule Z that is exactly twice the minimum of the initial counts of X and Y, thereby computing 2min{#X,#Y}. How fast does this program run, as a function of the initial species counts (assuming fixed conditions such as volume)? Are there faster programs that produce the same output? More generally, what can and cannot be computed by CRN programs? These questions are attracting much attention in light of significant success in "compiling" CRN programs into real molecular controllers that can sense and respond to conditions in a chemical environment. A beautiful emerging theory of computing with CRNs is providing sharp answers to such questions. The theory and underlying computing models have their roots partly in distributed computing, where population protocols and Petri nets - essentially CRNs in disguise - shed light on the computing power of massively parallel systems of distributed computing agents, interacting asynchronously. In this talk I'll introduce some stochastic CRN computing models, as well as results on their computational power that are due to Angluin, Aspnes, Doty, Soloveichik and others, along with open questions and directions for future work.

Item Media

Item Citations and Data


Attribution-NonCommercial-NoDerivatives 4.0 International