Buracos nas Pontas

Uma seqüência de DNA pode ser continuação da outra, como por exemplo:

ATCGTCCCACACGTAGACCCTGC e ACCCTGCCGGTCTATTGCAAC

Mas o algoritmo básico poderia não nos mostrar este fato. Por penalizar todos os buracos com -2 pontos, este alinhamento (uma cadeia ``encaixando'' na extremidade da outra) não teria a melhor pontuação. Se levarmos este fato em consideração, poderíamos modificar o algoritmo para não cobrar por buracos nas extremidades. No exemplo acima, o alinhamento ótimo ficaria:

ATCGTCCCACACGTAGACCCTGC______________ ________________ACCCTGCCGGTCTATTGCAAC

Para não cobrarmos por buracos no início das seqüêcias, basta inicializarmos a primeira linha e a primeira coluna da matriz com zeros. Uma vez que a posição (i, 0) da matriz nos dá o valor do alinhamento ótimo entre s₁[1..i] com buracos anteriores ao primeiro caracter de s₂, ao inicializarmos a coluna 0 com zeros não estaremos cobrando por buracos na extremidade da s₂. Raciocínio análogo para a linha 0 em relação a buracos na extremidade de s₁. Para não cobrarmos por buracos no final das seqüêcias, basta tomarmos o maior valor dentre a última linha e a última coluna como a similaridade e construirmos o alinhamento ótimo a partir dele. Sendo m o comprimento de s₁, a posição (m, j) conterá o valor do alinhamento ótimo entre s₁[1..m] (o que equivale a s₁ por inteira) e s₂[1..j]. Sendo n comprimento de s₂ e j<n, teremos comparado s₁ a um prefixo de s₂. Adotando (m, j) como a similaridade entre as duas cadeias, não levaremos em conta a comparação de s₁ com os caracteres finais de s₂. Podemos colocar 1 buraco ao final de s₁ para cada caracter de s₂ não comparado. Desta forma, não estaremos penalizando os buracos ao final de s₁. Raciocínio análogo para a coluna n da matriz.