Algorisme de Needleman-Wunsch

L'algorisme de Needleman–Wunsch és un algorisme àmpliament utilitzat en bioinformàtica per a l'alineament global de seqüències proteiques o nucleotídiques. L'algorisme va ser proposar per primera per Saul Needleman i Christian Wunsch el 1970.

L'algorisme de Needleman–Wunsch és un exemple de programació dinàmica i es considera la primera aplicació de programació dinàmica en la comparació de seqüències biològiques.

Funcionament de l'algorisme

La puntuació per a l'alineació de seqüències a la matriu de similitud. Aquí, $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:

-	A	G	C	T
A	10	-1	-3	-4
G	-1	7	-5	-3
C	-3	-5	9	0
T	-4	-3	0	8

llavors, l'alineament:

AGACTAGTTAC
CGA---GACGT

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

$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)$
$=-3+7+10-3\times 5+7+-4+0+-1+0=1$

Per trobar l'alineament de major puntuació es crea una matriu bidimensional, $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:

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

$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*i
per j=0 fins longitud(B)
F(0,j) ← d*j
per 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) + d
Opció3 ← F(i, j-1) + d
F(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) + AlineamentA
AlineamentB ← B(j-1) + AlineamentB
i ← i - 1
j ← j - 1
}
sinó si (Puntuació == Puntuació Horitzontal + d)
{
AlineamentA ← A(i-1) + AlineamentA
AlineamentB ← "-" + AlineamentB
i ← i - 1
}
sinó (Puntuació == Puntuació Vertical + d)
{
AlineamentA ← "-" + AlineamentA
AlineamentB ← B(j-1) + AlineamentB
j ← j - 1
}
}
mentre (i > 0)
{
AlineamentA ← A(i-1) + AlineamentA
AlineamentB ← "-" + AlineamentB
i ← i - 1
}
mentre (j > 0)
{
AlineamentA ← "-" + AlineamentA
AlineamentB ← B(j-1) + AlineamentB
j ← j - 1
}

Vegeu també

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

Enllaços externs

• Algorisme de Needleman-Wunsch en codi Ruby Arxivat 2006-11-01 a Wayback Machine.
• Implementació de l'algorisme de Needleman-Wunsch en Java Arxivat 2007-03-28 a Wayback Machine.
• Explicació del funcionament de l'algorisme de Needleman-Wunsch
• Explicació del funcionament de l'algorisme de Needleman-Wunsch Arxivat 2011-05-15 a Wayback Machine.