Comparação Rápida

Nosso método de comparação rápida é inspirado no utilizado em [MS 94]. O primeiro passo é codificar os fragmentos de DNA na forma de dígitos. Definimos A=0, C=1, G=2 e T=3 (Figura 6 a).

Definimos, também, um tamanho para as janelas, isto é, subseqüências contínuas dos fragmentos. Vamos assumir, por exemplo, que nossas janelas tenham tamanho 8. A idéia é avaliar quantas janelas dois fragmentos, f_i e f_j, têm em comum. Se o número de janelas comum for suficientemente grande (acima de um parâmetro $\beta$), podemos dizer que os fragmentos são suficientemente parecidos para serem avaliados por programação dinâmica na fase posterior, ou seja, estes fragmentos têm grande probabilidade de serem similares ( $Sim(f_{i}, f_{j})>\alpha$).

Analisamos todas as janelas de cada fragmento f_i. Suponha, por exemplo, que encontremos a janela ATCATGCT, que codificada torna-se 03103213. Associamos uma tabela de hashing t_i a f_i, na forma de um vetor de bits de tamanho h. Para obtermos um bom espalhamento, h deve ser um número primo e razoavelmente grande, de modo que não haja muitas colisões. Para prosseguir com nosso exemplo, tomemos h=2003. Então, para indicar a presença da janela ATCATGCT no fragmento f_i:

t_i[pos] = 1
onde
pos = (03103213)₄ mod 2003 = 13543 mod 2003 = 1525

Deste modo, obtemos tabelas de hashing para cada fragmento, como indicado na Figura 6 b. Para saber se dois fragmentos têm um número suficientemente grande de janelas comuns, aplicamos uma operação AND entre seus vetores de hashing e contamos o número de bits 1, verificando se este total é maior ou igual ao parâmetro $\beta$.

Podemos agora criar um grafo G tal que a cada vértice é associado um fragmento. Há uma aresta conectando dois vértices se seus fragmentos associados possuem um número satisfatório de janels comuns.

Note que nosso sistema de hashing não trata colisões, ou seja, duas janelas diferentes w₁ e w₂, presentes em f_i, poderiam alterar um mesmo bit em t_i. Porém, como estamos interessados em um método ``grosseiro'' de comparação, cuja função é apenas eliminar o uso da comparação por programação dinâmica entre seqüências muito diferentes, tal fato não se torna um problema.

Figure: (a) Codificação em base 4. (b) Tabelas de Hashing.