Digital logic circuits in yeast with CRISPR-dCas9 NOR gates

Abstract

Natural genetic circuits enable cells to make sophisticated digital decisions. Building equally complex synthetic circuits in eukaryotes remains difficult, however, because commonly used components leak transcriptionally, do not arbitrarily interconnect or do not have digital responses. Here, we designed dCas9-Mxi1-based NOR gates in Saccharomyces cerevisiae that allow arbitrary connectivity and large genetic circuits. Because we used the chromatin remodeller Mxi1, our gates showed minimal leak and digital responses. We built a combinatorial library of NOR gates that directly convert guide RNA (gRNA) inputs into gRNA outputs, enabling the gates to be 'wired' together. We constructed logic circuits with up to seven gRNAs, including repression cascades with up to seven layers. Modelling predicted the NOR gates have effectively zero transcriptional leak explaining the limited signal degradation in the circuits. Our approach enabled the largest, eukaryotic gene circuits to date and will form the basis for large, synthetic, cellular decision-making systems.

ARTICLE

Received 10 Mar 2017 | Accepted 31 Mar 2017 | Published 25 May 2017

Natural genetic circuits enable cells to make sophisticated digital decisions. Building equally complex synthetic circuits in eukaryotes remains difcult, however, because commonly used components leak transcriptionally, do not arbitrarily interconnect or do not have digital responses. Here, we designed dCas9-Mxi1-based NOR gates in Saccharomyces cerevisiae that allow arbitrary connectivity and large genetic circuits. Because we used the chromatin remodeller Mxi1, our gates showed minimal leak and digital responses. We built a combinatorial library of NOR gates that directly convert guide RNA (gRNA) inputs into gRNA outputs, enabling the gates to be wired together. We constructed logic circuits with up to seven gRNAs, including repression cascades with up to seven layers. Modelling predicted the NOR gates have effectively zero transcriptional leak explaining the limited signal degradation in the circuits. Our approach enabled the largest, eukaryotic gene circuits to date and will form the basis for large, synthetic, cellular decision-making systems.

DOI: 10.1038/ncomms15459 OPEN

Digital logic circuits in yeast with CRISPR-dCas9 NOR gates

Miles W. Gander1, Justin D. Vrana2, William E. Voje3, James M. Carothers3,4 & Eric Klavins1,4

1 Department of Electrical Engineering, University of Washington, Seattle, Washington 98195, USA. 2 Department of Bioengineering, University of Washington, Seattle, Washington 98195, USA. 3 Department of Chemical Engineering, University of Washington, Seattle, Washington 98195, USA.

4 Center for Synthetic Biology, University of Washington, Seattle, Washington 98195, USA. Correspondence and requests for materials should be addressed to M.W.G. (email: mailto:[email protected]

Web End [email protected] ).

NATURE COMMUNICATIONS | 8:15459 | DOI: 10.1038/ncomms15459 | http://www.nature.com/naturecommunications

Web End =www.nature.com/naturecommunications 1

ARTICLE NATURE COMMUNICATIONS | DOI: 10.1038/ncomms15459

Living cells make decisions based on information processing genetic programmes. Many of these programmes execute digital functions18. The capability to build synthetic digital

systems in living cells could allow engineers to build novel decision-making regulatory networks for use in a variety of applications9, ranging from gene therapies that modify cell state based on sensed information10,11 to entirely new developmental programmes for tissue engineering12,13. In electronics a compositional approach has allowed the construction of digital circuits of great complexity to be quickly designed and implemented. Here, we have developed set of low-variability genetic parts that can be routinely composed to create large digital circuits in yeast cells.

Genetic components that implement simple logical operations, which in principle could be interconnected to form complex logic functions, have been demonstrated1423. DNA-binding domains (DBDs) such as zinc ngers and TALEs (transcription activator-like effectors) have been used to construct libraries of transcription factors in eukaryotes19,2427. However, scaling with DBDs in eukaryotes has been difcult because of challenges in synthesizing libraries of orthogonal parts28,29. Libraries of DBD-based parts have been shown in prokaryotes, but extensive part characterization and computer-aided design (CAD) was necessary to identify part combinations that yielded functional logic circuits22. Recently, programmable and orthogonal CRISPR-dCas9 transcription factors have been employed18,20,3034 to build up to ve component circuits using

dCas9-mediated repression in prokaryotes18. Transcriptional repression in these circuits is likely due to steric hindrance of RNA polymerase by dCas9. Although dCas9 allows for programmable interconnections, its response function is leaky leading to signal degradation when layered18. Site-specic recombinases have been employed in genetic circuits as a means to reduce leak3537, but there are a limited number of such enzymes restricting the scalability of this approach. Here, we address these issues, advancing the art of engineering living digital circuits by focusing on two main engineering goals.

First, we built a universal, single-gene NOR logic gate; the NOR gates are functionally complete38 and as such can be composed to implement any logic function. Crucially, the input and output signals of our gates have the same molecular types while still being programmable so that, as in electronics, gates can be wired together. To achieve this, we made use of the CRISPR-dCas9 system: the signals in our framework are guide RNAs (gRNAs) whose sequences specically match up to programmable target sequences on our NOR gate promoters.

Second, we required a consistent OFF state for our NOR gates. To achieve this, we used the chromatin remodelling repression domain Mxi1 to take advantage of the eukaryotic cells ability to repress gene expression, by fusing this domain to dCas9 (ref. 30). The Mxi1 domain is thought to recruit histone deacetylases39,40, and with it we observed strong transcriptional repression in our circuits. The strong and consistent OFF behaviour we observe with our NOR gates is a key factor that allows them to be

a

ri

rj

b c d

pGRRi,j

RGRk

NORi,j,k

GFP GFP

Figure 1 | Schematic of the NOR gate architecture and circuit composition. (a) A NOR gate input stage consists of a Pol II pGRR promoter that is fully repressed by the binding of either one or both of its cognate gRNA-dCas9-Mxi1 complexes. The output stage of the NOR gate is a gRNA transcript, anked by self-cleaving ribozymes (RGR). Cleavage sites are indicated by red arrows. The cleavage of the ribozymes prevents nuclear export of the gRNA, indicated by dotted grey arrow. (b) The process of NOR gate library construction. Our library consists of a set of 400 two-input pGRR promoters and20 RGR outputs for a total of 8,000 possible NOR gates. (c) Genomically integrating NOR gates into S. cerevisiae. (d) Arbitrary circuits are constructed by integrating multiple NOR gates into a single strain.

2 NATURE COMMUNICATIONS | 8:15459 | DOI: 10.1038/ncomms15459 | http://www.nature.com/naturecommunications

Web End =www.nature.com/naturecommunications

NATURE COMMUNICATIONS | DOI: 10.1038/ncomms15459 ARTICLE

composed into larger circuits by minimizing accumulation of transcriptional leak with every added layer. A mathematical model of our NOR gates predicts that they have effectively no transcriptional leak in their OFF states. We show that with low leak there exist parameters that allow our NOR gates to be composed without signicant signal degradation. More importantly, we show experimentally that we can build a variety of digital logic circuits composed of up to ve NOR gates and seven internal gRNA wires, as well as cascades of gates with up to seven layers that still have digital responses according to our specications.

In summary, we developed low-variability single-gene NOR gates that can be regularly interconnected into arbitrary topologies that implement large digital circuits in yeast cells. Neither meticulous characterization of individual parts nor sophisticated design tools were necessary to nd combinations of NOR gates that conferred functional circuits. Because the technology is essentially generic and easy to rewire, it can in principle be used to implement arbitrary internal logic for a variety of synthetic cellular decision-making systems, such as those being explored for diagnostics11,41, therapeutics41,42 and development43,44.

