Full Design Au oma ion o Mul i-S a e RNA De ices o
P og am Gene Exp ession Using Ene gy-Based
Op imiza ion
Guille mo Rod igo
1.
, Thomas E. Land ain
1.
, Esz e Maje
2
, Jose
´-An onio Da o
`s
2
, Al onso Ja amillo
1
*
1Ins i u e o Sys ems and Syn he ic Biology, CNRS UPS 3509 – Uni e si e
´d’E
´ y Val d’Essonne – Genopole, E
´ y, F ance, 2Ins i u o de Biologı
´a Molecula y Cellula de
Plan as, CSIC – Uni e sidad Poli e
´cnica de Valencia, Valencia, Spain
Abs ac
Small RNAs (sRNAs) can ope a e as egula o y agen s o con ol p o ein exp ession by in e ac ion wi h he 59un ansla ed
egion o he mRNA. We ha e de eloped a physicochemical amewo k, elying on base pai in e ac ion ene gies, o design
mul i-s a e sRNA de ices by sol ing an op imiza ion p oblem wi h an objec i e unc ion accoun ing o he s abili y o he
ansi ion and inal in e molecula s a es. Con a y o he analysis o he eac ion kine ics o an ensemble o sRNAs, we sol e
he in e se p oblem o inding sequences sa is ying a ge ed eac ions. We show he e ha ou objec i e unc ion co ela es
well wi h measu ed ibo egula o y ac i i y o a se o mu an s. This has enabled he applica ion o he me hodology o an
ex ended design o RNA de ices wi h speci ied beha io , assuming di e en molecula in e ac ion models based on
Wa son-C ick in e ac ion. We designed se e al YES, NOT, AND, and OR logic ga es, including he design o combina o ial
ibo egula o s. In sum, ou de no o app oach p o ides a new pa adigm in syn he ic biology o design molecula in e ac ion
mechanisms acili a ing u u e high- h oughpu unc ional sRNA design.
Ci a ion: Rod igo G, Land ain TE, Maje E, Da o
`s J-A, Ja amillo A (2013) Full Design Au oma ion o Mul i-S a e RNA De ices o P og am Gene Exp ession Using
Ene gy-Based Op imiza ion. PLoS Compu Biol 9(8): e1003172. doi:10.1371/jou nal.pcbi.1003172
Edi o : Adam P. A kin, Law ence Be keley Na ional Labo a o y, Uni ed S a es o Ame ica
Recei ed No embe 3, 2012; Accep ed June 21, 2013; Published Augus 1, 2013
Copy igh : ß2013 Rod igo e al. This is an open-access a icle dis ibu ed unde he e ms o he C ea i e Commons A ibu ion License, which pe mi s
un es ic ed use, dis ibu ion, and ep oduc ion in any medium, p o ided he o iginal au ho and sou ce a e c edi ed.
Funding: Wo k suppo ed by he g an s FP7-ICT-043338 (BACTOCOM) o AJ, and BIO2011-26741 (Minis e io de Economı
´a y Compe i i idad, Spain) o JAD. GR is
suppo ed by an EMBO long- e m ellowship co- unded by Ma ie Cu ie ac ions (ALTF-1177-2011), and TEL by a PhD ellowship om he AXA Resea ch Fund. The
unde s had no ole in s udy design, da a collec ion and analysis, decision o publish, o p epa a ion o he manusc ip .
Compe ing In e es s: The au ho s ha e decla ed ha no compe ing in e es s exis .
* E-mail: al onso.ja [email protected].
.These au ho s con ibu ed equally o his wo k.
In oduc ion
Small non-coding RNA (sRNA) has aised a big in e es because
o he p edic abili y and modula i y o i s binding wi h a la ge
a ie y o molecules and mac omolecules [1]. Gi en his unc ional
po en ial, he use o sRNAs o con ol p o ein exp ession has
igge ed a new way o enginee in eg a ed egula o y ne wo ks
[2]. Al hough a ional echniques ha e been success ully applied o
edesign na u al sys ems [3,4], enginee syn he ic ones [2,5–7] and
assemble modula s uc u es [8–10], de no o sequence design s ill
emains di icul because o he size and complexi y o mul i-s a e
sys ems. To o e come his, we p opose an e olu iona y compu-
a ion design s a egy [11], whe e all design speci ica ions a e
au oma ically assembled o yield an op imal solu ion.
In his wo k, we demons a e a ull design au oma ion o RNA
sequences ha implemen di e se ibo egula o y mechanisms, able
o p oduce se e al sRNA-based logic ga es ha a e unc ional in
li ing cells. We gene alize ou p e ious wo k [11] on he design o
ibo egula o s o ac i a ing p o ein exp ession, which could be
conside ed as YES ga es, o de i e objec i e unc ions o design
ibo egula o s implemen ing se e al logic ga es. Fu he mo e, we
expe imen ally alida e ou objec i e unc ion by conside ing
mu an s o na u al and syn he ic ibo egula o s [11,4], and his
allows assessing he gene ali y o he me hodology.
By gene alizing he posi i e ibo egula ion pa adigm, whe e an
sRNA in e ac s h ough Wa son-C ick pai ing wi h a a ge
mRNA o igge a con o ma ional change enabling ibosome
docking, we can ex end he me hodology o design a bi a y logic
ga es, accoun ing o new egula o y mechanisms, such as an i-
e mina ion, and implemen ing cons ained design s a egies
(Fig. 1). Fo ha , we exploi an isense and allos e ic RNA
[12,13], wo conse ed mechanisms based on p ecise seconda y
s uc u es, and whose majo ole has been epo ed o e he las
yea s in bac e ia [14], bu also in humans [15] and plan s [16].
Ou me hod s a s om andom sequences o p oceed wi h
successi e ounds o a mu a ion ope a o , ollowed by selec ion
using an objec i e unc ion ha accoun s o he ee ene gies o all
possible eac ions and he seconda y s uc u es o all species.
P e ious wo k on ull design au oma ion o nucleic acids was
ocused on in i o annealing o small DNAs [17–20], hamme head
ibozymes [21], o ibosome binding si es (RBSs) [22].
In he ollowing, we will s a by o mula ing he RNA design
p oblem as an in e se p oblem o p og am gene exp ession. This is
basedonanop imiza ionme hod ha minimizesanab ini io objec i e
unc ion, which con as s wi h o he app oaches [4]. We will e alua e
such an objec i e unc ion by enginee ing and cha ac e izing ou own
mu an lib a y o syn he ic ibo egula o s ac i a ing gene exp ession.
A e wa ds, we will show and exempli y how o design sRNA-based
logic ga es, including complex ga es in ol ing syne gis ic in e ac ions
o di e en sRNAs as inpu s. Finally, we will discuss he esul s
s essing he limi a ions o ou me hodology.
PLOS Compu a ional Biology | www.ploscompbiol.o g 1 Augus 2013 | Volume 9 | Issue 8 | e1003172
Resul s
Fo mula ion o an in e se p oblem
Ribo egula ion is based on con o ma ional changes, a e
in e ac ion, in he s uc u es o RNA molecules, which allow
con olling p o ein exp ession. To design such egula o y RNAs,
we op imize he po en ial ene gy cu e de ined in he ansi ion
s a e heo y [23], minimizing he ee ene gies o he ansi ion and
hyb idiza ion s a es. We assume ha he indi idual olding s a e is
o med be o e in e molecula RNA-RNA in e ac ion, because i s
ime scale is o milliseconds whe eas hyb idiza ion akes seconds o
e en minu es [24,25]. The in e ac ion mechanism is guided by
means o he seed egion (nuclea ion si e; he i s nucleo ides ha
ge pai ed) o o m an in e media e complex a he ansi ion s a e
[3,11]. Then, bo h RNAs a e des abilized o o m a complex wi h
a new s uc u e and minimal ene gy.
He e, we conside he s uc u es o all indi idual species as design
speci ica ions. To add ess he compu a ional design, we i s ly ha e
o ind sequences olding in o p ede ined s uc u es and, second,
ind sequences able o in e ac speci ically among hem o o m
complexes displaying he co ec beha io . The s uc u al con-
s ain s a e exploi ed o conside ably educe he combina o ial
space and accele a e he design o nucleic acid sequences. Ou
compu a ional p ocedu e op imizes a he same ime all RNA
sequences o he ci cui . Du ing he op imiza ion, we do no impose
cons ain s in nucleo ide sequence, such as s ems wi h high GC-
con en o loops wi h YUNR mo i s, which ha e been ound in
na u al sys ems [12]. Impo an ly, ou designs a e jus based on
basic physicochemical p inciples and no on addi ional i ing,
allowing he solu ion o he ull design p oblem.
Bu , is he p oposed objec i e unc ion p edic i e enough o allow
he designabili y o mul i-s a e RNA de ices? To illus a e his
ques ion, we cons uc ed he e a lib a y o mu an s o one o ou
p e iously designed ci cui s ( he de ice RAJ11 [11], implemen ing a
YES logic ga e as shown in Fig. 1B). Then, we ep esen ed he
expe imen al alues o he measu ed ac i a ion old agains he
objec i e unc ion calcula ed o hose mu an s (Fig. 2A). To gi e
u he suppo o ou objec i e unc ion, we e alua ed i o a se o
mu a ional a ian s o he IS10 an isense RNA sys em [4],
implemen ing a NOT logic ga e (Fig. 1A), and hen we ep esen ed
hose alues agains he expe imen al ep ession olds epo ed
(Fig. 2B). This na u al sys em cons i u es an independen alida ion.
The objec i e unc ion he e (Eq. 13) accoun ed o he ee ene gy o
o ma ion and he leng h o he seed in he sRNA-mRNA
in e ac ion. Fig. 2 shows a good co ela ion (wi hou any i ing)
o ou objec i e unc ion and expe imen al da a, which suppo s
he designabili y o hose de ices.
Design o simple sRNA-based logic ga es
We i s applied ou design me hodology o ob ain sRNA-based
ep ession and ac i a ion. Many known ibo egula o s impa a
ep essi e ac ion on hei a ge s by p omo ing accele a ed
deg ada ion h ough endo ibonucleases, which ini ia e u no e
o bo h RNAs [26]. Ins ead, we he e accoun o sRNAs ha bind
speci ically o a segmen o i s a ge mRNA in o de o inhibi
ansla ion (NOT logic unc ion) [4]. The mos in ui i e mecha-
nism consis s in blocking he Shine-Dalga no sequence, which is
gene ally loca ed abou eigh base pai s ups eam o he s a
codon (AUG), o p e en ing ibosome docking (Fig. 1A). Fo
ins ance, in E. coli plasmid F, sRNA FinP di ec ly binds o he 59
un ansla ed egion (UTR) o p o ein T aJ [12]. We cons uc ed
he ollowing objec i e unc ions (de ini ions o DG
kin
and DG
s
in
sec ion Me hods) o sol e he op imiza ion p oblem
In Ou
min
DGs 5’UTR,RBS ee
ðÞ
DGkin sRNA,5’UTRðÞzDGs sRNA :5’UTR,RBSpai ed

