Ãndices Completos para Casamento de PadrÃes e InferÃncia de Motifs

AUTOR(ES)
DATA DE PUBLICAÇÃO

2003

RESUMO

Uma das maneiras mais eficientes (notadamente do ponto de vista computacional) empregada pela humanidade para a representaÃÃo da informaÃÃo tem sido atravÃs da forma de texto, ou seja, atravÃs de cadeias unimensionais de sÃmbolos (ou caracteres) tomados sobre conjuntos discretos finitos (ou alfabetos). As fecundas teorias, tÃcnicas e algoritmos destinados ao processamento de texto tÃm ocupado um papel central em diversos Ãmbitos da CiÃncia da ComputaÃÃo, constituindo-se, sobretudo ao longo das Ãltimas trÃs dÃcadas, em um campo de particular interesse no seio da Ãrea-mÃe que compreende o estudo dos Algoritmos e Estruturas de Dados. Grande parte do recente interesse com respeito ao processamento de texto deve-se ao emergente ramo da ciÃncia denominado Biologia Molecular Computacional, que, a grosso modo, comporta o estudo, atravÃs de tÃcnicas matemÃticas e computacionais, da estrutura e da funÃÃo dos artefatos bio-moleculares responsÃveis pela conformaÃÃo e pelas atividades fisiolÃgicas dos organismos vivos. A confluÃncia dos problemas de Biologia Molecular e de processamento de textos dÃ-se na medida em que as estruturas macromoleculares fundamentais (DNA, RNA e proteÃnas) podem ser representadas atravÃs de cadeias (muito longas) de caracteres tomados sobre alfabetos (curtos) especÃficos. O problema fundamental relacionado ao processamento de cadeias corresponde à determinaÃÃo das ocorrÃncias, exatas ou aproximadas, de um determinado padrÃo em um dado texto - problema do casamento de padrÃes - problema esse que admite inÃmeras variaÃÃes. Os problemas de casamento de padrÃes podem ser particionados em duas grandes categorias com respeito ao conhecimento prÃvio ou nÃo do texto a ser examinado. Os algoritmos clÃssicos destinados à resoluÃÃo do problema do casamento de padrÃes dizem respeito ao caso no qual o texto nÃo à conhecido previamente. Nesse caso, cada um dos seus caracteres deve ser examinado pelo menos uma vez, o que resulta em soluÃÃes de custo, no mÃnimo, linearmente proporcional ao tamanho do texto. Se, todavia, o texto a ser examinado à conhecido a priori, entÃo ele pode ser prÃ-processado (tipicamente em tempo linear), dando origem a uma estrutura auxiliar (tipicamente de tamanho linear) denominada Ãndice, contra a qual os padrÃes podem entÃo ser confrontados para que as suas ocorrÃncias sejam determinadas. Nesse caso, o custo da soluÃÃo Ãtimado problema à linearmente proporcional ao comprimento do padrÃo (em geral, muito menor do que o texto). Em Biologia Molecular Computacional, freqÃentemente estamos interessados em localizar as ocorrÃncias de uma determinada subseqÃÃncia molecular (ou motif) dentro de estruturas maiores. Esses motifs representam, em geral, regiÃes altamente conservadas, i.e., pouco afetadas por mutaÃÃes, que desempenham funÃÃes biolÃgicas especÃficas. Esse problema de localizaÃÃo de motifs limita-se com o problema do casamento de padrÃes e pode ser abordado atravÃs das mesmas tÃcnicas. Em outras situaÃÃes, todavia, estamos interessados nÃo em localizar motifs mas sim em inferÃ-los. Isto Ã, dado um conjunto de seqÃÃncias moleculares, queremos descobrir que subseqÃÃncias aparecem repetidas em uma quantidade significativa dessas seqÃÃncias de maneira suficientemente conservada e que, portanto, possuem uma boa probabilidade de representar um objeto biolÃgico de particular interesse. Neste trabalho, nos propomos a reunir em uma obra Ãnica, boa parte da informaÃÃo fundamental dispersa na literatura acerca dos principais Ãndices completos conhecidos, com Ãnfase nas suas propriedades estruturais. Como apresentaÃÃo nÃo intenciona ser estritamente panorÃmica um certo rigor matemÃtico faz-se necessÃrio. AlÃm disso, apresentamos uma anÃlise crÃtica da adequaÃÃo e desempenho das estruturas de Ãndice estudadas para a resoluÃÃo do problema da inferÃncia de motifs atravÃs de algoritmos exatos e combinatÃrios

ASSUNTO(S)

ciencia da computacao dawgs motif inference estruturas de Ãndice index structures suffix trees affix trees suffix arrays casamento de padrÃes motif localization suffix automata Ãrvores de sufix string matching

ACESSO AO ARTIGO

Documentos Relacionados