ResultsNOR gate architecture. We built a universal, single-gene logic gate, in our case a NOR gate (Fig. 1a). The NOR gate outputs are then gRNAs that match the target sequences on other NOR gate promoters (Fig. 1b). Our NOR gates are genomically integrated into yeast cells (Fig. 1c). We avoided using RNA polymerase (Pol) III promoters to express gRNAs20,30,31,34 because they have low expression levels relative to Pol II promoters and are more difcult to engineer45,46. By programming the NOR gate input target sequences and output gRNA sequences in a set of gates, we were able to construct a variety of circuit topologies (Fig. 1d).

Second, we required a consistent OFF state for our NOR gates that corresponded to complete or near complete repression of the output promoter (Supplementary Fig. 1). we used the chromatin remodelling repression domain Mxi1 to take advantage of the eukaryotic cells ability to repress gene expression, by fusing this domain to dCas9 (ref. 30) (Fig. 2a). When compared with a number of repression domains, Mxi1 showed the strongest repression (Supplementary Fig. 2). Our results suggest that such repression provides a signicantly improved and more consistent OFF signal compared with repression via steric hindrance (Fig. 2b), in which dCas9 is interfering with transcriptional initiation, but is not remodelling chromatin. A mathematical model of our NOR gates, t to both steady-state and time response data, predicts them have effectively zero transcriptional leak in their OFF states. Additionally, the model predicts that repression via steric hindrance leaks more than repression via dCas9-Mxi1 (Fig. 2b).

Our approach allowed for the construction of the largest eukaryotic gene circuits, to the best of our knowledge, ever demonstrated (Table 1).

The gate NORi,j,k, with input signals ri and rj and output rk, consists of a gRNA-responsive Pol II promoter (pGRRi,j) input

stage, driving an output stage, ribozyme-anked gRNA (RGRk)

(Fig. 1a). According to NOR logic, rk is high only when both ri and rj are low. A signal, ri, is dened as a gRNA complexed with a dCas9-Mix1 fusion protein that confers strong transcriptional repression when bound to DNA30. The gRNA signals are distinguished by their unique 50 guide sequence.

A 20-component library of signals dening r1r20 was used in this work (Supplementary Table 1). The pGRRi,j promoter contains two, 20 base-pair (bp) target sites that match ri and rj

respectively. Since we designed 20 signals, there are 203 8,000

total NOR gates in the set. A NORi,j,k functions as a NOTj,k if the pGRRi,j contains two identical target sites, if the pGRRi,j contains only one target site from the 20 component library (pGRRi,null) or

if ri is simply not used in the circuit. A target sequence of null refers to a pGRR that contains a target sequence that does not match any gRNA used in the containing circuit.

Input stage promoter design. The pGRRi,j promoter is tightly repressed when gRNA-dCas9-Mxi1 is bound to one or both of its two 20 bp target sites. The core region of the pGRRi,j, the minimal

pCYC1 promoter, was chosen based on its successful use with dCas9 in the past32. Because the promoter has relatively low expression levels and we wanted its output to have a strong ON output when not repressed, an upstream activating sequence (UAS) from the strong pGPD promoter47 was added, forming the base pGRR promoter. The UAS increased the unrepressed expression level of the pGRR output by approximately threefold while maintaining the same OFF state expression level in the presence of ri and rj, further separating the digital ON and digital

OFF levels (Supplementary Fig. 3a). A pGRR promoter map highlighting all relevant sequence features is included in Supplementary Fig. 4. A library of 11 pGRRi,j promoters, with i and j chosen from the 20 guide sequences, showed limited expression variability when driving GFP, with an B18% s.d. from the mean (Supplementary Fig. 3b) Of the 20 pGRRi,null:GFP

constructs (i ranging from 1 to 20), 16 were repressed to or near the level of Saccharomyces cerevisiae autouorescence in the presence of the corresponding signal ri (Supplementary Fig. 1).

Output stage RNA design. Two different RNA pol II expression methods were used in this work (Supplementary Fig. 5). The rst was an RGR design utilizing a 50 minimal hammerhead ribozyme (mHH) and a 30 hepatitis delta virus ribozyme (HDV), anking the gRNA48. The second was an insulated RGR (iRGR) with the mHH replaced by an avocado sunblotch viroid (ASBV) ribozyme. Both designs are intended to post-transcriptionally remove nuclear export signals, the 50 cap and 30 poly-A tail49,50. It has been shown that RNA device folding can be insulated from surrounding sequence context through computational sequence selection51,52. Ten guide sequences were chosen for the RGR architecture that were computationally predicted to confer proper folding of the mHH 50 ribozyme. Ten more guide sequences were chosen for the iRGR context whose ASBV 50 ribozyme is predicted to fold properly regardless of guide sequence. We observed similar levels of dCas9-Mxi1-mediated repression with gRNAs expressed from both iRGR and RGR constructs (Supplementary Fig. 6). Interestingly, RGR transcripts lacking a 50 ribozyme also showed dCas9-Mxi1-mediated repression. These results are consistent with previous studies that indicate a majority of 50 extended gRNA target sequences are processed to 20 nucleotides53. No signicant crosstalk was observed when all r110 (RGR design) and r1120 (iRGR design) were paired with all pGRR1-20,null:GFP among noncognate pairs (Fig. 2a and

Supplementary Fig. 7). Out of 20 total RGRs (RGR110 and

iRGR1120) when targeted to their cognate pGRR1-20,null:GFP constructs, 16 repressed uorescence to or near the level of autouorescence for S. cerevisiae (Supplementary Fig. 1).

Logic circuits. As a demonstration of the complex circuits possible with our NOR gates, six two-input, one-output digital logic circuits were built by integrating up to ve NOR gate cassettes into various selectable loci in the yeast genome (Fig. 3af). The output of each circuit was made observable by having the last NOR gate drive the expression of GFP. The

NATURE COMMUNICATIONS | 8:15459 | DOI: 10.1038/ncomms15459 | http://www.nature.com/naturecommunications

Web End =www.nature.com/naturecommunications 3

ARTICLE NATURE COMMUNICATIONS | DOI: 10.1038/ncomms15459

a

1

5

10

15

gRNA

pCONST

RGRi

30,000

24,000

18,000

Fluorescence [a.u.]

pGRRi,null:GFP NOT

i Null

GFP i

pGRR j

UAS

Ti

Null

GFP

12,000

6,000

0

pGRRi,null

20 1 5 15 20

10 gRNAi

Treatment [nM]

b

pGRRi,j

Position 3

30,000

20,000

10,000

30,000

20,000

10,000

Fluorescence [a.u.]

Fluorescence [a.u.]

Position 1 Mxi1 L = 1.7%

Steric L = 61.3%

Position 3 Mxi1 L = 0.0%

Steric L = 25.0%

UAS

Ti

Tj

Position 1

Position 2

tss

0 102 101 100 101 102 103

Treatment [nM]

Fluorescence [a.u.]

30,000

20,000

10,000

Position 2 Mxi1 L = 0.0%

Steric L = 0.0%

0 102 101 100 101 102 103

0 102 101 100 101 102 103

Treatment [nM]

