Synthetic Recombinase-Based State Machines

Abstract

State machines underlie the sophisticated functionality behind man-made and natural computing systems that perform order-dependent information processing. We developed a recombinase-based framework for building state machines in living cells by leveraging chemically controlled DNA excision and inversion operations to encode state in DNA sequence. This strategy enables convenient read-out of states by sequencing and/or PCR, as well as complex regulation of gene expression. We validated our framework by engineering state machines in Escherichia coli that used up to three chemical inputs to control 16 DNA states. These state machines were capable of recording the temporal order of all inputs and performing multi-input, multi-output control of gene expression. We also developed a computational tool for the automated design of gene regulation programs using recombinase-based state machines. Our scalable framework should enable new strategies for recording and studying how combinational and temporal events regulate complex cell functions and for programming sophisticated cell behaviors.