Tesi Robotica Un co-processore per Stereo-Matching: Architettura | Page 38

i

i
“LP_Tesi” — 2011/9/9 — 21:20 — page 38 — #38

i

3.1. CREAZIONE DELLA MATRICE DEI PUNTEGGI

i

38

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 in posizione i e j sono uguali allora ci ritroviamo
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.

3.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:3.1.
Algoritmo 3.1 Needleman–Wunsch
1
2
3

for i = 1 to length(sequence1){
for j = 1 to length(sequence2){
north <- M(i-1,j) + gap

4

if( character1 = character2 )
diagonal <- M(i-1,j-1) + match
else
diagonal <- M(i-1,j-1) + mismatch
endif

5
6
7
8
9
10

west <- M(i,j-1) +gap

11
12

M(i,j) <- max(north, diagonal, west)

13

}

14
15

}

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

i

i
i

i