Figure 2 | Orthogonality and repression via dCas9-Mxi1. (a) A constitutive promoter drives expression of gRNAs paired with a combinatorial library of cognate promoters. Orthogonality of the gRNA guide sequences was tested by crossing the 20 pGRRi,null promoters, each expressing GFP, with the 20 gRNAi, creating 400 different strains of yeast. Fluorescence values of each strain were measured using ow cytometry. Fluorescence values from one biological replicate are displayed in the matrix. (b) Dose response curves are shown for repression via dCas9-Mxi1 and dCas9 repression via steric hindrance of pGRR driving GFP at three separate positions in the promoter. The three positions are annotated on the pGRR promoter representation. At all three positions, at maximal induction, dCas9-Mxi1 represses the promoter to a lower uorescence level than dCas9 alone. Model ts predicted the parameter value L, representing transcriptional leak, for all curves. At all three positions the predicted L value is as small or smaller for dCas9-Mix1 than for steric repression. Error bars represent the s.d. of three biological replicates measured over three separate experiments.

circuits were constructed from the 16 guide sequences of the 20-component library that exhibited the strongest repression (Supplementary Fig. 1). The truth table for each gate was experimentally obtained by constructing four separate strains, one for each pair of possible input values, in which the corresponding gRNA input signals were expressed from constitutive promoters (Supplementary Table 2).

We observed uorescence intensity differences in the digital ON and OFF states in various circuits. To distinguish circuit state, value bands for digital ON, OFF and Undened, uorescence values were determined with the 16 guide sequences and their cognate pGRR promoters used in circuit construction (Supplementary Fig. 8). For the state of a circuit to be considered ON or OFF we specied that a majority of cell population fall in the expected uorescence band. Population fraction tables for all circuits can be found in Supplementary Table 3.

Circuits containing different NOR gate variants can exhibit a range of behaviours. For example, 15 versions of the XOR, from Fig. 3e, constructed using different NOR gates exhibited a range of performance (Supplementary Fig. 9). We hypothesize that

circuit performance variations are due to expression differences in the pGRR promoters and repression efciency variations of the gRNA in the individual NOR gates of the circuit.

Cascades. To test the limits of size and complexity our NOR gate circuits can achieve inverter cascades of depth one through seven were composed with NOT gates (Fig. 4a). The cascade of depth D was made by the addition of a NOT gate to repress the input stage of the depth D1 cascade. Each successive addition of a NOT gate inverter resulted in switching the behaviour of the output GFP expression. As seen previously with the two-input logic circuits, there is considerable variability within the ON and OFF states. However, circuits that are expected to exhibit ON or OFF behaviour are clearly distinguishable from one another according to our digital ON and OFF specication. As cascade depth increased the uorescence levels of the OFF states for all of the odd depth cascades increased. Similarly, except for the cascade of depth 6, as cascade depth increased the uorescence levels of the ON states decreased. This suggests a gradual degradation of

4 NATURE COMMUNICATIONS | 8:15459 | DOI: 10.1038/ncomms15459 | http://www.nature.com/naturecommunications

Web End =www.nature.com/naturecommunications

NATURE COMMUNICATIONS | DOI: 10.1038/ncomms15459 ARTICLE

Table 1 | Synthetic circuit size comparison.

Publication No. of gates /parts

No. of connections

Medium

Cascade circuit 7 6 1 9.22 Yes S. cerevisiae Nielsen et al.22 7 6 3 9.22 Yes E. coliQian et al.70 6 5 4 7.81 Yes In vitro XOR circuit 5 4 2 6.40 Yes S. cerevisiae Xie et al.11 5 4 6 6.40 No Mammalian Auslanderet al.71

No. of inputs

Circuit complexity (gates2 connections2)1/2

Functionally complete parts?

5 4 2 6.40 No Mammalian

Regot et al.72 5 3 2 5.83 Yes MulticellularS. cerevisiae

Nissim et al.33 5 3 1 5.83 No Mammalian Stanton et al.19 4 3 2 5 Yes E. coli Nielsen et al.18 3 2 2 3.61 Yes E. coliKiani et al.20 2 2 1 2.83 No Mammalian

The best method for quantifying the size of synthetic biological circuits is an open question. Here we took the largest synthetic circuits constructed in recent publications and compared them with the two

largest circuits from this paper. We separated the inputs to the circuits from internal components. We also counted the number of connections between the internal components. By our denition, a part

is a molecular species that carries information necessary for the internal function of the circuit (as opposed to a helper protein such as cas9). A connection is a molecular interaction between parts that

propagates information within the circuit.

circuit function as the number of layers increased. Similar behaviour was also observed for other repression cascades that were constructed (Supplementary Fig. 10). Alternative versions of 6 gRNA cascades were constructed and showed variability in their levels of ON (Supplementary Fig. 11).

To investigate the temporal characteristics of the inverter cascades, we analysed the kinetics of cascades of depth one through four. A b-estradiol-inducible promoter54 was used to activate transcription of the input gRNA and GFP expression was periodically measured over the course of B30 h of log phase growth (Fig. 4b). With increasing cascade depth, a clear delay in output response was evident, with the cascades reaching half-maximal expression at 4.10.5, 10.81.0, 12.01.2 and17.81.0 h (residual s.d. deviation) for cascades of depth one through four respectively. The dose response curves of the four cascades were also measured after passaging cells over 5 days (Fig. 4c). Consistent with the steady-state cascades, the induction of a gRNA targeting the input of the cascade switched the output of the cascade from OFF to ON (even depth cascades) or from ON to OFF (odd depth cascades). Some signal degradation with successive layers was observed (Fig. 4c), suggesting a limit to the possible depth of the cascades.

Mathematical modelling. A kinetic model was constructed to capture the behaviour of our synthetic cascades. The model combines successive Hill functions to represent simple transcription and repression associated with each gRNA-dCas9-Mxi1 signal. The parameters vd and kd roughly capture expression and repression strengths of the promoters driving each gRNA-dCas9-Mxi1 signal, rd. The parameter L represents the transcriptional leak as a percentage of the maximal expression of a given gate when maximally repressed parameters n and b capture the cooperativity of repression. Degradation/dilution of gRNA-dCas9-Mxi1 signals respectively (Fig. 4d). The steady-state dose response and kinetic time course for inducible cascade data were both t to the model (Fig. 4b,c). Due to the different growth conditions of the steady-state and kinetic cascade experiments, two separate model ts were generated for each experiment. As inducible cascades were built in such a way that they shared many of the same pGRR and gRNA components (Fig. 4b), parameters

for the one-, two-, three- and four-layer cascades were shared between the models and t simultaneously. To address potential model identiability issues parameter values were constrained based on published biological values (Supplementary Table 4). The tting results were found to correlate well with the experimental data. The measured B18% s.d. from the mean for the promoter strength values matches well with the B24% s.d. from the mean of the promoter strength parameters, vd (Supplementary Table 4).

Model ts of the steady-state and time course data predict the transcriptional leak of repression due to dcas9-Mxi1, the value of L, to be effectively zero, L 0.60.1% (s.d.), equivalent to the

production of roughly one transcript every 5 to 10 cell divisions. The reported value of L was calculated as the average of the predicted transcriptional leak from the model ts from Fig. 2b. To demonstrate the ability of dCas9-Mxi1 to decrease transcriptional leak compared with steric repression via dCas9, gRNA dose response curves of repression at three pGRR promoter target site positions were performed using dCas9 and dCas9-Mxi1 (Fig. 2b). At maximal induction, dCas9-Mxi1 represses the promoter to a lower uorescence level than dCas9 alone at all three positions. Repression via steric hindrance showed promoter positional variations in predicted leak parameter values. The observed positional variation is consistent with previous results32. In all three positions dCas9-Mxi1 was predicted to have the same or lower leak parameter L. These data indicate that in the context of our NOR gates, dCas9-Mxi1 confers stronger and more consistent repression than dCas9 alone. Alternative plots comparing dCas9 and dCas9-Mxi1 repression as a function of inducible promoter activation driving gRNA are included in Supplementary Fig. 12.

