Tesi Robotica Analisi, progettazione e implementazione... | Page 64

i

i
“LP_Tesi” — 2013/10/17 — 18:27 — page 64 — #64

i

64

i

2. APPROCCI ALTERNATIVI

L’algoritmo bio-informatico per l’allineamento di sequenze geniche utilizzato
è il Needleman–Wunsch (N-W) [Needleman and Wunsch, 1970], algoritmo di
programmazione dinamica sviluppato nel 1970 da Saul B. Needleman e Christian
D. Wunsch.
Per comprendere meglio la relazione che c’è fra le sequenze geniche e le righe
delle immagini basta pensare alle due immagini come a una la mutazione (genetica) dell’altra. Pensata la questione in questi termini, i ragionamenti successivi
saranno più chiari e lineari. L’algoritmo ottimizza l’allineamento globale di tutti
i caratteri delle stringhe in accordo ad una funzione di scoring che tiene presente di tutte le possibili mutazioni. In pratica, l’allineamento viene prodotto
attraverso due fasi: Fase1 la matrice (programmazione dinamica) dei punteggi
viene riempita fino all’ultima riga e colonna, Fase2 Backtracking (tracciamento
all’indietro) dal valore più alto dell’ultima colonna/riga fino a ritornare alla cella in prima posizione. Ogni cella della matrice contiene il massimo valore che
può essere raggiunto estendendo i precedenti allineamenti, ad esempio potremmo avere due stringhe di dimensione n e m, il valore che abbiamo nella cella
di indice (i, j) è il massimo valore dell’allineamento che si otterrebbe avendo a
disposizione due sotto stringhe di dimensione i e j. Entrando più nello specifico
se i due caratteri che si trovano rispettivamente in posizione i nella prima riga
e in posizione j nella seconda sono uguali, allora si dice che i due caratteri son
in una situazione di match, se questo non dovesse succedere è necessario esaminare i dintorni della cella (sopra e sinistra o north e west) per capire quale sia
la casella che porta ad avere un allineamento con valore maggiore.

2.2.1

Creazione della matrice dei punteggi

Passiamo ora alla descrizione dell’algoritmo in pseudo-codice per il riempimento
della matrice dei punteggi, una prima versione è disponibile alla consultazione
in Alg:2.1.
In output riceveremo una matrice di dimensioni n ∗ m, dove n e m sono rispettivamente la lunghezza di sequence1 e sequence2. A questo punto le stringhe
vengono analizzate sequenzialmente comparando carattere per carattere. Come
detto prima se i due caratteri sono identici alla casella viene dato un punteggio
equivalente alla casella sulla diagonale (sopra a sinistra) più il valore di match
(stabilito precedentemente con tecniche ben determinate), in caso contrario al
valore della cella sulla diagonale viene aggiunto il valore di mismatch e viene
esaminato il valore di north e west con l’aggiunta del gap, il valore massimo

i

i
i

i