Um filtro sem perda para localização de repetições locais múltiplas dentro de certa distância de edição

Resumo:

A busca de similaridade em seqüências, notavelmente as seqüências biológicas, tem recebido atenção substancial nos últimos anos. Várias técnicas de filtragem e indexação vêm sendo criadas de forma a acelerar a obtenção de uma solução para o problema. Contudo, os trabalhos anteriores vem sendo realizados no sentido de acelerar os algoritmos de busca de padrão, busca de repetições em duas seqüências ou repetições que se repetem duas vezes na mesma seqüência, sem se preocupar de forma adequada com o caso de repetições múltiplas, reconhecidamente mais difícil. Se as repetições envolvidas são exatas, ou se permitem um certo número de substituições, ou ainda se encontram a uma distância máxima de edição, é bastante importante e confere poder mais realista ou não ao algoritmo. Seguramente, o último caso é o mais realista e também o mais difícil.

Nesta palestra devemos descrever um algoritmo, tuiuiu, que auxilia de forma significativa, garantindo que não haja perda de solução possível, na procura por regiões da(s) seqüência(s) fornecida(s) que fazem parte de uma repetição de comprimento ao menos L, com no máximo d erros (substituições, inserções, ou remoções), e que se repita ao menos r vezes na(s) seqüencia(s) forcecida(s). Um algoritmo exato para o problema é exponencial em r e tuiuiu reduz drasticamente o espaço de busca, acelerando o processamento das seqüências envolvidas, através do uso de algumas propriedades combinatórias das palavras até que bastante simples. Relatamos experimentação com tuiuiu, onde se podem verificar estas afirmativas e tratamos seqüências por vezes tão grandes quanto as de um cromossomo humano.