Filtros para a busca e extração de padrões aproximados em cadeias biológicas / Filter Algorithms for Approximate Patterns Matching and Extraction from Biological Strings
AUTOR(ES)
Domingos Soares Neto
DATA DE PUBLICAÇÃO
2008
RESUMO
Esta dissertação de mestrado aborda formulações computacionais e algoritmos para a busca e extração de padrões em cadeias biológicas. Em particular, o presente texto concentra-se nos dois problemas a seguir, considerando-os sob as distâncias de Hamming e Levenshtein: a) como determinar os locais nos quais um dado padrão ocorre de modo aproximado em uma cadeia fornecida; b) como extrair padrões que ocorram de modo aproximado em um número significativo de cadeias de um conjunto fornecido. O primeiro problema, para o qual já existem diversos algoritmos polinomiais, tem recebido muita atenção desde a década de 60, e ganhou novos ares com o advento da biologia computacional, nos idos dos anos 80, e com a popularização da Internet e seus mecanismos de busca: ambos os fenômenos trouxeram novos obstáculos a serem superados, em razão do grande volume de dados e das bastante justas restrições de tempo inerentes a essas aplicações. O segundo problema, de surgimento um pouco mais recente, é intrinsicamente desafiador, em razão de sua complexidade computacional, do tamanho das entradas tratadas nas aplicações mais comuns e de sua dificuldade de aproximação. Também é de chamar a atenção o seu grande potencial de aplicação. Neste trabalho são apresentadas formulações adequadas dos problemas abordados, assim como algoritmos e estruturas de dados essenciais ao seu estudo. Em especial, estudamos a extremamente versátil árvore dos sufixos, assim como uma de suas generalizações e sua estrutura irmã: o vetor dos sufixos. Grande parte do texto é dedicada aos filtros baseados em q-gramas para a busca aproximada de padrões e algumas de suas mais recentes variações. Estão cobertos os algoritmos bit-paralelos de Myers e Baeza-Yates-Gonnet para a busca de padrões; os algoritmos de Sagot para a extração de padrões; os algoritmos de filtragem de Ukkonen, Jokinen-Ukkonen, Burkhardt-Kärkkäinen, entre outros.
ASSUNTO(S)
algoritmos de filtragem motifs árvores dos sufixos patterns extraction suffix array filter algorithms motifs algoritmos bit-paralelos vetor dos sufixos bit-parallel algorithms extração de padrões q-grams approximate string matching busca aproximada de padrões q-gramas suffix tree
Documentos Relacionados
- Aplicação de autômatos finitos nebulosos no reconhecimento aproximado de cadeias.
- Algoritmos enumerativos para geração de padrões tabuleiros
- Algoritmos enumerativos para geração de padrões tabuleiros
- MÉTODOS APROXIMADOS DE SOLUÇÃO DE SISTEMAS DINÂMICOS NÃO-LINEARES
- Multialinhamento de seqüências biológicas utilizando algoritmos genéticos