GENERALITA' SULLA PROGRAMMAZIONE DINAMICA

Sono in grado di produrre il migliore allineamento senza ricalcolare lo score per ogni posizione dello scorrimento, risparmiando così molto tempo.

Il dinamismo di un algoritmo consiste nel fatto che ogni operazione determina l’operazione successiva, scartando una serie di altre operazioni inutili.

Tre fasi sono alla base degli algoritmi dinamici:

Date due proteine di lunghezza n e m, una matrice di sostituzione ed un gap penalty.

1. Produzione di una matrice n x m con tutti i residui delle due. In ogni casella si posiziona il punteggio attribuito da una matrice di sostituzione per la coppia di residui corrispondente.
2. Per ogni casella trovare il massimo punteggio che si ottiene dai percorsi:
   diagonale :lo score della casella precedente in diagonale + punteggio della casella;
   verticale : lo score della casella precedente in verticale - il penalty;
   orizzontale : lo score della casella precedente in orizzontale - il penalty.
3. Cercare lo score più alto di tutti tra tutte le caselle, procedere verso gli scores più alti a ritroso verso l’inizio della diagonale, scrivendo i residui corrispondenti.

ASSUNZIONI IMPLICITE DELLA PROGRAMMAZIONE DINAMICA

1. Se una sequenza è scritta da sinistra a destra e l’altra è scritta dall’alto in basso, qualsiasi percorso valido deve procedere dall’angolo in alto sinistra all’angolo in basso a destra. Altre strade non sono permesse.
2. Se il percorso procede in verticale o in orizzontale, solo una casella deve essere conteggiata. Quindi un aminoacido non può appaiarsi due volte.
3. Ogni casella ha uno score che dipende dal percorso a monte ed è indipendente dal percorso a valle. Il miglior percorso a monte di un residuo è sempre determinabile.

Score: numero in alto a sinistra nella casella.

Punteggio max: numero in basso a destra nella casella.

Esempio:
Allineamento globale. Le due sequenze da allineare sono poste ai margini superiore e sinistro della matrice. Il percorso evidenziato in grigio indica il miglior allineamento che può essere trovato partendo dalla casella col punteggio massimo.Penalità = 5.

Esempio

Il percorso all’interno di una matrice di allineamento deve seguire delle regole. Le direzioni indicate dalle frecce colorate nel riquadro di sinistra non hanno senso e quindi non sono consentite. Allo stesso modo, nel pannello di destra, per raggiungere la casella con il punto in colore il percorso può provenire solo da una delle tre caselle con il punto di domanda.