(01:
10
ð1Þ
These unc ions a e associa ed o each en y o he u h Table,
and hen he solu ion o his p oblem will yield NOT logic ga es.
In Fig. 3, we show se e al compu a ional designs o his logic
de ice. We applied ou me hodology wi h di e en na u al
occu ing s uc u es in ol ing one, wo o h ee hai pins o he
ans- ep essing sRNAs. In ou designs, we used he Shine-
Dalga no sequence AGGAGA.
Al hough he majo i y o sRNA-media ed egula ion in E. coli
consis s in ep ession, an sRNA can also ope a e as an ac i a o
(YES logic unc ion) [2]. In his case, he sRNA ans-ac i a es a cis-
ep essed gene by i s 59UTR. A e in e ac ion, he con o ma-
ional change in he 59UTR eleases he Shine-Dalga no
sequence and allows ansla ion (Fig. 1B). Fo ins ance, in E. coli,
sRNA Ds A is esponsible o ac i a ing he exp ession o sigma
ac o RpoS, which modula es he s ess esponse [13]. Hence, we
cons uc ed he ollowing objec i e unc ions
In Ou
min
DGs 5’UTR,RBSpai ed

DGkin sRNA,5’UTRðÞzDGs sRNA :5’UTR,RBS ee
ðÞ
(00
11
:ð2Þ
The solu ion o his p oblem will p oduce he in ended unc ion
speci ied in he u h Table. This p oblem is much complex ha
he p e ious one because he e he wo RNA species ha e
s uc u e. In Fig. 4, we show se e al compu a ional designs o
YES logic ga es based on con o ma ional changes in he 59UTRs
o he a ge genes. We applied ou me hodology wi h di e en
s uc u es o he ans-ac i a ing sRNAs, while main aining a
common s uc u e o he 59UTR. We also a emp ed he
compu a ional design o a syn he ic RNA able o in e ac wi h he
RpoS 59UTR, and hen enhance he ansla ion a e. Fig. S2
shows he sequences and s uc u es ob ained.
In addi ion, we exploi ed ou me hodology o design NOT logic
ga es based on s uc u ed 59UTRs. He e, he ans-ac i a ing
sRNA in e ac s wi h he 59UTR o induce a con o ma ional
Au ho Summa y
Is ou cu en knowledge o in i o RNA-RNA in e ac ions
and he modynamics enough o pe o m he unsupe ised
compu a ional design o ully syn he ic sequences encod-
ing unc ional RNAs in li ing cells? Recen wo k ga e a
posi i e answe o he challenging p oblem o designing
ac i a ing ibo egula o s. This was done by in eg a ing
heo y and compu a ion o de elop a physicochemical
amewo k o he design o egula o y RNA sys ems, using
Wa son-C ick in e ac ions and op imiza ion algo i hms.
S ill, he objec i e unc ion was no di ec ly alida ed,
p e en ing using wi h con idence he me hodology o
o he sys ems. We he e alida e expe imen ally an
objec i e unc ion elying on ee ene gies o RNA complex
ac i a ion and o ma ion, which allows ex ending he
amewo k o p oduce logic de ices ha can be imple-
men ed o p og am gene exp ession. We demons a e ha
i is possible o design inc easingly sophis ica ed and
modula unc ions, poin ing ou esul s ou ha ene gy-
based op imiza ion me hods can pe o m he la ge
combina o ial sea ch equi ed o RNA design.
ð1Þ
ð2Þ
Regula o y RNA Design
PLOS Compu a ional Biology | www.ploscompbiol.o g 2 Augus 2013 | Volume 9 | Issue 8 | e1003172
change ha blocks he Shine-Dalga no sequence (Fig. 1C). The
objec i e unc ions o sol e he co esponding p oblem ead
In Ou
min
DGs 5’UTR,RBS ee
ðÞ
DGkin sRNA,5’UTR
ðÞ
zDGs sRNA :5’UTR,RBSpai ed in amol

(01
10
,ð3Þ
whe e he di e ence wi h Eqs. (1) elies on he imposi ion ha he
RBS mus be pai ed a he in amolecula le el. Fig. 5A shows a
compu a ional design implemen ing his egula o y mechanism. We
also designed ibo egula o s wi h ac i a ion ac i i y based on a
mechanism o an i- e mina ion [27]. This design elies on a ans-
egula ing sRNA able o des abilize he s uc u e o a e mina o ,
which is he e he cis- egula ing elemen , esul ing in a complex ha
allows he p og ession o he RNA polyme ase (Fig. 1D). This
mechanism can also en ail kine ic e ec s [3], whe e he in e ac ion
has o occu be o e RNA polyme ase eads h ough he e mina o .
This may impose a na ow ime window o ope a ion, which we
specula e su moun able p o ided a gi en ee ene gy h eshold and
a high a io sRNA/mRNA. In his case, he objec i e unc ions we e
In Ou
min
DGs 5’UTR,Hai pin wi h poly(U)
ðÞ
DGkin sRNA,5’UTRðÞzDGs sRNA :5’UTR, No hai pinðÞ
(00
11
,ð4Þ
whe e he 59UTR encodes o a e mina o ha is o med in
absence o he sRNA. The solu ion o his p oblem will also sa is y
he u h Table o YES. Fig. 5B shows a compu a ional design o a
YES logic ga e based on his mechanism. In he inal s uc u e o he
complex, he e mina o hai pin is des abilized and he poly(U) ail
does no ha e any e ec .
Figu e 1. Schemes o di e en sRNA-based mechanisms o con ol p o ein exp ession. Ribo egula ion is based on con o ma ional
changes in he seconda y s uc u es o RNA molecules ha allow con olling p o ein exp ession. The annealing mechanism be ween wo sRNAs s a s
by he nucleo ides in he seed o o m an in e media e complex and hen ollows o each he s uc u e o minimal ene gy. (A) Scheme o a NOT logic
ga e, which consis s in an sRNA able o bind o he RBS sequence o block ansla ion. (B) Scheme o a YES logic ga e, whe e he sRNA is designed o
elease he RBS ha is cis- ep essed. (C) Scheme o a u he NOT logic ga e, whe e he sRNA is able o induce cis- ep ession (exploi ing he
mechanism shown in B). (D) Scheme o a u he YES logic ga e, whe e he sRNA in e ac s wi h a ansc ip ion e mina o placed ups eam o he RBS,
allowing o p e en ing he o ma ion o he mRNA. (E) Scheme o an AND logic ga e, whe e wo sRNAs a e designed o in e ac among hem and
o m a complex ha can elease he RBS.
doi:10.1371/jou nal.pcbi.1003172.g001
ð3Þ
ð4Þ
Regula o y RNA Design
PLOS Compu a ional Biology | www.ploscompbiol.o g 3 Augus 2013 | Volume 9 | Issue 8 | e1003172
Design o combina o ial sRNA-based logic ga es
We hen applied ou me hodology o he design o highe -o de
ibo egula o y de ices. Taking he NOT logic ga e shown in Fig. 5A
as a e e ence, we pe o med he design o a new 59UTR o cis-
ep ession and ha was able o espond o he same ibo egula o , in
his case wo king as an ac i a o . The op imiza ion p oblem ead
In Ou
min
DGs 5’UTR,RBSpai ed

DGkin sRNA,5’UTR
ðÞ
zDGs sRNA :5’UTR,RBS ee
ðÞj
sRNA cons
(00
11
,ð5Þ
whe e he di e ence wi h Eqs. (2) elies on he imposi ion ha he
sRNA sequence is cons an . Likewise, he same sRNA will ha e he
abili y o bo h ep ess and ac i a e p o ein exp ession (coupled
YES/NOT logic ga e). Exploi ing u he his modula i y, we
ca ied ou he design o an OR logic ga e using he 59UTR
sequence jus designed. We now en o ced he design o a new sRNA
ha had also he abili y o eleasing he RBS, main aining cons an
he 59UTR sequence. The op imiza ion p oblem had hen only one
ins ance, gi en by
In Ou
min DGkin sRNA,5’UTRðÞzDGs sRNA :5’UTR,RBS ee
ðÞD50UTR cons 11
:ð6Þ
Thus, he esul ing sys em will in eg a e wo sRNAs capable o
ac i a ing he elease o he RBS con ained in a single 59UTR.
Subsequen ly, we e i ied he e was no in e e ence be ween he wo
sRNAs, al hough his could ha e also been inco po a ed in o he
design p ocess. Fig. 6 shows he in eg a i e ci cui (mul i-inpu ,
mul i-ou pu ) ha we inally ob ained wi h his s a egy based on
se ial design o cons ained YES ga es.
Mo i a ed by he p e ious esul s, we ca ied ou he design o
coope a i e ibo egula ions. The egula o y unc ion o mul iple-
sRNA complexes has no been epo ed in p oka yo es (all na u al
sys ems o ibo egula ion in ol e wo RNA species, a mos
in e ac ing wi h p o eins such as RNA chape ones o endo ibo-
nucleases [28]), which u he encou ages he explo a ion by
means o compu a ional me hods. To illus a e he powe o ou
app oach, we ocused on he design o syne gis ic ac i a ion (AND
logic unc ion), whe e wo ans- egula ing sRNAs i s in e ac
among hem o o m a complex ha will hen ac i a e ansla ion
(Fig. 1E). To sol e he op imiza ion p oblem, we cons uc ed he
ollowing objec i e unc ions
In1In2Ou
min
DGs 5’UTR,RBSpai ed

{DGkin sRNA1,5’UTRðÞ
{DGkin sRNA2,5’UTRðÞ
DGkin sRNA1,sRNA2
ðÞzDGkin sRNA1:sRNA2,5’UTRðÞz
DGs sRNA1:sRNA2:5’UTR,RBS ee
ðÞ
8
>
>
>
>
>
>
>
>
<
>
>
>
>
>
>
>
>
:
000
100
010
111
:ð7Þ
As in he p e ious cases, hese unc ions a e associa ed o each en y
o he u h Table, and hence he solu ion o his p oblem will yield
AND logic ga es. In Fig. 7, we show wo di e en designs o his
logic, combina o ial de ice. By hemsel es, he ans- egula ing
sRNAs canno elease he RBS. Howe e , he dime hey o m has a
dis inc s uc u e ha allows in e playing wi h he 59UTR.
Discussion
In conclusion, we ha e ollowed a bo om-up app oach o design
RNA de ices wi h YES, NOT, AND, and OR logic unc ions, based
on i s physical p inciples. These logic ga es implemen mul i-s a e
sRNA de ices o which he e was no design me hod be o e, and ha
can be in e connec ed o c ea e mo e complex logic p og ams.
Al hough we could sol e in e molecula in e se olding p oblems
[29], i was no possible he sys ema ic design o mul iple RNA species
implemen ing a bi a y logic ga es. Fo hei design, each en y o he
u h Table imposes a s uc u al speci ica ion. He e, we accoun ed o
he ee ene gies o all possible eac ions ( he modynamic po en ial) o
sol e his mul i-objec i e in e se p oblem by op imiza ion. Because
ou me hodology does no equi e na u al sequences (wi h he
Figu e 2. Expe imen al alida ion o he objec i e unc ion. (A)
Rep esen a ion o he log o he expe imen al ac i a ion olds o a se
o RNA de ices cons uc ed in his wo k (mu a ional a ian s o he
RAJ11 sys em [11]) e sus DG
kin
(Eq. 13). This sys em implemen s a YES
logic ga e, which was designed wi h he algo i hm p esen ed he e (see
also Table S4). (B) Rep esen a ion o he log o he expe imen al
ep ession olds ecen ly epo ed o a se o mu a ional a ian s o he
IS10 an isense RNA sys em [4] e sus DG
kin
. This sys em implemen s a
NOT logic ga e, and i se es o es he p edic abili y o he me hod
agains independen expe imen al da a (see also Table S2). He e, we do
no conside DG
s
as we a e only analyzing he in e ac ion abili y. The
lines co espond o linea eg essions, and he coe icien s R
2
a e
shown, assuming a model whe e he old change scales exponen ially
wi h he ee ene gy.
doi:10.1371/jou nal.pcbi.1003172.g002
ð5Þ
ð6Þ
ð7Þ
Regula o y RNA Design
PLOS Compu a ional Biology | www.ploscompbiol.o g 4 Augus 2013 | Volume 9 | Issue 8 | e1003172
excep ion o key mo i s such as he Shine-Dalga no sequence), we
ha e sol ed he ull design p oblem o egula o y RNA o
implemen ing logic p og ams in li ing cells.
Ou app oach has, howe e , some limi a ions, which p ospec
u he esea ch in he ield. One o hem is he use o he seconda y
s uc u e o model ibo egula ion. This ype o egula ion could
in ol e pseudokno in e ac ions and e en non-canonical base
pai ing, o which h ee-dimensional models could be e cap u e
he in e ac ion ea u es [30]. In addi ion, ou model does no
accoun o RNA chape ons (e.g., H q) [31], no co- ac o s such as
Mg
2+
o Zn
2+
, no kine ic binding e ec s, which migh ha e an
impac on he designs. Ano he es ain o he cu en me hod is he
en o cemen o a gi en s uc u e o all single species in he ci cui
(al hough no o he complex ones), because his cons ains he
sequence space o possible solu ions [11]. By lea ing uncons ained
hose s uc u es, we could pe o m addi ions and/o dele ions (no
only eplacemen s) o nucleo ides du ing he op imiza ion, and we
would need o include in o he unc ion DG
s
a new e m o he
s abili y (e.g., based on ee ene gy). Finally, he con e gence o he
algo i hm is highly educed when e ol ing sys ems wi h mul iple
species, making necessa y o educe he sequence space by eusing
unc ional modules o ob ain mo e sophis ica ed sys ems.
Despi e hese limi a ions, we ha e demons a ed he powe o
compu a ional design ( h ough heu is ic op imiza ion) o o e come
he complexi y in ob aining ully syn he ic ibo egula ion, explo -
ing he as combina o ial space o sequences. The p oposed
objec i e unc ion was shown p edic i e enough o allow he
designabili y o mul i-s a e RNA de ices, as DG
kin
explained
di e ences in expe imen al ep ession old o a se o mu a ional
a ian s o he IS10 an isense RNA sys em (Fig. 2) [4]. Mo eo e ,
we ecen ly alida ed expe imen ally some designs o YES logic
ga es in bac e ia, encou aging u he wo k [11]. E en hough, he
design p oblem does no equi e a pe ec p edic ion, and simila
o e en lowe co ela ions can be su icien o ackle his p oblem,
such as in he case o au oma ed RBS design [22]. O cou se, mo e
sophis ica ed objec i e unc ions will be de eloped in he coming
yea s o imp o e he design o unc ional RNAs.
The combina ion o DG
kin
and DG
s
, o e e y possible
con o ma ional s a e (in a- o in e molecula ) o a gi en geno ype,
esul s in an e ec i e ee ene gy ha de ines a i ness landscape.
In case o ibo egula ion, he o al sea ch space can be abou 10
40
sequences [11], and ypical op imiza ions ha lead o su icien ly
good solu ions consis o 10
6
–10
7
i e a ions. Indeed, he gene al-
ized p oblem o inding he nucleo ide sequences o mul i-species
ensembles ha will old in o speci ied con o ma ions has an
exponen ially la ge numbe o solu ions. I emains howe e a
ques ion how o dis inguish se e al op imized sequences (assuming
equal ene ge ic ea u es). Fo ins ance, di e ences in in acellula
s abili y o he species will a ec he a io sRNA/mRNA, and hen
be key o he egula o y ac i i y. Addi ionally, he kine ics o RNA
olding, binding, and u no e will ha e signi ican impac on he
pe o mance o designed RNA ci cui s [3,10]. All hese c i e ia,
ei he om i s p inciples o om expe imen al eedback, will be
exploi ed o enhance he design me hodology.
Figu e 3. Designs o sRNA-based NOT logic ga es. We show ou designs (A o D) using di e en s uc u es o he ans- ep essing sRNAs
(mechanism shown in Fig. 1A). (A.1) De ail o a design, showing he RBS in blue, s a codon in g een, and seed egion in ed. The seconda y
s uc u es o he in amolecula and in e molecula olding s a es a e p esen ed. (A.2, B.1, C.1 and D.1) Helical plo o he complex, whe e he RBS is
blocked. DG,DG
kin
and DG
s
a e in Kcal/mol. Zis he pa i ion unc ion. (A.3, B.2, C.2 and D.2) Base pai ing p obabili y ma ix, enci cling he pai s o
in e molecula in e ac ion wi h high p obabili y. RNA sequences shown in Table S1. Seconda y s uc u es imposed o all species shown in Fig. S1.
doi:10.1371/jou nal.pcbi.1003172.g003
Regula o y RNA Design
PLOS Compu a ional Biology | www.ploscompbiol.o g 5 Augus 2013 | Volume 9 | Issue 8 | e1003172

Ou p esen me hodology is gene al and could be applied o ob ain
designs based on u he mechanisms. In addi ion, ins ead o a emp ing
ull designs, i pe mi s eusing comple e known sequences (na u al o
syn he ic) o cons ain he design o new logic sys ems. This capaci y
enables he c ea ion o a la ge a ie y o combina o ial sRNA sys ems,
inc easing sophis ica ion a a educed compu a ional cos . Mo eo e ,
ou app oach can be used o analyze po en ial RNA sequences o a
gi en unc ional ci cui as a e e se enginee ing ool. The designed
sRNA-based logic ga es can be combined wi h ansc ip ion egula ion
o gene a e mo e complex unc ions [32], and also be in eg a ed in o
lib a ies o models o he compu a ional design o mo e complex
ne wo ks in ol ing ansc ip ion and pos - ansc ip ion egula ion [33].
Ye , ou ull design au oma ion app oach oge he wi h high-
h oughpu sc eening echniques will p opel he cons uc ion o
modula and o hogonal de ices o syn he ic biology [34].
Me hods
The modynamic model
We conside ed ibo egula ion (RNA-RNA in e ac ion) in e ms
o he modynamics [29,35,36], assuming ha he sys em eaches an
equilib ium s a e. We i s applied an in e se olding s a egy o e
he s uc u es o all indi idual species. Then, neu al mu a ions in
s uc u e we e e alua ed wi h an objec i e unc ion in ended o
op imize he in e molecula olding s a es. To ob ain an in e mo-
lecula olding sa is ying he elease o blockage o he RBS, in
p inciple, we needed o maximize he pa i ion unc ion (Z)o he
whole sys em. Using he eac ion coo dina e o he sys em ( ),
de ined as he numbe o in e molecula Wa son-C ick in e ac ions
(i.e., = 0 ep esen s indi idual olding) [11], Zcan be w i en as
Z~X
exp {G ðÞ
RT

,ð8Þ
whe e G( ) is he e ec i e ee ene gy o he s a e wi h eac ion
coo dina e (whe e G(0) ep esen s he ee ene gy o he no-
in e ac ion s a e, wi h G=0 o he un olded s a e), R he gas
cons an , and T he empe a u e. He e, we a e in e es ed in G( )a he
eac ion coo dina es o he ansi ion, G(
ans
), and inal in e molec-
ula (hyb idiza ion) s a es, G(
hyb
), o de ine ou unc ions DG, he ee
ene gy o o ma ion, and DG
{
, he ee ene gy o ac i a ion, by
DG~G
hyb

{G0ðÞ
DGz
z~G
ans
ðÞ{G0ðÞ:
ð9Þ
To compu e he ee ene gy and seconda y s uc u e o all
species (single and complexes) o a sys em, we used he
ViennaRNA [37] and Mul iRNAFold [38] (when ha ing mo e
han wo RNA species) so wa e. We only conside ed he
Figu e 4. Designs o sRNA-based YES logic ga es. We show ou designs (A o D) using di e en s uc u es o he ans-ac i a ing sRNAs
(mechanism shown in Fig. 1B). (A.1) De ail o a design, showing he RBS in blue, s a codon in g een, and seed egion in ed. The seconda y
s uc u es o he in amolecula and in e molecula olding s a es a e p esen ed. (A.2, B.1, C.1 and D.1) Helical plo o he complex, whe e he RBS is
eleased. DG,DG
kin
and DG
s
a e in Kcal/mol. Zis he pa i ion unc ion. (A.3, B.2, C.2 and D.2) Base pai ing p obabili y ma ix, enci cling he pai s o
in e molecula in e ac ion wi h high p obabili y. RNA sequences shown in Table S1. Seconda y s uc u es imposed o all species shown in Fig. S1.
doi:10.1371/jou nal.pcbi.1003172.g004
Regula o y RNA Design
PLOS Compu a ional Biology | www.ploscompbiol.o g 6 Augus 2013 | Volume 9 | Issue 8 | e1003172
minimum ee ene gy s a e disca ding he subop imal ones. He e,
we did no conside pseudokno s. A e wa ds, he designed
sequences we e analyzed wi h he Nupack so wa e [29], which
is able o compu e ensemble p ope ies such as Z. In his wo k, we
used he M old 3.0 RNA ene gy pa ame e s [39], and always
conside ed T=37uC (which gi es RT = 0.61 Kcal/mol).
De i ing a gene ic objec i e unc ion o in i o RNA-RNA
in e ac ions
In an RNA-RNA in e ac ion be ween species Aand B,an
in e media e complex a he ansi ion s a e ([A:B]
{
) is o med
media ed by he seed. Then, a as eac ion inducing a
con o ma ional change occu s. Deno ing k
on
and k
o
he o wa d
and e e se cons an s, espec i ely, o o m [A:B]
{
, and k
hyb
he
hyb idiza ion cons an o o m he inal complex (A:B), he mass
ac ion kine ic model eads
dA:B½
z
z
d ~konAB{ko A:B½
z
z{khyb A:B½
z
z{d1A:B½
z
z
dA :B
d ~khyb A:B½
z
z{d2A:B,
ð10Þ
whe e d
1
and d
2
a e he deg ada ion cons an s. Assuming ha k
o
+
k
hyb
is much g ea e han d
1
(sRNA deg ada ion akes se e al
minu es [13]), we can ob ain in s eady s a e [A:B]
{
=AB/K
M
, whe e
K
M
=(k
o
+k
hyb
)/k
on
is he Michaelis cons an . Hence, A:B (and also
he ansla ion a e) will be in s eady s a e p opo ional o k
hyb
/K
M
,
assuming he e is no sa u a ion.
The cons an k
on
can be ob ained by i ing in i o DNA
hyb idiza ion da a, whe e only he leng h o he seed (a), i espec i e
o he sequence, de e mines he kine ic cons an ollowing a
Bol zmann ac o [25]. Mo eo e , we can say ha he cons an
k
hyb
is de e mined by DG( he ee ene gy o o ma ion be ween A+B
and A:B) also wi h a Bol zmann ac o . This allows us o w i e
kon!exp {
aGp
RT

khyb!exp {
DG
RT

:ð11Þ
The e o e, he esul ing model eads
khyb
KM
~khybkon
ko zkhyb
!1
ko zkhyb
exp {
DGzaGp
RT

,ð12Þ
whe e G
p
is a i ed pa ame e o accoun o he a e age ene ge ic
con ibu ion o one nucleo ide. G
p
=21.28 Kcal/mol [25]. Finally,
we p oposed DG+aG
p
as he objec i e unc ion o op imize RNA-
RNA in e ac ions. This o mula ion is in pa equi alen o
maximize Z, because om he A henius equa ion [23] DG
{
and
ashould ha e a linea ela ionship.
Op imiza ion algo i hm
Ou e olu iona y algo i hm consis s in a Mon e Ca lo
Simula ed Annealing [40], which can be pa allelized o e ol e a
Figu e 5. Fu he designs o sRNA-based NOT and YES logic ga es. We show wo designs (A and B) using he mechanisms shown in Figs. 1C
and 1D. Fo he NOT ga e, helical plo s showing (A.1) he RBS exposed, and (A.2) he RBS blocked a e sRNA in e ac ion. Fo he YES ga e, helical
plo s showing (B.1) a ansc ip ion e mina o , and (B.2) ha he hai pin be o e he poly(U) ail is des abilized a e sRNA in e ac ion. DGis in Kcal/mol.
Zis he pa i ion unc ion. (A.3 and B.3) Base pai ing p obabili y ma ix, enci cling he pai s o in e molecula in e ac ion wi h high p obabili y. RNA
sequences shown in Table S1. Seconda y s uc u es imposed o all species shown in Fig. S1.
doi:10.1371/jou nal.pcbi.1003172.g005
Regula o y RNA Design
PLOS Compu a ional Biology | www.ploscompbiol.o g 7 Augus 2013 | Volume 9 | Issue 8 | e1003172
popula ion o sequences. Ou app oach consis s in op imizing an
objec i e unc ion accoun ing o he in e ac ion and s uc u e o
he RNAs ha lead o he a ge beha io .
The design speci ica ions comp ise he seconda y s uc u es o
all single RNAs, c i ical subsequences o nucleo ides (e.g., RBS),
he eac ion ee ene gies, and he s uc u e o he ou pu
complex. The algo i hm s a s om pu e andom sequences
sa is ying he s uc u al and subsequence cons ain s, al hough i
can also be speci ied an ini ial sequence. I he subsequence
cons ain s do no allow sa is ying he s uc u es, he algo i hm
s ops. E en ually, we can in oduce a elaxa ion in he s uc u al
cons ain s ( h ough an ha monic cons ain ) allowing ha ing
species wi h dissimila s uc u es o hei a ge s. Subsequen ly,
an i e a i e p ocess o mu a ion and selec ion is implemen ed (see
scheme o he algo i hm in Fig. S3). The mu a ion ope a o
consis s in ei he andom o di ec ed nucleo ide eplacemen s.
We do no conside addi ions o dele ions, so he leng h o he
RNAs is main ained cons an . To speed up he con e gence, we
gene a ed a mu a ion ope a o ha only c ea ed use ul mu a ions,
e.g., mu a ions ha a e always gua an eed o con ibu e o an
in e ac ion among RNA species. We do his by aking a wo d
(i.e., se o consecu i e nucleo ides) om one sequence, making
i s e e se complemen a y, and andomly inse ing i in o
ano he sequence. Ini ially, he leng h o his wo d is h ee,
and i is educed o one (i.e., single poin mu a ion) du ing he
op imiza ion p ocess. Those mu a ions speed up he in silico
e olu ion. I a nucleo ide ha has o be mu a ed belongs o a
s em, i s pai in he s em is also mu a ed wi h he co esponding
nucleo ide wi h he aim o p e en ing he dis up ion o he
seconda y s uc u e and imp o ing he con e gence. We a oid
sequences ha ing consecu i e epea s o ou o mo e iden ical
nucleo ides.
The objec i e unc ion is a weigh ed sum o wo e ms o be
minimized. The i s e m (DG
kin
) accoun s o he eac ion kine ics
o he sys em. Fo ha , we compu e he DGand ao all possible
eac ions, ha ing be ween species Aand B
DGkin A,BðÞ~DGzaGp:ð13Þ
No ice ha DG
kin
is a nega i e- alued a iable. We will minimize
o maximize DG
kin
i he eac ion mus occu o no (in o de o
ob ain he speci ied beha io ). Maximizing DG
kin
is equi alen o
minimize 2DG
kin
. Du ing he op imiza ion we exclude sequences
o ming homodime s. In addi ion, we conside ed DG
sa
=215 K-
cal/mol and a
sa
= 6 as a bi a y sa u a ion le els (i.e., le els om
which he e is no need o u he minimiza ion). These alues can
be enla ged o ge designs wi h lowe DG
kin
, al hough a a cos o
al e ing he con e gence. The second e m (DG
s
) accoun s o he
s uc u al change o he ou pu RNA. Fo ha , we use a Hamming
dis ance (d) be ween he cu en and a ge s uc u es, being
DGs A,S ðÞ~{dA,S ðÞGp:ð14Þ
This indica es ha species A(which can be single o complex) is
e ol ed o display he a ge s uc u e, o subs uc u e, S (e.g.,
RBS pai ed, hen ep essing p o ein ansla ion). G
p
is used o
escale he dis ance in e ms o ee ene gy. We no e ha DG
s
is a
posi i e- alued a iable, which we will minimize.
Figu e 6. Design o a mul i-inpu , mul i-ou pu sRNA-based logic ci cui . We show a design o a ci cui ha assembles di e en
ibo egula o s. He e, sRNA R13 is able o bo h ep ess and ac i a e he exp ession o wo di e en cis- ep essed genes, by cR31 and cR19 espec i ely,
esul ing in a coupled YES/NOT logic ga e. In addi ion, sRNA R19 is able o ac i a e cR19, implemen ing oge he wi h R13 an OR logic ga e. RNA
sequences shown in Table S1. Seconda y s uc u es imposed o all species shown in Fig. S1.
doi:10.1371/jou nal.pcbi.1003172.g006
Regula o y RNA Design
PLOS Compu a ional Biology | www.ploscompbiol.o g 8 Augus 2013 | Volume 9 | Issue 8 | e1003172
Expe imen al lib a y o RNA de ices
100 ng o plasmid pRAJ11 coding o he ibo egula o y de ice
RAJ11 we e subjec ed o 30 cycles o PCR ampli ica ion wi h
di e gen p ime s I (59-CCGCGAAGACCGGCACGGNNNGG-
TTGATTGTGTGAGTCTGTC-39, N is A, C, G o T; BpiI
ecogni ion and clea age si es unde lined) and II (59-GGCGGAA-
GACGCGTGCTCAGTATCTCTATCACTG-39, BpiI ecogni-
ion and clea age si es unde lined) in a olume o 20 mL wi h
0.4 U o he high ideli y Phusion DNA polyme ase (The mo
Fishe Scien i ic) in he p esence o HF bu e (The mo Fishe
Scien i ic), 3% dime hyl sul oxide, 0.2 mM each dNTP and
0.5 mM each p ime . Reac ions consis ed o an ini ial dena u a ion
o 30 s a 98uC ollowed by 30 cycles o 10 s a 98uC, 30 s a 55uC
and 1:15 min a 72uC, wi h a inal incuba ion o 10 min a 72uC.
A e PCR, 10 U o DpnI (The mo Fishe Scien i ic) we e added
o each sample o diges he empla e plasmid and incuba ed o
1 h a 37uC. Reac ion p oduc s we e elec opho esed in a 1%
aga ose gel in TAE bu e (40 mM T is, 20 mM sodium ace a e,
1 mM EDTA, pH 7.2) and he gel s ained wi h e hidium b omide.
The 4460-bp long DNA p oduc co esponding o he ull-leng h
plasmid was elu ed om he gel, diges ed wi h BpiI o 1 h a 37uC
(The mo Fishe Scien i ic) and inally subjec ed o sel -ci cula i-
za ion wi h 5 U o T4 DNA ligase (The mo Fishe Scien i ic) o
1 h a 22uC. Reac ion p oduc s we e pu i ied by ch oma og aphy
wi h silica gel spin columns (DNA Clean and Concen a o , Zymo
Resea ch) and elec opo a ed in E. coli DH5a. Recombinan
bac e ia we e selec ed in pla es wi h 50 mg/mL ampicillin.
Plasmids we e pu i ied om liquid cul u es o selec ed clones
Figu e 7. Designs o sRNA-based AND logic ga es. We show wo designs (A and B) using di e en s uc u es o he ans-ac i a ing sRNAs
(mechanism shown in Fig. 1E). (A.1) De ail o a design, showing he RBS in blue, s a codon in g een, and seed egions in ed and magen a. The
seconda y s uc u es o he in amolecula and in e molecula olding s a es a e p esen ed. (A.2 and B.1) Helical plo o he complex, whe e he RBS is
eleased. DG,DG
kin
and DG
s
a e in Kcal/mol. Zis he pa i ion unc ion. (A.3 and B.2) Base pai ing p obabili y ma ix, enci cling he pai s o
in e molecula in e ac ions wi h high p obabili y. RNA sequences shown in Table S1. Seconda y s uc u es imposed o all species shown in Fig. S1.
doi:10.1371/jou nal.pcbi.1003172.g007
Regula o y RNA Design
PLOS Compu a ional Biology | www.ploscompbiol.o g 9 Augus 2013 | Volume 9 | Issue 8 | e1003172