We're sorry but this page doesn't work properly without JavaScript enabled. Please enable it to continue.
Feedback

Overview talk - An introduction to molecular programming with Stochastic CRNs

Formal Metadata

Title
Overview talk - An introduction to molecular programming with Stochastic CRNs
Title of Series
Number of Parts
13
Author
License
CC Attribution - NonCommercial - NoDerivatives 4.0 International:
You are free to use, copy, distribute and transmit the work or content in unchanged form for any legal and non-commercial purpose as long as the work is attributed to the author in the manner specified by the author or licensor.
Identifiers
Publisher
Release Date
Language

Content Metadata

Subject Area
Genre
Abstract
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.
Keywords