Algoritme Needleman-Wunsch

Archiu:Needleman-Wunsch pairwise sequence alignment.png

Algoritme de Needleman-Wunsch.

El algoritme de Needleman-Wunsch servix per a realisar alineamientos globals de dos seqüències. Se sol utilisar en l'àmbit de la bioinformática per a alinear seqüències de proteïnas 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 alineamiento.

Les dos seqüències a alinear, cridades A i B en els eixemples, de llongitut ___MATH_0___ i ___MATH_1___, estan formades per elements d'un alfabet finito 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 ___MATH_2___ indique la similitut entre els elements i i j de l'alfabet usat. Si el nostre alfabet de símbols no anara finito, en lloc d'una matriu podríem usar una funció ___MATH_3___ 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:

___MATH_4___

I llavors el següent alineamiento:

AGACTAGTTAC
CGA---GACGT

en una penalisació per buit de ___MATH_5___ nos tornaria com a solució òptima:

___MATH_6___

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 alineamiento. Les dimensions de la matriu F són el número d'elements en la seqüència A i el de B (___MATH_7___).

En cada iteración de l'algoritme rep valor un element de la matriu F. El valor que rep l'element ___MATH_8___ 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 (___MATH_9___, en ___MATH_10___ i ___MATH_11___) contindrà la puntuació per al alineament òptim d'abdós seqüències.

  Inici de l'algoritme:
  ___MATH_12___
  ___MATH_13___
  Recursión per a obtindre el següent element de forma òptima:
  ___MATH_14___

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, ___MATH_15___, 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 ___MATH_16___ devem comparar ___MATH_17___ i ___MATH_18___. Si l'element usat és ___MATH_19___, llavors ___MATH_20___ s'ha alineat en un buit; si és ___MATH_21___, llavors ___MATH_22___ s'ha alineat en un buit; i si no, si l'element elegit és ___MATH_23___, els elements ___MATH_24___ i ___MATH_25___ 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

• Implementació de l'algoritme en Java
• Una atra implementació en Java