Algoritme Needleman-Wunsch

El algoritme de Needleman-Wunsch servix per a realisar allineaments globals de dos seqüències. Se sol utilisar en l'àmbit de la bioinformàtica per a alinear seqüències de proteïnes o d'àcits nucleicos. Va ser propost per primera volta en 1970, per Saul Needleman i Christian Wunsch. Es tracta d'un eixemple típic de [[Programació dinàmica (computació)|programació dinàmica]]. L'algoritme funciona de la mateixa manera independentment de la complexitat o llongitut de les seqüències i garantisa l'obtenció del millor allineament.[1]
Les dos seqüències a alinear, cridades A i B en els eixemples, de llongitut i , estan formades per elements d'un alfabet finit de símbols. L'algoritme necessita saber qué símbols són diferents entre sí i quins són iguals. Podem utilisar una matriu quadrada (S) per a este propòsit, en la que cada element indique la similitut entre els elements i i j de l'alfabet usat. Si el nostre alfabet de símbols no anara finit, en lloc d'una matriu podríem usar una funció que tinguera com a paràmetros abdós símbols a comparar i que la seua eixida anara la similitut entre abdós. També es necessita un atre paràmetro (d) que nos indique cóm anem a valorar que un símbol no quede alineat en un atre i que en el seu lloc s'utilise un buit.
Per eixemple podem definir la següent matriu:
I llavors el següent allineament:
AGACTAGTTAC CGA---GACGT
en una penalisació per buit de nos tornaria com a solució òptima:
Per a determinar la puntuació òptima i poder reconstruir el alineament que tornaria eixa puntuació es necessita una atra matriu, F, que almagasena els resultats parcials de cada possible allineament. Les dimensions de la matriu F són el número d'elements en la seqüència A i el de B ().
En cada iteració de l'algoritme rep valor un element de la matriu F. El valor que rep l'element representa la puntuació obtinguda en alinear de forma òptima els primers i elements d'i els primers j de B. Quan l'algoritme termine, l'últim element de F (, en i ) contindrà la puntuació per al alineament òptim d'abdós seqüències.
Inici de l'algoritme: Recursió per a obtindre el següent element de forma òptima:
La matriu F es calcula en el següent algoritme:
for i=0 to length(A)-1
F(i,0) <- d*i
for j=0 to length(B)-1
F(0,j) <- dj
for i=1 to length(A)
for j = 1 to length(B)
{
Choice1 <- F(i-1,j-1) + S(A(i), B(j))
Choice2 <- F(i-1, j) + d
Choice3 <- F(i, j-1) + d
F(i,j) <- max(Choice1, Choice2, Choice3)
}
Quan l'algoritme acaba tenim calculada la matriu F; el resultat és la puntuació tornada pel millor alineament possible, d'acort als paràmetros que hem definit. Per a obtindre la seqüència es necessita eixecutar el següent algoritme, que fa us de la matriu F. Este algoritme comença per l'últim element, , i va retrocedint fins a aplegar a un element de la primera fila o la primera columna de F. En cada pas es comparen 3 elements de F per a vore quin d'ells és el que s'ha seguit en la solució òptima. Per a cada devem comparar i . Si l'element usat és , llavors s'ha alineat en un buit; si és , llavors s'ha alineat en un buit; i si no, si l'element elegit és , els elements i han segut alineats. És important destacar que el que dos elements siguen alineats no implica necessàriament que siguen iguals; significa que entre eixa possibilitat, alinear en buits o alinear símbols diferents, eixa era la millor opció. El pseudo-algoritme que permet obtindre el alineament correcte és el següent:
AlignmentA <- ""
AlignmentB <- ""
i <- length(A)
j <- length(B)
while (i > 0 AND j > 0)
{
Score <- F(i,j)
ScoreDiag <- F(i - 1, j - 1)
ScoreUp <- F(i, j - 1)
ScoreLeft <- F(i - 1, j)
if (Score == ScoreDiag + S(A(i), B(j)))
{
AlignmentA <- A(i-1) + AlignmentA
AlignmentB <- B(j-1) + AlignmentB
i <- i - 1
j <- j - 1
}
else if (Score == ScoreLeft + d)
{
AlignmentA <- A(i-1) + AlignmentA
AlignmentB <- "-" + AlignmentB
i <- i - 1
}
otherwise (Score == ScoreUp + d)
{
AlignmentA <- "-" + AlignmentA
AlignmentB <- B(j-1) + AlignmentB
j <- j - 1
}
}
while (i > 0)
{
AlignmentA <- A(i-1) + AlignmentA
AlignmentB <- "-" + AlignmentB
i <- i - 1
}
while (j > 0)
{
AlignmentA <- "-" + AlignmentA
AlignmentB <- B(j-1) + AlignmentB
j <- j - 1
}Es pot demostrar formalment que tant el temps d'eixecució com l'espai necessari per a eixecutar l'algoritme són d'orde O(nm). Per a alguna aplicacions, sobretot en bioinformàtica, el requeriment d'espai és prohibitivo, ya que s'alineen seqüències molt llargues. Existix una optimisació d'este algoritme, denominada algoritme de Hirschberg, que solament necessita espai de l'orde O(m+n), pero a costa d'incrementar el temps de computació.
Llocs externs
Referències
- ↑ Needleman, S.B. and Wunsch, C.D.(1970).«A general method applicable to the search for similarities in the amino acid sequence of two proteins».Journal of molecular biology.Elsevier.48: 443-453.
- Este artícul conté una traducció derivada de «Algoritmo Needleman-Wunsch» de Wikipedia en castellà publicada baix la Llicència de documentació lliure de GNU i la Llicència Creative Commons Reconeiximent-CompartirIgual 4.0 Internacional.