On the Rewards and Challenges of Programming with Chemical Reaction Networks and DNA Strand Displacement Systems
Bio-molecules have remarkable capabilities in the cell, including information processing, communication and transportation. Recent technological advances have enabled scientists to design and program simple DNA molecular systems with a variety of computational and functional capabilities, many of which already exceed the roles of DNA in the cell. Bio-molecules are interesting to program because of their dynamic structural and material properties, because they enable us to organize matter at the nano-scale and because they can naturally interact with biological systems at the cellular level. It is hard to imagine a future in which programming molecules will not be central to understanding and mediating cellular and other nano-scale processes.
So, how can we program molecules? Researchers in the field of DNA
computing and molecular programming have developed many creative
approaches, along with experimental demonstrations of the viability of
these approaches. In this tutorial I'll focus on two personal
favourites, namely Chemical Reaction Networks (CRNs) and DNA Strand
Displacement Systems (DSDs). I'll
describe why these are interesting programming models, what we know
about effective ways to write CRN and DSD programs, and what are
important directions for further progress.
CRNs comprise a distributed computing model in which, starting from an
initial pool of molecules (duplicates from a finite set of species),
reactions ensue that consume and produce species, thereby converging
on an "outcome" pool that indicates the result of a computation. CRNs
are interesting in part because they model chemical system kinetics -
the basis for biological information processing - and in part because
they provide a very natural level of abstraction in which to design
and reason about molecular processes.
DSD programs model a lower level of abstraction than CRNs. At their
core is a basic primitive whereby an initially unbound input DNA
strand I binds to a template T, thereby displacing an output
strand O that was initially bound to T so that O becomes unbound.
Strand O can in turn act as input for a subsequent displacement. DSDs
are collections of strands that can change configurations, i.e., which
strands are bound and which are unbound, via successive strand
displacements in a pre-programmed fashion, ultimately producing
unbound strands that encode the result of a computation.
Topics covered will include:
- Motivation: why CRNs and DSDs provide useful levels of abstraction
for reasoning about molecular computations
- Overview of experimental successes in programming with DSDs;
- How the models are related: how to compile abstract CRNs to
physically realizable DSDs;
- How to measure time and space use of CRN and DSD programs;
- Uniform and non-uniform CRN and DSD complexity classes; deterministic
and stochastic variants;
- Limits to computing with CRNs and DSDs;
- Connections with reversible computing;
- Connections with known distributed computing models;
- Variants of the models, e.g., CRNs with (polymer) stacks;
- Connections with nucleic acid folding pathways;
- Directions for future research (there are many).
Much of the material covered can be found in recent seminal research
papers of Doty, Qian, Seelig, Soloveichik, Winfree and others
that have appeared both in theoretical forums and in more experimental
science journals. Some of the material will draw from work that I have
done with collaborators Kirkpatrick, Manuch, and Thachuk.
Anne Condon studies combinatorial and algorithmic problems that arise in the design of DNA strands that behave well in real DNA computing experiments.
She won the ACM Distinguished Dissertation award for her thesis research. In 2010, the Association for Computing Machinery named her an ACM Fellow "for contributions to complexity theory and leadership in advancing women in computing". In the same year, she also won the A. Nico Habermann Award of the Computing Research Association for "long-standing and impactful service toward the goal of increasing the participation of women in computer science research." She is also a winner of the University College Cork Distinguished Alumna Award, the University of Washington CSE Alumni Achievement Award, and the 2012 University of Washington College of Engineering Diamond Award for Distinguished Achievement in Academia.
Condon was elected a Fellow of the Royal Society of Canada in 2012.