Para alinhar duas sequências temos que fazer as letras (correspondentes de bases ou aminoácidos) formarem pares com as letras da outra sequência ou se a letra não apresentar correspondencia na outra seqências fazemos ela parear com o gap (sinal -). O sinal de gap indica que temos uma alteraçao (mutação) em uma das sequências, e a mutaçao pode ser que base faltando em um sequência (a base foi deletada), ou que temos uma base a mais (a base foi adicionada). O procedimento de alinhar duas sequências pode levar muito tempo. Para cada duas sequências alinhadas existem m x n alinhamentos possíveis, sendo m e n o comprumento das duas sequências.

 Para fazer um alinhamento portanto seria necessário produzir todas as possibilidades de alinhamento e depois calcular para cada uma delas qual a opção que retornou um alinhamento com melhor pontuação (score) segundo um algortimo para calcular esses scores em alinhamentos. Entretanto produzir todos os alinhamentos possíveis levaria muit tempo mesmo para um super computador.

Vamos usar a programação dinâmica para resolver esse problema (Artigo). Para realizar essas tarefa iremos utilizar de uma estratégia que será dividir o problema complexo de alinhar duas sequências para um problema muito menor e mais facil de resolver que seria alinhar duas bases (ou dois aminoácidos). Essa tarefa menor para o computador é muito simples, iremos armazenar todas as soluções possíveis e depois montar somente um alinhamento (“o melhor alinhamento”) usando essas respostas de cada problema.

Iremos resolver o problema de alinhar as sequências AND e SEND usando duas matrizes. Uma matriz é a a matriz de pontuaçao,e a outra matriz é a matriz que armazena qual o caminha usar para fazer o melhor alinhamento dessas duas sequencias. Vejam como contruir essas duas matrizes na figura 1.

Colocamos cada letra em uma célula. As sequência AND ficará nas linhas enquanto que a sequência SEND ficará nas colunas. A célula 1,1 de cada matriz não irá conter informação, na matriz de score será atribiudo o valor inicial zero(0), enquanto que na matriz traceback será usado um sinal que o alinhamento terminou. Essa informação será usanda quando estivermos construíndo o alinhamento das duas sequências no final. A célula vazia 1,1 representa o gap que cada uma das letras pode formar par. Inicialmente devemos verificar a possibilidade da sequencia toda (AND ou SEND) alinhar somente com gap.

Preenchendo a linha 1 vamos colocar o valor da célula da esquerda mais o valor de penalidade do gap (-10), portanto célula 1,2 recebe 0 -10 = -10. Continuamos esse precesso até preencher toda a linha.

célula 1,1 recebe 0 – 10 = -10;

célula 1,2 recebe -10-10 = -20;

célula 1,3 recebe -20-10 = -30

célula 1,4 recebe -30-10 = -40

Agora valor preencer a coluna 1.

O memso processo é feito para preencher a coluna 1 nas diferentes linhas:

célula 2,1 recebe 0 – 10 = -10;

célula 3,1 recebe -10-10 = -20;

célula 4,1 recebe -20-10 = -30

Vamos agora alinhar a letra A da paravra AND com cada uma das letras da palavra SEND. Cada um dessas tentativas será um pequenco problema do nosso problema maior. Para fazer isso usamos a informaçao de 3 células (1,1; 1,2; 2,1) cada uma dessas células contém uma valor (0; -10; -10). Isso é obrigatório, toda vez que eu for preencher uma nova célula eu devo usar os valores das tr6es células anteriores que tem que estar preenchidas..

Devemos considerar todas as três possibilidades de alinhamento

“A” pareando com “S”

“A” pareando com gap

“S” pareando com gap

e para fazer isso iremos usar o maior valor de três equações

diag = C(i-1, j-1) + (score de pareamento)

up = C(i-1, j) + (penalidade do gap)

left = C(i, j-1) + (penalidade do gap)

A equação que retornar a maior pontuação será usada para preencher a céula C(i, j) e indicará o caminho do traceback (qual é o pareamento da letra)

Vamos usar essas regras

diag = C(1,1) + S(2,2) = 0 + 1 = 1,

up = C(1, 2) + gap = -10 + (-10) = -20,

left = C(2, 1) + gap = -10 + (-10) = -20

Após preencher todas as duas matrizes vamos recumerar o melor alinhamento. O valor encontrado na ultima célula da matriz de pontuação é o score do melhor alinhamento. Para recuperar esse alinhamento devemos seguir as direçoes indicadas pela matriz traceback. Diag representa para parearmos as letras das duas sequencias, a corresponde da linhae coluna; up significa para parearmos a letra da sequências na vertical (AND) com um gap; left significa para parearmos a letra da sequências na horirontal (SEND) com um gap.

Seguindo a matriz traceback encontraremos socore 3 o alinhamento entre AND e SEND igual:

Pos1	Pos2	Pos3	Pos4
A	-	N	D
S	E	N	D