Title: Less Haste, Less Waste: On Recycling and its Limits in Strand Displacement Systems
Speaker: Chris Thachuk
Department of Computer Science, University of British Columbia
Abstract

We study the potential for molecule recycling in chemical reaction systems and their DNA strand displacement realizations. Recycling happens when a product of one reaction is a reactant in a later reaction. Recycling has the benefits of reducing consumption, or waste, of molecules and of avoiding fuel depletion. We present a binary counter that recycles molecules efficiently while incurring just a moderate slowdown compared to alternative counters that do not recycle strands. This counter is an n-bit binary reflecting Gray code counter that advances through 2^n states. In the strand displacement realization of this counter, the waste---total number of nucleotides of the DNA strands consumed---is O(n^3), while alternative counters have Omega(2^n) waste. We also show that our n-bit counter fails to work correctly when Theta(n) copies of the species that represent the state (bits) of the counter are present initially. The proof applies more generally to show that a class of chemical reaction systems, in which all but one reactant of each reaction are catalysts, are not capable of computations longer than 1/2*n^2 steps when there are at least n copies.