Algoritmo Needleman-Wunsch
Origem: Wikipédia, a enciclopédia livre.
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 70 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 sequencias biológicas.
O primeiro elemento necessário é uma matriz de pesos (scores). Aqui, 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 matrix 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 matrix F é alocada. Há uma coluna para caractere da sequencia A e uma linha para cada caractere da sequencia B.
Na medida que o algoritmo avança, a matrix Fij é 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: F0j = d * j Fi0 = d * i Recursão, baseada no princípio de otimização: Fij = max(Fi − 1,j − 1 + S(Ai − 1,Bj − 1),Fi,j − 1 + d,Fi − 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 matrix F é calculada, o elemento na posição do canto direito inferior da matrix é 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 }
[editar] Links Externos
- [1] Java Implementation of the Needleman-Wunsch Algorithm.
- Java Applet
- [2] Needleman-Wunsch Algorithm as Ruby Code.
- Java Implementation of the Needleman-Wunsch Algorithm (JDK Version >= 1.4 Needed) by Peter Petrov
- [3] A clear explanation of NW and its applications to sequence alignment
[editar] Veja Também
- BLAST
Referências
- ↑ Needleman SB, Wunsch CD (1970). "A general method applicable to the search for similarities in the amino acid sequence of two proteins". Journal of Molecular Biology 48 (3): 443.