Algoritmo Needleman-Wunsch

O algoritmo Needleman–Wunsch tem por objetivo realizar o alinhamento de seqüências global de duas seqüências (denominadas aqui de A e B). Este algoritmo é frequentemente utilizado em Bioinformática para alinhar seqüências de proteínas ou nucleotídeos. O algoritmo foi proposto na década de 1970 por Saul Needleman e Christian Wunsch.^[1]

Este algoritmo é um exemplo de programação dinâmica e foi a primeira aplicação desta técnica a comparação de sequências biológicas.

O primeiro elemento necessário é uma matriz de pesos (scores). Aqui, ${\displaystyle S(i,j)}$ mede a similaridade entre os caracteres i e j. Usa-se uma penalidade para espaços (gap penalty) linear d. Um exemplo de matriz seria:

então o alinhamento:

  AGACTAGTTAC  CGA---GACGT

com gap penalty de -5, deveria ter o score:

  ${\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}$

Para encontrar o alinhamento com o maior score, uma matriz F é alocada. Há uma coluna para caractere da sequência A e uma linha para cada caractere da sequência B.

À medida que o algoritmo avança, a matriz ${\displaystyle F_{ij}}$ é preenchida com o score ótimo do alinhamento entre os i primeiros caracteres de A e os j primeiros de B. O princípio de optimização é aplicado como segue:

  Base:  ${\displaystyle F_{0j}=d*j}$  ${\displaystyle F_{i0}=d*i}$  Recursão, baseada no princípio de otimização:  ${\displaystyle F_{ij}=\max(F_{i-1,j-1}+S(A_{i-1},B_{j-1}),F_{i,j-1}+d,F_{i-1,j}+d)}$

O pseudo-código para o algoritmo que calcula F é como segue (índice 0 representa 1a posição):

  for i=0 to length(A)-1    F(i,0) ← d*i  for j=0 to length(B)-1    F(0,j) ← d*j  for i=1 to length(A)    for j = 1 to length(B)    {      Choice1 ← F(i-1,j-1) + S(A(i-1), B(j-1))      Choice2 ← F(i-1, j) + d      Choice3 ← F(i, j-1) + d      F(i,j) ← max(Choice1, Choice2, Choice3)    }

Quando a matriz F é calculada, o elemento na posição do canto direito inferior da matriz é o score máximo para qualquer alinhamento. Para descobrir qual é o alinhamento que de fato dá este score, deve-se iniciar uma caminhada da posição direita inferior e ir-se comparando este valor com as 3 possíveis fontes (Choice1, Choice2, e Choice3 acima) para descobrir-se de onde este veio. Se veio de Choice1, então A(i) e B(i) estão alinhados. Se veio de Choice2 então A(i) está alinhado com um gap, e se veio de Choice3 então B(i) está alinhado com o gap.

  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-1), B(j-1)))    {      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  }