Ordenação de sufixos e medidas de similaridade entre cadeias

Resumo

A ordenação de sufixos é um problema fundamental em processamento de cadeias de caracteres presente em muitas aplicações de Bioinformática, Recuperação de informação e Mineração de textos. Esse problema está relacionado com a construção do vetor de sufixos e com a transformada de Burrows-Wheeler, os quais desempenham um papel importante em métodos de indexação de cadeias (e.g. FM-índice) e compressão de dados (e.g. bzip). Na literatura, muitos trabalhos têm sido propostos para construir o vetor de sufixos de uma única cadeia e obter a transformada de Burrows-Wheeler. Entretanto, em muitas situações estamos interessados em processar conjuntos de cadeias e obter diretamente a transformada de Burrows-Wheeler, isto é, sem construir o vetor de sufixos. Poucas soluções têm sido propostas para esses problemas. Dessa forma, o principal objetivo desse projeto é investigar o cálculo direto da transformada de Burrows-Wheeler para conjuntos de cadeias. Além disso, pretende-se investigar medidas de similaridades que utilizam a transformada de Burrows-Wheeler para comparar e classificar cadeias de caracteres.