Índices completos para casamento de padrões e inferência de motifs

• Ano de defesa: 2003
• Autor(a) principal: Gustavo Soares da Fonseca, Paulo
• Orientador(a): Silva Guimarães, Katia
• Tipo de documento: Dissertação
• Tipo de acesso: Acesso aberto
• Idioma: por
• Instituição de defesa: Universidade Federal de Pernambuco
• Palavras-chave em Português: Casamento de padrões; Estruturas de Índice, Árvores de sufixos, Árvores de afixos
• Link de acesso: https://repositorio.ufpe.br/handle/123456789/2533

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 unidimensionais 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 grande área de 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´aveis 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 ótima do problema é linearmente proporcional ao comprimento do padrão (em geral, muito menor do que o texto). Em Biologia Molecular Computacional, frequentemente estamos interessados em localizar as ocorrências de uma determinada subsequê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 inferi-los. Isto é, dado um conjunto de sequências moleculares, queremos descobrir que subsequências aparecem repetidas emuma quantidade significativa dessas sequê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. Nossa apresentação não intenciona ser estritamente panorâmica e, portanto, algum sacrif´ıcio da fluência deve ser depositado no altar do rigor matemático. 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