The languages of RNA: a formal
grammar that includes pseudoknots
Elena Rivas and Sean R. Eddy
Corso di Laboratorio di Linguaggi (2006/07)
Prof. Nicoletta Cocco
Bordignon Claudio
Gaglio Elia
06-12-2006
Bordignon - Gaglio
1
L’area di ricerca della Bioinformatica:
 Si basa sul trattamento e l’analisi di dati biologici con metodi informatici
 Grande sviluppo negli ultimi decenni, grazie allo sviluppo di Internet
 Gli obiettivi della Bioinformatica:
- Gestione di dati (costruzione di banche dati di informazioni biologiche)
- Formulazione di modelli biologici (es. modelli statistici per individuare leggi
numeriche e tendenze)
- Analisi di sequenze di acidi nucleici (DNA, RNA)
06-12-2006
Bordignon - Gaglio
2
La composizione dell’RNA:
 RNA: acido ribonucleico, molto simile al DNA.
 Catena polinucleotidica a singolo filamento contenente 4 nucleotidi differenti:
Gruppo fosfato, legato da 2 molecole
di ribosio
Ribosio, lo zucchero dell’RNA
Basi azotate,le molecole che
trasmettono l’informazione genetica
06-12-2006
Bordignon - Gaglio
3
Le caratteristiche dell’RNA (2):
 L’informazione genetica risiede nel DNA.
 Il flusso dell’informazione genetica è rappresentata dal “dogma centrale”:
Duplicazione: formazione di copie di
molecole di DNA e trasferimento di materiale
genetico
Trascrizione: trasferimento dell’informazione
dal DNA alla molecola di RNA
Traduzione: processo attraverso il quale di
passa dall’RNA alla sintesi delle proteine
06-12-2006
Bordignon - Gaglio
4
Le strutture secondarie dell’RNA:
 L’RNA non è solo un intermediario tra il DNA e la sintesi proteica…
 Vi sono molti RNA non codificanti che svolgono varie funzioni grazie
all’acquisizione di strutture precise:
06-12-2006
Bordignon - Gaglio
5
Tipologie di correlazioni tra coppie di basi:

Normalmente gli accoppiamenti di basi sono tra loro annidati (nested)
AGUGUCGGCUCACU


Esistono anche accoppiamenti di basi non annidati (unnested o crossed)
Sono definiti come “pseudonodi” e sono funzionalmente molto importanti
AGUGUCACUUCACUGGAUGU
06-12-2006
Bordignon - Gaglio
6
Linguaggi formali per la predizione di strutture:
 Linguaggi formali per modellare stringhe di simboli correlati
Idea: L’RNA è dominato da coppie di correlazioni annidate
descrivibili da grammatiche context-free (tipo 2)
Predizione di strutture secondarie
Sviluppo di grammatiche
context free stocastiche
06-12-2006
MFOLD (si basa sull’utilizzo di
parametri termodinamici)
Bordignon - Gaglio
7
Rna’s prediction: MFOLD (1):
 MFOLD = “multiple web server”
 Predizione di strutture secondarie sfruttando il calcolo dell’energia libera
06-12-2006
Bordignon - Gaglio
8
Rna’s prediction: MFOLD (2):
 La stabilità di una molecola ripiegata di RNA può essere misurato in termini di
variazioni di energia libera (ΔG) tra la molecola a singolo filamento e quella
ripiegata in una struttura secondaria
 Struttura ottimale = struttura a minima energia
 Possibilità di ottenere strutture alternative, attraverso l’ “Energy Plot”:
06-12-2006
Bordignon - Gaglio
9
Rna’s prediction: Rivas & Eddy Algorithm (1):
 Problema: la tecnica precedente non tratta gli pseudonodi…
 Soluzione: Algoritmo di Rivas & Eddy
 Algoritmo di programmazione dinamica
 Permette la predizione di strutture secondarie sfruttando parametri
termodinamici, cercando strutture ad energia minima (folding ottimale)
 Funziona correttamente anche per strutture pseudo-knotted
 Complessità (caso peggiore):
tempo: O(n6)
spazio: O(n4)
06-12-2006
Bordignon - Gaglio
10
Rna’s prediction: Rivas & Eddy Algorithm (2):
 wx e vx: matrici che riportano i punteggi del miglior folding tra le posizioni i e j
 Per determinare i pesi corretti per le matrici wx e vx si sfruttano delle relazioni
ricorsive (sintetizzate dalla rappresentazione grafica)
06-12-2006
Bordignon - Gaglio
11
Rna’s prediction: Rivas & Eddy Algorithm (3):
paired
dangles
single stranded
06-12-2006
Bordignon - Gaglio
bifurcations
12
Rna’s prediction: Rivas & Eddy Algorithm (4):
hairpin
internal loop
multiloop
 Necessità di troncare l’espansione interna per avere una grammatica trattabile
in quanto la complessità rende intrattabile l’algoritmo
 ad esempio, O(IS2)
06-12-2006
Bordignon - Gaglio
13
Rna’s prediction: Rivas & Eddy Algorithm (5):
 Per poter gestire gli pseudonodi è necessario estendere le matrici introdotte
(adottando nuove matrici, dette matrici gap):
06-12-2006
Bordignon - Gaglio
14
Rna’s prediction: Rivas & Eddy Algorithm (6):
 Le ricorsioni portano all’introduzione di una nuova rappresentazione:
06-12-2006
Bordignon - Gaglio
15
Grammatica “Crossed-interaction”:
 Una grammatica G che include pseudonodi (crossed interaction) è la seguente:
G = { V, T, S, I, P, R }
dove:
V= insieme (finito) dei simboli non terminali
T= insieme (finito) dei simboli terminali (alfabeto). T* è l’insieme di tutte le
stringhe costruite da T, inclusa ε e la stringa Λ
S= non terminale iniziale
I= insieme (finito) dei simboli extra non terminali
P= insieme (finito) delle produzioni
R= insieme (finito) delle regole di riarrangiamento
06-12-2006
Bordignon - Gaglio
16
Linguaggio “Crossed-interaction” (1):
Un esempio di linguaggio che include le crossing interactions è il cosiddetto
“linguaggio copia”.
Ad esempio, per ottenere pattern duplicati correlati (ab, aba, abaaba, ecc.):
T = { a, b }
L = { ε, W Λ W | W Є (a,b)* }
S={W}
I = { (, ), x }
 Le produzioni associate sono:
06-12-2006
Bordignon - Gaglio
17
Linguaggio “Crossed-interaction” (2):
 Ad esempio, la sequenza:
 può essere analizzata con la seguente
grammatica:
 Sfruttando le parentesi possiamo costruire annidamenti complessi:
06-12-2006
Bordignon - Gaglio
18
“Crossed-interaction” – definizioni formali:
 Indichiamo con:
l’insieme di tutte le stringhe generabile dall’alfabeto:
 L’insieme delle produzioni P ha la forma generale:
 La struttura delle produzioni è simile a quelle delle grammatiche context-free
(tipo 2), ad eccezione della presenza dei simboli extra I, che permettono dei
riarrangiamenti la cui forma generale è:
 La grammatica genera perciò il seguente linguaggio:
06-12-2006
Bordignon - Gaglio
19
“Crossed-interaction” – accorgimenti per il parsing:
 Il parsing per tale grammatica può essere complesso (in alcuni casi NPCompleto). Un possibile accorgimento è troncare la seguente somma infinita
(ad esempio per n=2):
 Infatti, se n=0 abbiamo una grammatica context-free
se n>0 non abbiamo più una grammatica context-free, ma limitando n
rendo il parsing un problema trattabile.
06-12-2006
Bordignon - Gaglio
20
RNA pseudoknot grammar (1):
 La grammatica per definire le strutture di pseudonodi è una specializzazione
della G definita precedentemente. I simboli non-terminali sono:
non gapped
gapped
creano i loop
 L’alfabeto T rispecchia la struttura dell’RNA:
 I simboli extra sono:
06-12-2006
Bordignon - Gaglio
21
RNA pseudoknot grammar (2):
 Le regole di produzione per W sono le seguenti (si Є T è il nucleotide in
posizione i-esima):
 Vab è il non terminale iniziale trovato dopo l’appaiamento di una coppia a,b. Le
regole di produzione sono le seguenti:
06-12-2006
Bordignon - Gaglio
22
RNA pseudoknot grammar (3):
 WH è il non terminale che introduce uno pseudonodo e le regole di
produzione sono le seguenti:
06-12-2006
Bordignon - Gaglio
23
RNA pseudoknot grammar (4):
 VHabcd è il non terminale che si ha dopo la formazione di uno pseudonodo. Le
regole di produzione sono le seguenti:
 Infine i non terminali che creano le “strutture loop” sono così composti:
Hairpin loops
Stems, bulge,
internal loops
06-12-2006
Bordignon - Gaglio
24
RNA pseudoknot grammar (5):
 Le regole di riarrangiamento sono applicabili dopo le diverse produzioni e
permettono un riordinamento della stringa. Esse sono:
06-12-2006
Bordignon - Gaglio
25
RNA pseudoknot grammar – esempio pratico:
a
b
d
c
e
f
W  Wh x Wh
 (Wh  Wb Λ  ) x Wh
 ((Sa VhSaSeSbSd Se  Sb Λ Sd)  Wb Λ ) x (Sc VhScSfSdSeSf  Sd Λ Se)
 ((Sa Λ Se  Sb Λ Sd)  SbVSbScSc Λ ) x (Sc Λ Sf  Sd Λ Se)
 ((Sa Λ Se  Sb Λ Sd)  SbSc Λ ) x (Sc Λ Sf  Sd Λ Se)
R
((Sa Sb Λ Sd Se)  SbSc Λ ) x (Sc Sd Λ Se Sf)
R
((Sa Sb Sb Sc Λ  Sd Se)) x (Sc Sd Λ Se Sf)
R
Sa Sb Sb Sc Sc Sd Λ Sd Se Se Sf
06-12-2006
Bordignon - Gaglio

26
Bibliografia:
 [1] The languages of RNA: a formal grammar that includes pseudoknotes – Rivas &
Eddy, Department of Genetics - Washington University August 1999.
 [2] A dynamic programming algorithm for RNA structure prediction including
pseudoknots – Rivas & Eddy, Department of Genetics - Washington University July 1998.
 [3] Introduzione alla Bioinformatica – Valle, Citterich, Attimonelli, Pesole – Zanichelli.
 [4] MFOLD web server for nucleic acid folding and hybridization prediction – Zuker,
Department of Science Troy USA, April 2003.
06-12-2006
Bordignon - Gaglio
27