The temporal responses of the cascades were predicted from simulations using randomly sampled parameters within the range of the model t. Parameter values for kinetic simulations were resampled from the model t using the kinetic time course experimental data. Response times were found to rise linearly (r2 0.83) with increasing circuit depth. Linear regression

analysis estimated the slope of the increase in response time per layer to be equal to 184.90.2 (s.e.m.) min layer 1 (Fig. 5a), consistent with our experimental results. Response delay was found to depend primarily on the degradation/dilution rate b of gRNA-dCas9-Mxi1 (Supplementary Fig. 13) that controls the overall timescale of the dynamics.

NATURE COMMUNICATIONS | 8:15459 | DOI: 10.1038/ncomms15459 | http://www.nature.com/naturecommunications

Web End =www.nature.com/naturecommunications 5

ARTICLE NATURE COMMUNICATIONS | DOI: 10.1038/ncomms15459

a

NOR

OR

AND

NAND

XNOR

XOR

r7

r5

r7

r3

pCONST

pCONST

pCONST

pCONST

pCONST

pCONST

pCONST

pCONST

pCONST

pCONST

+ +

+

+

r5

GFP

103 104 105

Fluorescence [a.u.]

103 104 105

Fluorescence [a.u.]

103 104 105

Fluorescence [a.u.]

103 104 105

Fluorescence [a.u.]

103 104 105

Fluorescence [a.u.]

103 104 105

Fluorescence [a.u.]

b

r3

r6

+ +

+

+

r7

r7

r6

r5

GFP

GFP

c

r2 r1

r10 r2

r10

r2

r1

r10

r2

r2

r10

r5

+ +

+

+

r3

d

Null

+ ++

r7

r1

r5

GFP

GFP

GFP

r3

r2

+

f

r2

r10

r

r1

r2

r10

+ +

+

+

r3

e

r3

r3

r6

r6

r3

r6

r6

r3

r2

pCONST

pCONST

+ ++

+

Figure 3 | NOR gate-based logic circuits. (af) Six different two-input logic circuits constructed by interconnecting NOR gates. For each of the four input possibilities ( , , , and ), a distinct strain was constructed with the corresponding inputs expressed off of constitutive promoters

(for logical ), or not integrated at all (for logical ). Fluorescence values were collected using ow cytometry of cells growing in log phase. The

histograms represent population fraction from three different biological replicates measured during a single experiment and were normalized so that area sums to unity. Fluorescence population ratios of the circuits are included in the Supplementary Table 3.

To extrapolate the model to predict the effect of leak on signal degradation for deeper cascades, cascades of various lengths were simulated, with increasing values of L, using randomly sampled parameter sets within the range of dose response experimental ts. Dynamic range of a cascade length D, rD, was calculated for each cascade. Here dynamic range is dened as the log fold

change of the maximal and minimal response of a cascade,

rD log

max G

min G

. A log-linear relationship was found between rD and D. This relationship was used to calculate the signal degradation, d, representing the percent loss in dynamic range per each additional layer (Fig. 5b).

6 NATURE COMMUNICATIONS | 8:15459 | DOI: 10.1038/ncomms15459 | http://www.nature.com/naturecommunications

Web End =www.nature.com/naturecommunications

NATURE COMMUNICATIONS | DOI: 10.1038/ncomms15459 ARTICLE

a

NOTi,GFP pGRRi,null:GFP

i

GFP

i

null

GFP

GFP

r5 r10

GFP

GFP

GFP

GFP

GFP

GFP

GFP

102.5 103 103.5 104 104.5 105Fluorescence [a.u.]

20,000

15,000

Fluorescence [AU]

10,000

5,000

0 102 101

r5

pCONST

pCONST

r7

r5

r2 r1

r7

r10

r10

r10

r5

r2

r7

r5

r6

r1

r2 r7

r7 r10

r10

r5

r3 r6

r1

r2

r5

pCONST

pCONST

pCONST

pCONST

pCONST

b c

18,000

14,000

Fluorescence [AU]

10,000

6,000

2,000

0 500 1,000 1,500 2,000 2,500

Time [min]

rD =

rd =

d

G L G

100 101 102 103

Treatment [nM]

d

u

Beta estradiol input

d

dth layer

rD

+ Lud

D

Cascade length

rd

gRNA signal at dth layer

Ud

Expression strength at dth layer

n

rd

kd

Repression strength at dth layer

n

Cooperativity coefficient

b

Degradation/dilution of gRNA signal

B

Degradation/dilution of GFP

G

Arbitrary fluorescence units

L

Transcriptional leak at maximal repression

rD

Input gRNA signal

V

Max expression level of input promtoer

K

Michaelis constant for input promoter

Figure 4 | Repression cascade characterization. (a) Repression cascades of one to seven gRNAs. Cascades were created with sequential genomic integrations of NOT gates. The nal output of each cascade is a NOT gate that expresses GFP. Each NOT gate represses the output of a subsequent NOT gate. Cascades with an even number of layers express a high level of GFP, creating a digital ON output, and odd depth cascades express low levels of GFP, creating a digital OFF output. Fluorescence measurements were taken using ow cytometry. The histograms represent population fraction from three different biological replicates measured during a single experiment and were normalized so that area sums to unity. Fluorescence population ratios of the circuits are included in Supplementary Table 3. (b) Temporal dynamics for cascades of one to four gRNAs. Expression of the input gRNA was induced with b-estradiol. A model of the cascade, in which each layer is treated as a Hill function, was used to t the data. The plot shows the data from one biological replicate. As the number of layers in the cascade increases, signal degradation and increased time to steady state is observed. (c) The steady-state response function for the four inducible cascades. Error bars represent the s.d. of three biological replicates measured over three separate experiments. (d) A representation of the model. The model was used to generate the ts for the steady-state and kinetic inducible cascade experiments.

Signal degradation was found to be largely dependent on the transcriptional leak parameter, L (Fig. 5b and Supplementary Fig. 12). As leak increases, d, on average, increases. At values of

L 480%, the median value of d trends to B80%. At values of L o1.75%, the spread of performance of the cascades is signicantly larger. In this range the performance of the cascade is more sensitive to other parameters in the model. Our estimate of leak from the dose response experiments, L 0.60.1% (s.d.),

falls within the sensitive range, indicating the importance of utilizing well-performing NOR gates in large circuits built using

our architecture. In addition, these data show the signicance of reducing NOR gate leak when constructing larger circuits.

DiscussionWe introduced a class of dCas9-based modular genetic NOR gates that behave digitally, have low variability and show minimal retroactivity or effects on cell growth. These features made these gates relatively easy to combine into Boolean logic circuits that are among the largest ever built in any organism. In particular, we

NATURE COMMUNICATIONS | 8:15459 | DOI: 10.1038/ncomms15459 | http://www.nature.com/naturecommunications

Web End =www.nature.com/naturecommunications 7

ARTICLE NATURE COMMUNICATIONS | DOI: 10.1038/ncomms15459

a b

5,000

100%

Signal degradation [afii9829]

75% 50% 25%

0%

1.75% 12.25% 22.75% 33.25% 43.75%

Leak % L bin size = 3.5%

4,000 3,000

Time to half max

[mins]

2,000 1,000

0

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

Layer depth

54.25% 64.75%

