Algoritmo Needleman-Wunsch

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa

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, 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:

- 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:

  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)
  = -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 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:
  F_{0j} = d*j
  F_{i0} = d*i
  Recursão, baseada no princípio de otimização:
  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
  }

Referências

Bibliografia[editar | editar código-fonte]

  • Korf, Ian;Yandell, Mark;Bedell, Joseph. Blast. Beijing: O'Reilly, 2003. 339 p. ISBN 0-596-00299-8
  • Markel, Scott; León, Darryl. Sequence Analysis. Beijing: O'Reilly, 2003. 286 p. ISBN 0-596-00494-X
  • Setubal, João; Meidanis, João. Introduction to Computational Molecular Biology. Boston: PWS Publishing Company, 1997. 296 p. ISBN 0-534-95262-3

Ver também[editar | editar código-fonte]

Ligações externas[editar | editar código-fonte]