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

i

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

i

2.2. N-W ALGORITHM

i

65

Algoritmo 2.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

}

fra questi tre diventerà il contenuto della casella analizzata. Ecco un esempio (Tab:2.1) di come la matrice può presentarsi alla fine della computazione,
avendo come input: sequence1 = EDECE, sequence2 = ADCE, match = 2,
mismatch = 0, gap = -1.

-

A
D
C
E

0
-1
-2
-3
-4

E

-1
0
-1
-2
-1

D

-2
-1
2
1
0

E

-3
-2
1
2
3

C

-4
-3
0
3
2

E

-5
-4
-1
2
-5

Tabella 2.1: Allineamento
Ma questa è solo una delle possibili implementazione dell’algoritmo, a voler
essere precisi, pur essendo molto semplice, alcune specializzazioni di questo algoritmo in campo didattico sono molto utili, primo fra tutti l’algoritmo per la
ricerca della più lunga sotto sequenza comune (LCS), basta fissare match=1,

i

i
i

i