Figure 5 | Model predictions and analysis of repression cascades. (a) Simulations of time to half-maximal response using the model. Increasingly layered cascades show a positive linear relationship between circuit time to half-maximal response and circuit depth, with a slope of 184.90.2 (s.e.m.) min layer 1.

The rst four data points highlighted in purple are experimental data from Fig. 4b. (b) Signal degradation, d, in a cascade increases as transcriptional leak of the gates increase. Boxplots of d values were plotted with binned values of the leak parameter L. At values of L o1.75% the spread of performance of the cascades is signicantly larger. The bin containing the steady-state experimentally predicted value of dCas9-Mxi1, L 0.60.1% (s.d.), is highlighted in purple. The bins

highlighted in orange and yellow contain the predicted L values for the steric repression measurements in Fig. 2 of position 1, L 25.0%, and position 3,

L 61.3%, respectively.

found that most circuits in Figs 3 and 4 required that only a handful of gate combinations be screened to identify a functional design, and others required only one.

Table 1 compares our technology with selected published circuits. We measured circuit complexity with a combination of two metrics: the number of gates and the number of connections among gates, allowing us to locate circuits in a two-dimensional plot (Supplementary Fig. 14). We can calculate a complexity score using the two metrics, complexity (gates2 connections2)1/2.

For example, the XOR gate had ve gates and four connections, producing a complexity of (52 42)1/2 6.4, while the cascade

has a complexity of (72 12)1/2 9.2. These complexities

compare well with gene circuits developed in Escherichia coli, for example. Our NOR gates enabled extremely simple design and construction of large gene circuits. Before genetic circuits can be made much larger, however, many factors that inuence the size and complexity of synthetic genetic circuits must be addressed.

First, the gates in any framework must be well behaved. Gates can suffer from retroactivity, where a downstream gate affects the behaviour of upstream gates to which it is not connected by design5557. In this case it is quite difcult to design large circuits even with CAD because we may not know the source of the retroactivity, how to model it or how to design with it. In addition, gates can be highly variable, where the outputs levels of one gate do not match the input levels of the next. Electrical engineers call this an impedance mismatch. A recent paper22 addressed retroactivity by adding insulators to their gates. By meticulously characterizing the performance each gate, and using CAD, they were able to select compatible subsets of parts out of which they constructed circuits as large as those demonstrated here, despite gate variability. Not all of the circuits predicted to work by the CAD tool functioned correctly, possibly due to residual retroactive effects, requiring the circuits to be screened for function. In contrast, our gates are considerably less variable and do not seem to be confounded by retroactive effects, at least in circuits with complexities o9.0. In such a case and when circuit sizes are small (o20 components) circuits are easy to design by hand since any subset of components from a library is likely to yield a functional circuit. Thus, in our case, the design problem is easy enough that extensive part characterization and CAD tools were not necessary at the circuit level (even though CAD tools such as standard DNA editors and secondary structure predictors for RNA were used at the sequence level).

Second, the host organism presents many unique challenges. Each organism can be thought of as a different computer operating system. Promoters, for example, in E. coli are B60 bp

of DNA long, and transcriptional regulation is a fairly well-understood process58. In contrast, the size of promoter and regulatory regions vary widely and can range from 250 bp to 10 kb in yeast and other eukaryotes. Transcriptional regulation in eukaryotes is complex, involving a variety of mechanisms including chromatin remodelling5963, and understanding it remains a highly active area of research64. Therefore, unfortunately, any genetic circuit technology designed for one kingdom of life is unlikely to be easily ported to another, especially those built on transcriptional or translational processes. Thus, directly comparing circuit architectures between organisms, as we did between yeast and E. coli in Table 1, is difcult. Nevertheless, we believe that because CRISPR-dCas9 functions in mammalian cells20,3032,34,48, and the human Mxi1 repression domain has been used in synthetic contexts to regulate transcription in human cells30,39,40, our NOR gates could be ported into mammalian cells, with difculties of strain engineering likely dominating.

Third, the method by which circuits are constructed and the genetic tractability of the host affects progress toward building large circuits. For example, the circuits we present here are all singly integrated into the yeast genome, because plasmid-based systems exhibit cell-to-cell variation in copy number. That made the process of building and testing strains slow, costly and cumbersome and in fact limited our ability to build circuits much larger than those shown here. Larger circuits and large libraries of circuit variants will require that we develop, for example, one-pot assembly methods for large DNA constructs65. Depending on the technology, such assemblies may be more or less difcult to harness. For example, our circuits currently benet from the fact that the gates are integrated into disparate genetic locations that decreases the possibility of interference between gates due to chromatin remodelling62,66 and of yeasts tendency to recombine nearby homologous regions67.

The success or failure of different approaches to building bigger circuits may depend on how well behaved, insulated, simple and scalable the input low-level devices and gates are. In addition, relaxing the requirement that circuits be digital, so that analogue or mixed analogue/digital circuits can be used when appropriate, will likely open up the design space, further increasing the size of the circuits we can build so that one day they can match the size and performance of natural genetic circuits.

Methods

Construction of yeast strains. Yeast transformations were carried out using a standard lithium acetate protocol68. Yeast cells were made competent by growing

8 NATURE COMMUNICATIONS | 8:15459 | DOI: 10.1038/ncomms15459 | http://www.nature.com/naturecommunications

Web End =www.nature.com/naturecommunications

NATURE COMMUNICATIONS | DOI: 10.1038/ncomms15459 ARTICLE

50 ml cultures in rich media to log growth phase, then spinning down the cells and washing with H20. Next, linearized DNA, salmon sperm donor DNA, 50%

polyethylene glycol and 1 M LiOAc were combined with 50 ml of competent cells and the mixture was heat shocked at 42 C for 15 min. The cells were then spun down, supernatant was removed and they were resuspended in H2O and then plated on selective agar media. Transformations were done into MATa W303-1A and MATalpha W303-1B background strains. Matings of the MATa and MATalpha were performed by coculturing both mating types and plating the culture onto selective agar media. All strains and sequences used in this work are detailed in the Supplementary Data 1.

RNA design. RGR and iRGR sequences were computationally designed to enable the 50 hammerhead ribozymes to fold into their target, functionally active, structures. ViennaRNA (RNAfold 2.1.9) was used to simulate long timescale (thermodynamic equilibrium) at an input temperature of 37 C. Kinefold (kinefold_long_static_bianary 20060404) was used to simulate short timescale folding (cotranscriptional folding) with inputs of low and high polymerization rates of 25 and 50 nt s 1 respectively, helix minimum free energy 6.346 kcal mol 1

and folded without pseudoknots or entanglements. A total of 12 Kinefold simulations were run for each candidate sequence and agglomerated to generate average folding trace data.

Ribozyme target structures needed for both viennaRNA and Kinefold simulation evaluation were determined by folding ribozyme sequences (Minimal HH: 50- NNNNNNCTGATGAGTCCGTGAGGACGAAACGAGTAAGCTCGT

CNNNNNN-30 ASBV1: 50-GGGACGGGCCATCATCTATCCCTGAAGAGAC GAAGGCTTCGGCCAAGTCGAAACGGAAACGTCGGATAGTCGCCCGTCCC-30) using RNAfold and Kinefold (melt and anneal of 1 min), respectively.

