O Algoritmo Básico

Vamos agora descrever o algoritmo que calcula o alinhamento ótimo. Tomemos como exemplo as seqüências ``AAAC'' e ``AGC''. Ao alinharmos a última coluna, teremos três possibilidades:

Este esquema nos dá um algoritmo recursivo para o cálculo do alinhamento ótimo. Chamando de Sim (s₁, s₂) a similaridade entre s₁ e s₂ e Max (i,j,k) o maior valor dentre i, j e k, temos:

Sim(AAAC, AGC)=Max(Sim(AAA,AG)+1, Sim(AAAC, AG)-2, Sim(AAA, AGC)-2)

Há um grande inconveniente neste método: ele gera um número exponencial de chamadas recursivas. Teremos um total de 2^m+n chamadas onde m e n são os tamanhos das seqüências. Mas com o uso da programação dinâmica podemos impedir tal quantidade de chamadas. Esta técnica nos mostra que várias chamadas são iguais (por exemplo, Sim(AAA, A) será solicitada mais de uma vez, gerando sempre o mesmo resultado!). A melhor maneira de comparar as seqüências é fazer uso da seguinte matriz:

Convencionamos s[a..b] como a subseqüência de s que vai do caracter na a-ésima posição ao caracter na b-ésina posição. Nesta matriz, o valor contido na linha i coluna j é a similaridade entre o prefixo s₁[1..i] e o prefixo s₂[1..j]. Logo, sendo m e n os tamanhos das cadeias em estudo, a posição (m, n) da matriz contém o valor da similaridade de s₁ e s₂. As setas indicam a origem do valor daquela posição. As setas horizontais indicam que o caracter da j-ésima posição de s₂ foi pareado com um buraco inserido em s₁ (penalização de -2). As setas verticais indicam que o caracter da i-ésima posição de s₁ foi pareado com um buraco em s₂ (penalização de -2). Já a seta diagonal indica que pareamos o caracter da i-ésima posição de s₁ com o da j-ésima posição de s₂ (1 se s₁ = s₂ e -1 se forem diferentes). Assim, as ``setas'' indicam, a partir da posição (m, n) da matriz, como devemos alinhar s₁ e s₂.