L'algoritmo di Nussinov, come la maggior parte degli algoritmi che cercano
di predire la struttura secondaria dell'rna, trova strutture secondarie palindrome.
Per cui gli pseudoknots non sono predicibili con questi approcci.
L'algoritmo che vedremo ora cerca di massimizzare il numero di coppie, o più in
generale un punteggio assegnato a ciascuna possibile coppia base(i),base(j).
La più semplice funzione è ovviamente quella di associare un valore di
se le due basi sono complementari e
altrimenti.
Se definiamo rna la nostra sequenza di basi e vogliamo valutare il
punteggio del possibile accoppiamento tra le basi in posizione i e j, possiamo
utilizzare la funzione definita in Figura
, dove abbiamo anche
introdotto tol, che serve ad evitare di calcolare legami tra basi
la cui separazione lungo la sequenza (|i-j|>=tol) sia troppo corta
(per poter fare un legame richiediamo almeno un loop lungo una base).
Il problema è quello di trovare un algoritmo efficiente per trovare tra le possibili soluzioni il valore di una di quelle ottimali. L'idea di base è sempre quella di utilizzare la soluzione dei sottoproblemi per ottenere la soluzione del problema generale.
Nel caso in esame dobbiamo valutare la possibilità
dei vari accoppiamenti, per cui possiamo partire considerando i possibili accoppiamenti
locali (vicini in sequenza) e poi aumentarne la separazione di sequenza tenendo conto del
risultato ottenuto per le separazioni di sequenza inferiori. Ciò significa partire
cercando i possibili accoppiamenti tra e
, per ogni
dove
è
la lunghezza della sequenza di rna, poi continuare la ricerca incrementando la separazine
tra le due possibili basi (cioè
e
con
.
Se quindi visualizziamo una matrice quadrata che rappresenta le possibili coppie che si
possono creare all'interno di una sequenza, essa andrà valutata per diagonali, dalla
maggiore all'angolo della matrice, come riportato in Tabella
.
Ricordiamo infatti che la diagonale della matrice
rappresenta la base con se stessa
, mentre la diagonale con separazione
di sequenza uguale ad
è
.
A | C | U | G | G | T | |
A | ![]() |
![]() |
![]() |
? | ? | ? |
C | ![]() |
![]() |
? | ? | ? | |
U | ![]() |
![]() |
? | ? | ||
G | ![]() |
![]() |
? | |||
G | ![]() |
![]() |
||||
T | ![]() |
Secondo l'algoritmo che andremo a considerare, ci sono solo quattro possibli scelte che di
volta in volta dovremo compiere, valutando quale tra le quattro ci fornisce il risultato
massimo. Dato il fatto che noi abbiamo già valutato tutte le soluzioni per separazioni
in sequenza pari a , se vogliamo valutare quelle per
con
avremo che la
soluzione ottimale per la coppia
sará da scegliere tra
![]() |
Una volta ottenuta la matrice dei punteggi (smat in Figura
)
di solito si vuole anche ottenere uno dei possibili accoppiamenti con tale punteggio.
Il metodo utilizzato è quello di utilizzare una coda LIFO (Last In First Out),
chiamata anche stack. Le operazioni che possiamo fare su questa coda sono quelle
che possiamo fare su di una pila di libri di cui esaminiamo quello in cima.
Possiamo quindi:
Score is 4.0 AACUUCUUCAA ((.)).((.))Che rappresenta la struttura
C C A = U U = A A = U U = A C
![]() |