RGR targeting sequences and iRGR insulating sequences were screened in specic 50 promoter contexts (pGAL1min: 50-AGTATCAACAAAAAATTGTTAATAT

ACCTCTATACT TTAACGTCAAGGAGAAAAAACTATACGGATTCTAGAACTAGTGGATCTACAAA-30, pAHD1: 50-CAAGCTATACCAAGCATACA

ATCAACTATCTCATATACAGGATTCTAGAA CTAGTGGATCTACAAA-30,

pCYC1: 50-ACTATACTTCTATAGACACACAAACACAAATACACACACTAATCTAGATATTGGATTCT AGAACTAGTGGATCTACAAA-30) and in the 30 context of the targeting sequence and the gRNA handle sequence (gRNA handle: 50-GTTTTAGAGCTAGAAATAGCAAGTTAAAATAAGGCTAGTCCGTTATCAACTTGAAAAAG TGGCACCGAGTCGGTGCTTTT-30).

Randomly generated 20 bp candidate targeting sequences for RGR, of which the most 50 6 bp dened the closing stem of the minimal HH ribozyme, were folded in the context of each promoter to conrm that the target structure was present in the MFE structure (viennaRNA) and that the target structure was present at 490% in the RNA folding trace at both low and high polymerase rates (Kinefold). Targeting sequences that enabled correct folding in the context of each promoter were considered successful. For iRGRs, randomly generated 50 and 30 insulating sequences were designed for each of the three promoter types and were screened for function in the same manner. However, to select for the most robust insulating sequences, each was screened against 75 randomly generated and 10 randomly generated 20 bp guide sequences using viennaRNA and Kinefold, respectively.

Cytometry. Fluorescence intensity was measured with a BD Accuri C6 ow cytometer equipped with a CSampler plate adapter using excitation wavelengths of 488 and 640 nm and an emission detection lter at 533 nm (FL1 channel). A total of 10,000 events above a 400,000 FSC-H threshold (to exclude debris) were recorded for each sample with and core size of 22 mm using the Accuri C6 CFlow Sampler software. Cytometry data were exported as FCS 3.0 les and processed using the owCore R software package and custom R scripts (Supplementary Software 1) to obtain the mean FL1-A value at each data point.

Data collection for orthogonality matrix. Cytometry readings were taken with cultures inoculated into synthetic complete with cells from freshly struck out on agar. Colonies were picked from plates and grown for 3 h at 30 C before reads were taken.

Data collection for logic circuits and static cascades. Cytometry measurements were taken on cells grown in cultures diluted 1:1,000 from saturated culture for 16 h at 30 C.

Data collection for inducible cascades. Cells from saturated culture were diluted 1:100 into fresh media with a Beta Estradiol (be) concentration of 100 nm. Cytometry measurements were taken over an B30 h period. During the time course, cells were periodically diluted to keep them in log growth phase. Experimental data collected for steady state were measured for four strains, each containing four different be-inducible cascades. Each of the four strains was induced with 18 different doses of be ranging from 0 to 100 mM in a single batch of 72 cultures. Cells were diluted every 815 h to prevent culture saturation. Steady-state uorescence readings were taken after 5 days when the cultures were in log phase.

Model description. A deterministic model of our system was described by three ordinary differential equations characterizing transcription, degradation and repression. The gRNA-dCas9-Mxi1 and green uorescent protein (GFP) molecular constituents were modelled as follows:

drddt b

vd 1 L

1

r

0

k

n

Lvd rd

1

A

drDdt b

V uK

n

1

u K

n

@ ! d 2 1 . . . D 1

f g

rD

dGdt B

1 L

1 r1

n

;

L G

rd is the concentration of the dth gRNA-dCas9-Mxi1, d ranges from 1 to D 1,

where D is the number of layers in the cascade; rD is the input gRNA driven by the inducible promoter; vd is the promoter strength driving each rd in terms of the maximum steady-state concentration of gRNA from the promoter; G is the measurable normalized concentration of GFP; b is the degradation/dilution rate of all rd; B is the degradation/dilution for GFP; kd is the repression strength of rd to its cognate promoter, in terms of the number of repressors required to suppress a promoter to half strength; to its cognate promoter is modelled with kd, the number of repressors required to suppress a promoter to half-strength; and n is a Hill coefcient. For the transfer function, V, K, nu respectively represent the maximum transcription, MichaelisMenten constant and Hill coefcient of the inducible promoter; u is the input be in mM. Concentration is rescaled as the Michaelis

Menten constant or the number of gRNAs required to suppress a NOT gate to half-maximal. Note that the model makes the assumptions that (1) there is no crosstalk between gRNA components, (2) Mxi1 represses transcription completely with no transcriptional leak and (3) dCas9-Mxi1 bind quickly and irreversibly to gRNA.

Fitting procedure. Parameters were optimized using differential evolution followed by minimization using the BFGS (BroydenFletcherGoldfarbShanno) algorithm69. For the steady-state experiments, optimal parameter ts for the parameters v0ss v3ss, k0ss k3ss, Vss, nss were generated from three separate

experiments. For each of the three experiments, 17 parameter ts were generated using differential evolution/BFGS and means were calculated for a total of 51 steady-state parameter sets. The means from each experiment were used to determine the experimental error (s) for estimating each parameter (Supplementary Table 4). For the kinetics experiments, ve parameter ts for v0kinetics v3kinetics, k0kinetics k3kinetics, b, B, Vkinetics, nkinetics were generated from a

single experiment (Supplementary Table 4). As there were only data for a single kinetics experiment, experimental errors for the kinetic parameter values were not calculated. Parameters K and nu were determined in a separate experiment by driving a YFP with the pGALZ4 b-estradiol inducible; this promoter is the same promoter used in the inducible cascades. The kinetics and steady-state parameter sets were resampled in downstream analyses to generate Monte Carlo simulations of longer repression cascades (Supplementary Software 1).

Model predictions. Long repression cascades of 1 to 11 (D A {1 y 11}) layers were simulated using the system of ordinary differential equations. Parameters for simulated cascades were generated by resampling parameter sets generated during the tting procedure. For the kinetic model predictions, 10,000 simulated cascades were generated by resampling parameters from 5 parameter sets estimated from the kinetics experiment. The time-to-half max of GFP (G) was calculated for each cascade length D and plotted in Fig. 5a. For the signal degradation (d) predictions in Fig. 5b, 100,000 simulated cascades of length D 7 were simulated by resam

pling parameters from the 51 parameter sets estimated from the 3 steady-state experiments. To compare L versus d, L was sampled from a uniform distribution between 0 and 1. Signal degradation (d) was calculated as the percent change in dynamic range per additional layer. The dynamic range at each layer d in a cascade of length D was calculated as:

rd log

max rd

min rd

Dynamic range was found to have a log-linear relationship with the length of the cascade, and hence the average slope between d versus log(rd) was calculated using linear regression for each of the 100,000 simulations of cascades of length D by:

Z

D

Pd

d log rd

Plog rd

D

Pd 2;with D 7. With Z being the change in log(rd) with each additional layer, the

percent loss in dynamic range per layer or signal degradation d is calculated as

d 1 10n:

Values for L were binned using a bin size of 0.035 and d versus L was plotted to generate Fig. 5b.

d

2

NATURE COMMUNICATIONS | 8:15459 | DOI: 10.1038/ncomms15459 | http://www.nature.com/naturecommunications

Web End =www.nature.com/naturecommunications 9

ARTICLE NATURE COMMUNICATIONS | DOI: 10.1038/ncomms15459

Data availability. No data sets were generated during the current study. All data values supporting the experimental conclusions are shown either in main or Supplementary Figures (source data and DNA are available from corresponding author). A list of strains and sequences used for plasmids constructed are included in Supplementary Data 1. Custom software used in this work is available in Supplementary Software 1.

