Obtendo o Alinhamento Ótimo com Economia de Espaço

Acima, obtivemos a similaridade entre duas seqüências. Resta obtermos o alinhamento ótimo entre duas cadeias s₁ e s₂. Trata-se de uma tarefa mais complicada pois, no algoritmo antigo, tínhamos em mãos toda a matriz, algo que não ocorre agora. Faremos uso de um algoritmo recursivo para resolver esta questão. Trata-se da estratégia da divisão e conquista, isto é, transformar um problema maior em dois subproblemas menores e, a seguir, juntar as soluções.

Note que a base T de s₁, na figura acima, pode ser alinhada de duas formas diferentes:

1.

Ela pode ser alinhada com uma base j de s₂ (, neste exemplo).

2.

Ela pode ser alinhada com um buraco de s₂ (, neste exemplo).

Para uma determinada base i de s₁, tendo decidido qual o caso em questão (1 ou 2) e determinada a posição j em s₂, o alinhamento ótimo total entre as duas seqüêcias pode ser obtido da seguinte forma:

1.

2.

Só precisamos determinar o método com que a posição j (bem como as situações 1 e 2) é encontrada. Para uma dada base i de s₁, precisamos encontrar pontuações ótimas entre o prefixo s₁[1..(i-1)] e os prefixos de s₂. Também precisamos encontrar as pontuações ótimas entre o sufixo s₁[(i+1)..m] e os sufixos de s₂. Munidos destes valores, poderemos determinar qual posição j nos dá o melhor alinhamento entre as duas cadeias. Para encontrarmos tais valores, basta usarmos o algoritmo que encontra a similaridade máxima entre duas seqüências (já visto anteriormente). Deste modo, a cada passo, tomamos i como sendo a metade da cadeia 1, analisamos qual seu melhor alinhamento e, em seguida, buscamos o alinhamento ótimo entre os prefixos determinado pela própria posição i e pela recém encontrada j, bem como seus sufixos. Observe o exemplo abaixo:

No exemplo acima, a última linha da tabela Best Score nos dá os alinhamentos ótimos entre o prefixo s₁[1..3] com todos os prefixos de s₂ (s₂[vazio], s₂[1..1], s₂[1..2], ...s₂[1..7]). Já a última linha da tabela Best Score Reverso nos dá os alinhamentos ótimos entre o sufixo s₁[5..7] e todos os sufixos de s₂ (s₂[1..7], s₂[2..7], ...s₂[vazio]). O melhor alinhamento é dado pela posição j=4:

prefixo[4] + sufixo[4] + Comp(s_l[i=4] e s₂[j=4])

ou seja

-1+(-1)+1=-1