Towards Temporal Logic Computation Using DNA Strand Displacement Reactions


Time-varying signals are ubiquitous throughout science, and studying the high-level temporal structure of such processes is of significant practical importance. In this context, techniques from computer science such as temporal logic are a powerful tool. Temporal logic allows one to describe temporal properties of time-varying processes, e.g., the order in which particular events occur. In this paper, we show that DNA strand displacement reaction networks can be used to implement computations that check certain temporal relationships within time-varying input signals. A key aspect of this work is the development of DNA circuits that incorporate a primitive memory, so that their behavior is influenced not just by the current observed chemical environment, but also by environments observed in the past. We formalize our circuit designs in the DSD programming language and use simulation results to confirm that they function as intended. This work opens up the possibility of developing DNA circuits capable of long-term monitoring of processes such as cellular function, and points to possible designs of future DNA circuits that can decide more sophisticated temporal logics.

Unconventional Computation and Natural Computation