References

1. Shmulevich, I., Dougherty, E. R. & Zhang, W. E. I. in Proceedings of the IEEE90.11, 17781792 (2002).2. Watterson, S., Marshall, S. & Ghazal, P. Logic models of pathway biology. Drug Discov. Today 13, 447456 (2008).

3. Hinkelmann, F. & Laubenbacher, R. Boolean models of bistable biological systems. arXiv preprint arXiv:0912.2089 (2009).

4. Yuh, C. H., Bolouri, H. & Davidson, E. H. Cis-regulatory logic in the endo16 gene: switching from a specication to a differentiation mode of control. Development 128, 617629 (2001).

5. Buchler, N. E., Gerland, U. & Hwa, T. On schemes of combinatorial transcription logic. Proc. Natl Acad. Sci. USA 100, 51365141 (2003).

6. Flames, N. & Hobert, O. Gene regulatory logic of dopamine neuron differentiation. Nature 458, 885889 (2009).

7. Hobert, O. Common logic of transcription factor and microRNA action. Trends Biochem. Sci. 29, 462468 (2004).

8. Bernot, G., Comet, J.-P., Richard, A. & Guespin, J. Application of formal methods to biological regulatory networks: extending Thomas asynchronous logical approach with temporal logic. J. Theor. Biol. 229, 339347 (2004).

9. Church, G. M., Elowitz, M. B., Smolke, C. D., Voigt, C. A. & Weiss, R. Realizing the potential of synthetic biology. Nat. Rev. Mol. Cell Biol. 15, 289294 (2014).

10. Roybal, K. T. et al. Engineering T cells with customized therapeutic response programs using synthetic notch receptors. Cell 167, 419432.e16 (2016).

11. Xie, Z., Wroblewska, L., Prochazka, L., Weiss, R. & Benenson, Y. Multi-input RNAi-based logic circuit for identication of specic cancer cells. Science 333, 13071311 (2011).

12. Lee, E. J., Tabor, J. J. & Mikos, A. G. Leveraging synthetic biology for tissue engineering applications. Inamm. Regen. 34, 1522 (2014).

13. Guye, P. et al. Genetically engineering self-organization of human pluripotent stem cells into a liver bud-like tissue using Gata6. Nat. Commun. 7, 10243 (2016).

14. Lucks, J. B., Qi, L., Mutalik, V. K., Wang, D. & Arkin, A. P. Versatile RNA-sensing transcriptional regulators for engineering genetic networks. Proc. Natl Acad. Sci. USA 108, 86178622 (2011).

15. Tamsir, A., Tabor, J. J. & Voigt, C. A. Robust multicellular computing using genetically encoded NOR gates and chemical wires. Nature 469, 212215 (2011).

16. Moon, T. S., Lou, C., Tamsir, A., Stanton, B. C. & Voigt, C. A. Genetic programs constructed from layered logic gates in single cells. Nature 491, 249253 (2012).

17. Siuti, P., Yazbek, J. & Lu, T. K. Synthetic circuits integrating logic and memory in living cells. Nat. Biotechnol. 31, 448452 (2013).

18. Nielsen, A. A. K. & Voigt, C. A. Multi-input CRISPR/Cas genetic circuits that interface host regulatory networks. Mol. Syst. Biol. 10, 763 (2014).

19. Stanton, B. C. et al. Genomic mining of prokaryotic repressors for orthogonal logic gates. Nat. Chem. Biol. 10, 99105 (2014).

20. Kiani, S. et al. CRISPR transcriptional repression devices and layered circuits in mammalian cells. Nat. Methods 11, 723726 (2014).

21. Didovyk, A. et al. Orthogonal modular gene repression in Escherichia coli using engineered CRISPR-Cas9. ACS Synth. biol. 5, 8188 (2016).

22. Nielsen, A. A. K. et al. Genetic circuit design automation. Sci. 352, aac7341 (2016).

23. Rinaudo, K. et al. A universal RNAi-based logic evaluator that operates in mammalian cells. Nat. Biotechnol. 25, 795801 (2007).

24. Klug, A. The discovery of zinc ngers and their development for practical applications in gene regulation and genome manipulation. Q. Rev. Biophys. 43, 121 (2010).

25. Zhang, F. et al. Efcient construction of sequence-specic TAL effectors for modulating mammalian transcription. Nat. Biotechnol. 29, 149153 (2011).

26. Gaber, R. et al. Designable DNA-binding domains enable construction of logic circuits in mammalian cells. Nat. Chem. Biol. 10, 203208 (2014).

27. Joung, J. K. & Sander, J. D. TALENs: a widely applicable technology for targeted genome editing. Nat. Rev. Mol. Cell Biol. 14, 4955 (2013).

28. Boch, J. et al. Breaking the code of DNA binding specicity of TAL-type III effectors. Science 326, 15091512 (2009).

29. Ramirez, C. L. et al. Unexpected failure rates for modular assembly of engineered zinc ngers. Nat. Methods 5, 374375 (2008).

30. Gilbert, L. A. et al. CRISPR-mediated modular RNA-guided regulation of transcription in eukaryotes. Cell 154, 442451 (2013).

31. Larson, M. H. et al. CRISPR interference (CRISPRi) for sequence-specic control of gene expression. Nat. Protoc. 8, 21802196 (2013).

32. Farzadfard, F., Perli, S. D. & Lu, T. K. Tunable and multifunctional eukaryotic transcription factors based on CRISPR/Cas. ACS Synth. Biol. 2, 604613 (2013).

33. Nissim, L., Perli, S. D., Fridkin, A., Perez-pinera, P. & Lu, T. K. Resource multiplexed and programmable regulation of gene networks with an integrated RNA and CRISPR/Cas toolkit in human cells. Mol. Cell 54, 698710 (2014).

34. Qi, L. S. et al. Repurposing CRISPR as an RNA-guided platform for sequence specic control of gene expression. Cell 152, 11731183 (2013).

35. Friedland, A. E. et al. Synthetic gene networks that count. Science 324, 11991202 (2009).

36. Lapique, N. & Benenson, Y. Digital switching in a biosensor circuit via programmable timing of gene availability. Nat. Chem. Biol. 10, 10201027 (2014).

37. Bowyer, J. et al. Mechanistic modeling of a rewritable recombinase addressable data module. IEEE Trans Biomed Circuits Syst. Cell 10, 11611170 (2016).

38. Nelson, V. P., Nagle, H. T., Carroll, B. D. & Irwin, J. D. Digital Logic Circuit Analysis and Design (Prentice-Hall, 1995).

39. Schreiber-Agus, N. et al. An amino-terminal domain of Mxi1 mediates anti-Myc oncogenic activity and interacts with a homolog of the yeast transcriptional repressor SIN3. Cell 80, 777786 (1995).

40. Lee, T. C. & Ziff, E. B. Mxi1 is a repressor of the c-myc promoter and reverses activation by USF. J. Biol. Chem. 274, 595606 (1999).

41. Shankar, S. & Pillai, M. R. Translating cancer research by synthetic biology. Mol. Biosyst. 7, 18021810 (2011).

42. Ye, H., Aubel, D. & Fussenegger, M. Synthetic mammalian gene circuits for biomedical applications. Curr. Opin. Chem. Biol. 17, 910917 (2013).

43. Marson, A. et al. Connecting microRNA genes to the core transcriptional regulatory circuitry of embryonic stem cells. Cell 134, 521533 (2008).

44. Warren, L. et al. Highly efcient reprogramming to pluripotency and directed differentiation of human cells with synthetic modied mRNA. Cell Stem Cell 7, 618630 (2016).

