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.
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, 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:
- A G C T A 10 -1 -3 -4 G -1 7 -5 -3 C -3 -5 9 0 T -4 -3 0 8
então o alinhamento: AGACTAGTTAC CGA---GACGT com gap penalty de -5, deveria ter o score:
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 é 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:
Recursão, baseada no princípio de otimização:
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
Bibliografia
Ver também BLAST
Ligações externas Java Implementation of the Needleman-Wunsch Algorithm. Java Applet Needleman-Wunsch Algorithm as Ruby Code. Java Implementation of the Needleman-Wunsch Algorithm (JDK Version >= 1.4 Needed) by Peter Petrov A clear explanation of NW and its applications to sequence alignment
Categoria:Biologia computacional Categoria:Bioinformática Categoria:Algoritmos Categoria:Programação dinâmica