Helsinki: os grafos de intervalos

Pesquisadores da Universidade de Helsinki, Finlândia, formalizaram a montagem de fragmentos como:

Problema 4   Dados um conjunto de fragmentos f₁, f₂,..., f_k e uma constante $\delta$ entre 0 e 1, encontrar a seqüência mais curta possível F tal que, para cada f_i, exista uma subcadeia de F cuja distância de edição¹ a f_i seja, no máximo, $\delta\vert f_{i}\vert$.

Para este problema, foi desenvolvido o SEQAIDS. A principal estrutura utilizada são os grafos de intervalo. Neste tipo de grafo, cada vértice representa um intervalo de elementos consecutivos $\langle e_{i}, e_{i+1},..., e_{j}\rangle$. Há uma aresta ligando dois vétices u e v se e somente se a intersecção entre seus intervalos correspondentes não for vazia. O peso associado à aresta é igual ao tamanho desta intersecção.

Usando um algoritmo de programação dinâmica, o sistema compara os fragmentos dois a dois. Este algoritmo foi modificado, de forma que leva tempo $O(\delta mn)$, onde m e n são os comprimentos dos fragmentos comparados e $\delta$ é uma constante proporcional a taxa de erro permitida. Um grafo G é criado, sendo cada um de seus vértices associado a um fragmento e cada aresta a indicação de sobreposição entre eles. SEQAIDS procura em G um subgrafo que seja uma grafo de intervalos e realiza a montagem a partir dele.