Comparando Fragmentos

As sobreposições podem ser avaliadas com o uso de um algoritmo por nós tratado em [SF 98]. Trata-se de uma adaptação do:

Problema 3 (Maior Subseqüência Comum)   Dadas duas seqüências $X = \langle x_{1}, x_{2},..., x_{m} \rangle$ e $Y = \langle y_{1}, y_{2},..., y_{n} \rangle$, encontrar a maior subseqüência comum entre X e Y, ou seja, a maior seqüência estritamente crescente $\langle i_{1}, i_{2},..., i_{k} \rangle$ tal que, para todo j = 1, 2,..., k, x_ij=y_ij.

Um algoritmo de programação dinâmica para a resolução do problema encontra-se na Figura 4. Ele devolve dois vetores b e c. O vetor b atua como um log das operações, permitindo reconstruir a máxima subseqüência comum. Já c[i, j] nos dá o comprimento da maior subseqüência entre $\langle x_{1},..., x_{i} \rangle$ e $\langle y_{1},..., y_{j} \rangle$.

Figure: Algoritmo para encontar a Maior Subseqüência Comum.

Uma modificação de MaxSC(X, Y) nos dá o algoritmo para a função Sim(X, Y) (vista anteriormente na definição do Problema 2). Tal algoritmo (Figura 5) leva em consideração pequenos erros nas strings de entrada. A função p(x_i, y_j) compara os dois caracteres x_i e y_j, retornando 1 caso sejam iguais ou -1 caso contrário. Assim, torna-se possível alinhar nucleotídeos diferentes, penalizando a similaridade entre os fragmentos de DNA toda vez que isso ocorre. Além disso, é possível inserir ``buracos'' nos fragmentos, de modo a maximizar a similaridade. Porém, quando um buraco é inserido, uma penalização g é removida da similaridade.

Este algoritmo, bem como o problema a ele associado, possui várias variantes. Maiores detalhes podem ser encontrados em [MS 94] e [SF 98].

Figure: Algoritmo para encontrar a similaridade entre duas seqüências.