Alinhamento Global - Needlman-Wunsch

Define-se alinhamento global como sendo o alinhamento em toda a extensão da sequência. De forma a retirar algum significado dos alinhamentos são usados algoritmos como o de Needleman-Wunsch na sua classificação.  

Este algoritmo é utilizado para alinhar globalmente pares de sequências, maximizando o número de alinhamentos individuais (um-para-um) que são iguais (match) e minimizando os espaçamentos (gap).

Para exemplifica o funcionamento deste algoritmo são escolhidas duas sequências:

CGCTATAT (sequência #1)

TATACTA (sequência #2)

Temos que M = 7 (comprimento da sequência #1) e N = 6  (comprimento da sequência #2)

O Needleman-Wunsch é um algoritmo de programação dinâmica que se processa em três passos: inicialização, preenchimento da matriz (scoring) e Alinhamento  (traceback).

1. Inicialização
   
   
   • O primeiro passo é criar a matriz com M + 1 colunas (uma coluna é para o espaçamento) e N + 1 linhas onde M e N correspondem ao comprimento das sequências a alinhar.
   • Inicializar a matriz de acordo com a condição inicial, sendo que F(i,j) é a Função de Pontuação para preenchimento da matriz e d a pontuação do espaçamento:
     
     
     
     Que se traduz na seguinte matriz inicializada:
     
     
     
2. Preenchimento da Matrix (scoring)
   
   
   • Escolher a Função de Pontuação e a Matriz de Mérito
     
   • Preencher o resto da tabela de acordo com a função de pontuação e a matriz de mérito.
     
     
     
     A matriz totalmente preenchida fica da seguinte forma:
     
     
3. Alinhamento (traceback)
   
   
• A pontuação máxima do alinhamento para as duas sequências é 10. O traceback determina o alinhamento actual que resulta na pontuação máxima. É de notar que poderá haver múltiplos alinhamentos com pontuação máxima. 
• Começar na posição M,N da matriz (esta caso existe um 10 nesta posição) e olhar para as células vizinhas que podem ser as precedentes directos de acordo com a seguinte regra de alinhamento:
  - Diagonal: x_i alinha com y_i;
  - Cima: y_i alinha com espaço;
  - Esquerda: x_i alinha com espaço;
  
   Na realidade, para o primeiro passo, significa olhar para cima (y_i alinha com espaço).
  
  
• Seguir todo o caminho até não existirem mais precedentes.
  
  
  O valor na posição M,N é dado pela soma das parcelas correspondentes à pontuação de cada alinhamento individual.

 Segue-se uma animação, que ajuda compreender o funcionamento deste algoritmo para uma alinhamento entre estas duas seqências de ADN:

O mesmo algoritmo pode ser aplicado a sequências de aminiácidos como na próxima animação: