Made available in DSpace on 2014-06-12T15:59:03Z (GMT). No. of bitstreams: 2
arquivo4823_1.pdf: 1258995 bytes, checksum: c83e73b81e30c352afae5e1805a2c9c2 (MD5)
license.txt: 1748 bytes, checksum: 8a4605be74aa9ea9d79846c1fba20a33 (MD5)
Previous issue date: 2003 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / 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
| Identifer | oai:union.ndltd.org:IBICT/oai:repositorio.ufpe.br:123456789/2533 |
| Date | January 2003 |
| Creators | Gustavo Soares da Fonseca, Paulo |
| Contributors | Silva Guimarães, Katia |
| Publisher | Universidade Federal de Pernambuco |
| Source Sets | IBICT Brazilian ETDs |
| Language | Portuguese |
| Detected Language | Portuguese |
| Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/masterThesis |
| Source | reponame:Repositório Institucional da UFPE, instname:Universidade Federal de Pernambuco, instacron:UFPE |
| Rights | info:eu-repo/semantics/openAccess |
Page generated in 0.0016 seconds