Research Article

Synthetic recombinase-based state machines in living cells

See allHide authors and affiliations

Science  22 Jul 2016:
Vol. 353, Issue 6297, aad8559
DOI: 10.1126/science.aad8559

Building a computing system in bacteria

Finite state machines are logic circuits with a predetermined sequence of actions that are triggered depending on the starting conditions. They are used for a variety of devices and biological systems, from vending machines to neural circuits. Roquet et al. have taken a finite state machine approach to control the expression of integrases, or enzymes that insert or excise phage DNA into or out of bacterial chromosomes. The integrases altered the DNA sequence of a plasmid to record all five possible combinations of two inputs. Such circuits can be used to record the states that the cell experienced over time and can be deployed in state-dependent gene expression programs.

Science, this issue p. 363

Structured Abstract


Living systems execute regulatory programs and exhibit specific phenotypes depending on the identity and timing of chemical signals, but general strategies for mimicking such behaviors with artificial genetic programs are lacking. Synthetic circuits that produce outputs only depending on simultaneous combinations of inputs are limited in their scale and their ability to recognize dynamics because they do not uniquely detect or respond to temporally ordered inputs. To address these limitations, we developed and experimentally validated a framework for implementing state machines that record and respond to all identities and orders of gene regulatory events in living cells.


We built recombinase-based state machines (RSMs) that use input-driven recombinases to manipulate DNA registers made up of overlapping and orthogonal pairs of recombinase recognition sites. Specifically, chemical inputs express recombinases that can perform two types of irreversible operations on a register: excision if their recognition sites are aligned, or inversion if their recognition sites are anti-aligned. The registers are designed to adopt a distinct DNA sequence (“state”) for every possible “permuted substring” of inputs—that is, every possible combination and ordering of inputs. The state persists even when inputs are removed and may be read with sequencing or by polymerase chain reaction. Using mathematical analysis to determine how the structure of a RSM relates to its scalability, we found that incorporating multiple orthogonal pairs of recognition sites per recombinase allows a RSM to outperform combinational circuits in scale.

Genetic parts (made up of promoters, terminators, and genes) may be interleaved into RSM registers to implement gene regulation programs capable of expressing unique combinations of genes in each state. In addition, we provide a computational tool that accepts a user-specified two-input multigene regulation program and returns corresponding registers that implement it. This searchable database enables facile creation of RSMs with desired behaviors without requiring detailed knowledge of gene circuit design.


We built two-input, five-state RSMs and three-input, 16-state RSMs capable of recording every permuted substring of their inputs. We tested the RSMs in Escherichia coli and used Sanger sequencing to measure performance. For the two-input, five-state RSM, at least 97% of cells treated with each permuted substring of inputs adopted their expected state. For the three-input, 16-state RSM, at least 88% of cells treated with each permuted substring of inputs adopted their expected state, although we observed 100% for most treatment conditions.

We used these two- and three-input RSMs to implement gene regulation programs by interleaving genetic parts into their registers. For the two-input, five-state system, we designed registers for various gene regulation programs using our computational database and search function. Four single-gene regulation programs and one multigene regulation program (which expressed a different set of fluorescent reports in each state) were successfully implemented in E. coli, with at least 94% of cells adopting their expected gene expression profile when treated with each permuted substring of inputs. Lastly, we successfully implemented two different three-input, 16-state gene regulation programs; one of these—a three-input passcode switch—performed with at least 97% of cells adopting the expected gene expression behavior.


Our work presents a powerful framework for implementing RSMs in living cells that are capable of recording and responding to all identities and orders of a set of chemical inputs. Depending on desired applications, the prototypical inducible systems used here to drive the RSMs can be replaced by sensors that correspond to desired input signals or gene regulation events. We anticipate that the integration of RSMs into complex living systems will transform our capacity to understand and engineer them.

Summary of a three-input, 16-state RSM.

(A) The RSM mechanism. A chemical input induces the expression of a recombinase (from a gene on the input plasmid) that modifies a DNA register made up of overlapping and orthogonal recombinase recognition sites. Distinct recombinases can be controlled by distinct inputs. These recombinases each target multiple orthogonal pairs of their cognate recognition sites (shown as triangles and half-ovals) to catalyze inversion (when the sites are anti-aligned) or excision (when the sites are aligned). (B) The register is designed to adopt a distinct DNA state for every identity and order of inputs. Three different inputs—orange, blue, and purple—are represented by colored arrows. Unrecombined recognition sites are shaded; recombined recognition sites are outlined.


State machines underlie the sophisticated functionality behind human-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 states in DNA sequences. This strategy enables convenient readout of states (by sequencing and/or polymerase chain reaction) as well as complex regulation of gene expression. We validated our framework by engineering state machines in Escherichia coli that used one, two, or three chemical inputs to control up to 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.

View Full Text

Stay Connected to Science