Algorisme de Needleman-Wunsch

La puntuació per a l'alineació de seqüències a la matriu de similitud. Aquí, ${\displaystyle S(i,j)}$ correspon a la matriu de similitud que recull la similitud entre caràcters i i j, en la qual s'utilitza una penalització per buit anomenada d. Per exemple, si la matriu de similitud és:

llavors, l'alineament:

AGACTAGTTACCGA---GACGT

amb una penalització per buit de d=-5, tindria la següent puntuació:

${\displaystyle S(A,C)+S(G,G)+S(A,A)+3\times d+S(G,G)+S(T,A)+S(T,C)+S(A,G)+S(C,T)}$ ${\displaystyle =-3+7+10-3\times 5+7+-4+0+-1+0=1}$ 

Per trobar l'alineament de major puntuació es crea una matriu bidimensional, ${\displaystyle F_{ij}}$ , que conté una columna per cada caràcter de la seqüència A i una línia per a cada caràcter de la seqüència B. Per a cada posició de la matriu F, l'algorisme calcula la l'alineament òptim per als primers i caràcters de la seqüència A i els j primers caràcters de la seqüència B. Els valors òptims de l'alineament es calculen de la manera següent:

${\displaystyle F_{0j}=d*j}$ ${\displaystyle F_{i0}=d*i}$ 

${\displaystyle F_{ij}=\max(F_{i-1,j-1}+S(A_{i},B_{j}),F_{i,j-1}+d,F_{i-1,j}+d)}$ 

A continuació es mostra el pseudocodi de l'algorisme per al càlcul de la matriu F:

per i=0 fins longitud(A)F(i,0) ← d*iper j=0 fins longitud(B)F(0,j) ← d*jper i=1 fins longitud(A)per j = 1 fins longitud(B){Opció1 ← F(i-1,j-1) + S(A(i), B(j))Opció2 ← F(i-1, j) + dOpció3 ← F(i, j-1) + dF(i,j) ← max(Opció1, Opció2, Opció3)}

Un cop que la matriu F ha estat calculada, es procedeix a la reconstrucció de l'alineament de seqüències que s'inicia a partir de l'última posició de la matriu F. El valor d'aquesta posició es compara amb els valors de Opció1, Opció2, Opció3 per determinar el seu origen. Si l'opció triada és l'Opció1, llavors A(i) i B(j) són alineades. En canvi, si s'escull l'Opció2, A(i) s'alinea amb un buit, mentre que si s'escull l'Opció3, B(j) s'alinea amb un buit. A vegades, existeixen diverses opcions vàlides que donen lloc a alineaments òptims alternatius, tots ells vàlids.

AlineamentA ← ""AlineamentB ← ""i ← longitud(A)j ← longitud(B)mentre (i > 0 i j > 0){Puntuació ← F(i,j)Puntuació Diagonal ← F(i - 1, j - 1)Puntuació Vertical ← F(i, j - 1)Puntuació Horitzontal ← F(i - 1, j)if (Puntuació == Puntuació Diagonal + S(A(i-1), B(j-1))){AlineamentA ← A(i-1) + AlineamentAAlineamentB ← B(j-1) + AlineamentBi ← i - 1j ← j - 1}sinó si (Puntuació == Puntuació Horitzontal + d){AlineamentA ← A(i-1) + AlineamentAAlineamentB ← "-" + AlineamentBi ← i - 1}sinó (Puntuació == Puntuació Vertical + d){AlineamentA ← "-" + AlineamentAAlineamentB ← B(j-1) + AlineamentBj ← j - 1}}mentre (i > 0){AlineamentA ← A(i-1) + AlineamentAAlineamentB ← "-" + AlineamentBi ← i - 1}mentre (j > 0){AlineamentA ← "-" + AlineamentAAlineamentB ← B(j-1) + AlineamentBj ← j - 1}

• Algorisme de Smith-Waterman
• BLAST
• Distància de Levenshtein