45. Huang, Y. & Maraia, R. J. Comparison of the RNA polymerase III transcription machinery in Schizosaccharomyces pombe, Saccharomyces cerevisiae and human. Nucleic Acids Res. 29, 26752690 (2001).

46. Blazeck, J., Garg, R., Reed, B. & Alper, H. S. Controlling promoter strength and regulation in Saccharomyces cerevisiae using synthetic hybrid promoters. Biotechnol. Bioeng. 109, 28842895 (2012).

47. Sun, J. et al. Cloning and characterization of a panel of constitutive promoters for applications in pathway engineering in Saccharomyces cerevisiae. Biotechnol. Bioeng. 109, 20822092 (2012).

48. Gao, Y. & Zhao, Y. Self-processing of ribozyme-anked RNAs into guide RNAs in vitro and in vivo for CRISPR-mediated genome editing. J. Integr. Plant Biol. 56, 343349 (2014).

49. Lewis, J. D. & Izaurralde, E. The role of the cap structure in RNA processing and nuclear export. Eur. J. Biochem. 247, 461469 (1997).

50. Dunn, E. F., Hammell, C. M., Hodge, C. A. & Cole, C. N. Yeast poly(A)-binding protein, Pab1, and PAN, a poly(A) nuclease complex recruited by Pab1, connect mRNA biogenesis to export. Genes Dev. 19, 90103 (2005).51. Cambray, G. et al. Measurement and modeling of intrinsic transcription terminators. Nucleic Acids Res. 41, 51395148 (2013).

52. Carothers, J. M. et al. Model-driven engineering of RNA devices to quantitatively program gene expression. Sci. 334, 17161719 (2011).

53. Ran, F. A. et al. Double nicking by RNA-guided CRISPR Cas9 for enhanced genome editing specicity. Cell 154, 13801389 (2013).

54. McIsaac, R. S. et al. Synthetic gene expression perturbation systems with rapid, tunable, single-gene specicity in yeast. Nucleic Acids Res. 41, e57e57 (2013).

55. Del Vecchio, D., Ninfa, A. J. & Sontag, E. D. Modular cell biology: retroactivity and insulation. Mol. Syst. Biol. 4, 161 (2008).

56. Jayanthi, S., Nilgiriwala, K. S. & Del Vecchio, D. Retroactivity controls the temporal dynamics of gene transcription. ACS Synth. Biol. 2, 431441 (2013).

57. Mishra, D., Rivera, P. M., Lin, A., Del Vecchio, D. & Weiss, R. A load driver device for engineering modularity in biological networks. Nat. Biotech. 32, 12681275 (2014).

58. Blazeck, J. & Alper, H. S. Promoter engineering: recent advances in controlling transcription at the most fundamental level. Biotechnol. J. 8, 4658 (2013).

59. Trifonov, E. N. Cracking the chromatin code: precise rule of nucleosome positioning. Phys. Life Rev. 8, 3950 (2011).

60. Rando, O. J. & Winston, F. Chromatin and transcription in yeast. Genetics 190, 351387 (2012).

61. Keung, A. J., Joung, J. K., Khalil, A. S. & Collins, J. J. Chromatin regulation at the frontier of synthetic biology. Nat. Rev. Genet. 16, 159171 (2015).62. Keung, A. J., Bashor, C. J., Kiriakov, S., Collins, J. J. & Khalil, A. S. Using targeted chromatin regulators to engineer combinatorial and spatial transcriptional regulation. Cell 158, 110120 (2014).

63. Jiang, C. & Pugh, B. F. Nucleosome positioning and gene regulation: advances through genomics. Nat. Rev. Genet. 10, 161172 (2009).

64. Rajkumar, A. S., Denervaud, N. & Maerkl, S. J. Mapping the ne structure of a eukaryotic promoter input-output function. Nat. Genet. 45, 12071215 (2013).

10 NATURE COMMUNICATIONS | 8:15459 | DOI: 10.1038/ncomms15459 | http://www.nature.com/naturecommunications

Web End =www.nature.com/naturecommunications

NATURE COMMUNICATIONS | DOI: 10.1038/ncomms15459 ARTICLE

65. Werner, S., Engler, C., Weber, E., Gruetzner, R. & Marillonnet, S. Fast track assembly of multigene constructs using Golden Gate cloning and the MoClo system. Bioengin. Bugs 3, 3843 (2012).

66. Naumova, N., Smith, E. M., Zhan, Y. & Dekker, J. Analysis of long-range chromatin interactions using Chromosome Conformation Capture. Methods 58, 192203 (2012).

67. Shinohara, A. & Ogawa, T. Homologous recombination and the roles of double-strand breaks. Trends Biochem. Sci. 20, 387391 (1995).

68. Gietz, R. D. & Woods, R. A. Transformation of yeast by lithium acetate/single-stranded carrier DNA/polyethylene glycol method. Methods Enzymol. 350, 8796 (2002).

69. Storn, R. & Price, K. Differential evolutiona simple and efcient heuristic for global optimization over continuous spaces. J. Glob. Optim. 11, 341359 (1997).

70. Qian, L. & Winfree, E. Scaling up digital circuit computation with DNA strand displacement cascades. Science 332, 11961201 (2011).

71. Auslander, S. et al. Programmable single-cell mammalian biocomputers. Nature 487, 123127 (2012).

72. Regot, S. et al. Distributed biological computation with multicellular engineered networks. Nature 469, 207211 (2011).

Acknowledgements

Michelle Parks and the Klavins Lab technicians helped build strains and performed experimental assays. The computational work was facilitated through the use of the Hyak supercomputer system at the University of Washington. This research is funded in part by a grant from the Semiconductor Research Corporation and NSF Grant Number 1317653. J.M.C. was a fellow of the Alfred P. Sloan Foundation. W.E.V. and J.M.C. were supported in part by funds from the University of Washington and an NSF Award MCB 1517052.

Author contributions

M.W.G. and E.K. wrote the manuscript with contributions from all authors. M.W.G. and J.D.V. designed all experiments and performed data collection. J.D.V. developed and analysed the mathematical model. W.E.V. performed model parameter sensitivity analysis. W.E.V. and J.M.C. performed all RNA design work.

Additional information

Supplementary Information accompanies this paper at http://www.nature.com/naturecommunications

Web End =http://www.nature.com/ http://www.nature.com/naturecommunications

Web End =naturecommunications

Competing interests: The authors declare no competing nancial interests.

Reprints and permission information is available online at http://npg.nature.com/reprintsandpermissions/

Web End =http://npg.nature.com/ http://npg.nature.com/reprintsandpermissions/

Web End =reprintsandpermissions/

How to cite this article: Gander, M. W. et al. Digital logic circuits in yeast with CRISPR-dCas9 NOR gates. Nat. Commun. 8, 15459 doi: 10.1038/ncomms15459 (2017).

Publishers note: Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional afliations.

This work is licensed under a Creative Commons Attribution 4.0 International License. The images or other third party material in this article are included in the articles Creative Commons license, unless indicated otherwise in the credit line; if the material is not included under the Creative Commons license, users will need to obtain permission from the license holder to reproduce the material. To view a copy of this license, visit http://creativecommons.org/licenses/by/4.0/

Web End =http://creativecommons.org/licenses/by/4.0/

r The Author(s) 2017

NATURE COMMUNICATIONS | 8:15459 | DOI: 10.1038/ncomms15459 | http://www.nature.com/naturecommunications

Web End =www.nature.com/naturecommunications 11