Economia de Espaço em Memória

Seqüências de DNA são muito longas. Imaginemos a comparação de duas cadeias com 100000 bases cada. Nossa matriz teria 100000 * 100000 = 10000000000 posições. Se cada posição ocupar 1 byte de memória teremos um gasto de 10000000000 bytes = 10 gigabytes! Mas há uma forma de diminuir drasticamente este número obtendo espaço linear, proporcional a soma das seqüências de entrada. Imaginemos nossa matriz mxn substituída por uma matriz 1xn. Podemos realizar a mesma tarefa com esta matriz menor, basta repararmos que cada linha da matriz antiga é obtida imediatamente de sua linha antecessora.

Podemos notar que a pequena matriz de uma linha, que antes equivalia a primeira linha da matriz maior, depois de algumas iterações, tornou-se igual a segunda linha da grande matriz. Repetindo o mesmo processo, a matriz menor torna-se semelhante a última linha da maior de onde retira-se a similaridade. Notamos que para isso usamos a propriedade mostrada no diagrama: uma determinada posição X da matriz é obtida do máximo entre:

1.

Posição A somada com a comparação entre os caracteres s₁[i] e s₂[j] (1 se igual e -1 para caracteres diferentes).

2.

Posição B -2 (buraco em s₂).

3.

Posição C -2 (buraco em s₁).

A posição auxiliar guarda o caracter B, perdido na interação anterior.