Anne Condon

Professor and Head, Department of Computer Science
University of British Columbia

Homepage
Profile page on Department of Computer Science, UBC

ABSTRACT

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.

BIOGRAPHY

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.