O Autômato dos Sufixos (1993)


[Home] [Biba] [Linux] [Conjugue] [br.ispell] [axw3] [uplink]

Estamos adicionando aqui trechos da dissertação na medida da necessidade e das nossas possibilidades. O texto completo em formato dvi está disponível para download.

Abstract

A proof of correctness and linear time complexity construction of the Suffix Automaton due to Blumer et alli is given. It is stressed that this algorithm also obtains the Suffix Tree for the reverse of the input word, a known but little explored fact. The representation problem of the Suffix Authomaton in linear space whithout loss of the linearity in construction time (independence on the alphabet size is required) is treated, and two negative results are presented.

We develop a space-economical implementation of the refinament algorithm due to Manber and Myers for Suffix Vector construction. It requires $2/3$ of the memory used by that presented by the authors. A note is given on the informatization of the Oxford English Dictionary, and an algorithm developed by Gonnet et alli along that large-scale text-processing project is described. Finally, a chapter with examples of the interface between Computer Science and Molecular Biology closes this dissertation.

Elaboramos uma prova da correção e linearidade no tempo do algoritmo de construção do Autômato dos Sufixos devido a Blumer et alli. Ressaltamos o fato de que esse algoritmo também obtém a Árvore dos Sufixos do reverso da entrada, fato conhecido mas pouco explorado. Demos ainda dois resultados negativos que obtivemos para o problema da representação do Autômato dos Sufixos em espaco linear preservando a linearidade no tempo de construção (exige-se independência no tamanho do alfabeto).

Desenvolvemos uma implementação espaço-econômica do algoritmo de refinamento de Manber e Myers para a construção do Vetor dos Sufixos. Ela consome 2/3 da memória usada por aquela apresentada pelos autores. Fizemos alguns comentários sobre a informatização do Dicionário de Oxford, e apresentamos um algoritmo de Gonnet et alli, desenvolvido durante aquele projeto de processamento de textos. Concluímos a dissertação com um capítulo contendo alguns exemplos da atual interação entre Ciência da Computação e Biologia Molecular.

Sumário e Introdução do Capítulo 3

Ferramentas Computacionais em Biologia Molecular

Recentes avanços em biologia molecular vêm revelando a estrutura primária de diversas proteínas, e a seqüencia de bases de trechos do DNA de inúmeros organismos. O volume de informações vêm crescendo com grande velocidade, e o uso de computadores nessa área é cada vez mais intenso. Com eles têm-se organizado grandes bancos de dados e desenvolvido diversas ferramentas para a análise dessas seqüencias biológicas. Os problemas que surgem então não são triviais, e têm pelo menos dois agravantes, que são as enormes dimensões dos bancos de dados biológicos e a ocorrência de erros de sequenciamento.

Esses problemas tem chamado a atenção dos cientistas de computação. Algo que pode ajudar-nos a medir o nível de interação atual entre a biologia molecular e a ciência da computação e o número de entradas de algumas bibliografias recentemente organizadas sobre o tema; nas maiores de que temos notícia esse numero gira em torno de mil.

O esforço de pesquisa tem trazido beneficios para os dois lados. Naturalmente, boa parte dos resultados obtidos tem um interesse ou uma aplicação muito particulares. Os métodos para a detecção de homologias, por exemplo -- e é necessário que o façam --, são calibrados em função de determinadas características estruturais das seqüencias biológicas. Essas características funcionam como hipóteses simplificadoras que, por um lado, permitem ganhos de eficiência, mas por outro tornam o método inaplicável noutros contextos.

Pode-se entretanto citar alguns trabalhos que extrapolam essa especificidade, constituindo-se por isso em legítimas contribuições para a ciência da computação. O vetor dos sufixos, por exemplo, e, como já dissemos, em parte fruto dessa interação. Outros exemplos são um algoritmo de aproximação para o problema da reconstrução e diversas estatísticas envolvendo seqüencias.

De maneira geral, entretanto, convém nao perder de vista que a interdisciplinaridade aqui é inevitável. Longe de ser um transtorno, essa exigência e com certeza bastante salutar. E essa a tônica que tentamos dar a este capítulo. Expusemos várias ferramentas computacionais usadas em biologia molecular procurando situar cada uma delas dentro do contexto particular em que foi desenvolvida. Nossa fonte principal para os conceitos básicos de bioquímica foi o livro de Lubert Stryer. Sempre que possivel relacionamos essas ferramentas com as estruturas baseadas em sufixos já apresentadas. Nossa abordagem não é exaustiva; entre os tópicos que não cobrimos pode-se citar o problema da reconstrução, a previsão da estrutura espacial de proteínas, o cálculo de alinhamentos e a detecção de consensos.

Bibliografia

[BLAST] S. F. Altschul and W. Gish and W. Miller and E. W. Myers and D. J. Lipman, A basic local alignement search tool, Journal of Molecular Biology, 1990.

[All-against-All] R. A. Baeza-Yates and G. H. Gonnet, All-Against-All sequence matching (preliminary version), 1990.

[HashTrie] J. Bentley and D. E. Knuth and D. McIlroy, Programming Pearls: A Literate Program, Communications of the ACM, 1986, vol 29, pp 471-483.

[LASS] A. Blum and T. Jiang and M. Li and J. Tromp and M. Yannakakis, Linear Approximation of Shortest Superstrings, STOC 91, 1991.

[Blumer] A. Blumer and J. Blumer and A. Ehrenfeucht and D. Haussler and M. T. Chen and J. Seiferas, The smallest automaton recognizing the subwords of a text, Theoretical Computer Science, 1985, vol. 40, pp. 31-55.

[AverageDAWG] A. Blumer and A. Ehrenfeucht and D. Haussler, Average sizes of suffix trees and DAWGs, Discrete Applied Mathematics, 1989, vol. 24, pp. 37-45.

[AplicAutSuf] B. Clift and D. Haussler and R. McConnell and T. D. Schneider and G. D. Stormo, Sequence landscapes, Nucleic Acids Research, 1986, vol. 14, pp. 141-158

[Crochemore] M. Crochemore, Transducers and repetitions, Theoretical Computer Science, 1986, vol. 45, pp. 63-86.

[Sete] M. Crochemore and T. Lecroq and A. Czumaj and L. Gasieniec and S. Jarominek and W. Plandowski and W. Rytter, Speeding up two string-matching algorithms, Lecture Notes in Computer Science, 1992.

[DivConqAppSM] P. Cull and J. L. Holloway, Divide and conquer approximate string matching: when dynamic programming is not powerful enough, Oregon State University, Computer Science Department, rel. téc. 92-20-06, 1992

[MetricaLinear] A. Ehrenfeucht and D. Haussler, A new distance metric on strings computable in linear time, Discrete Appl. Math., 20, vol. 1988, pp. 191-203.

[ExamPAT] G. H. Gonnet, Examples of PAT applied to the Oxford English Dictionary, UW Centre for the New Oxford English Dictionary, University of Waterloo, rel. téc. OED-87-02, 1987.

[VetSufOED] G. H. Gonnet and R. A. Baeza-Yates and T. Snider, Lexicographical indices for text: inverted files vs. PAT trees, UW Centre for the New Oxford English Dictionary, University of Waterloo, rel. téc. OED-91-01, 1991.

[BibHolloway] J. L. Holloway, An annotated bibliography of algorithms applicable to molecular biology, Oregon State University, Computer Science Department, rel. téc. 92-50-01, 1992.

[LinearMerge] B. C. Huang and M. A. Langston, Practical In-Place Merging, Communications of the ACM, 1988, vol. 31, pp. 348-352.

[KarlinSurvey] S. Karlin and F. Ost and B. E. Blaisdell, Patterns in DNA and amino acid sequences and their statistical significance, Mathematical Methods for DNA Sequences, 1988, M. S. Waterman (ed.), pp. 133-156, CRC Press.

[FatRep] S. Karlin and G. Ghandour and F. Ost and L. J. Korn, New Approaches for computer analysis of nucleic acid sequences, Proc. Natl. Acad. Sci. USA, 1983, vol. 80, pp. 5660-5664.

[FASTP] D. J. Lipman and W. R. Pearson, Rapid and sensitive protein similarity searches, Science, 1985, vol. 227, pp. 1435-1441.

[Manber&Myers] U. Manber and E. W. Myers, Suffix Arrays: A new method for on-line string searches, University of Arizona, TR 89-14, 1989.

[Martinez] H. M. Martinez, An efficient method for finding repeats in molecular sequences, Nucleic Acids Research, 1983, vol. 11, pp. 4629-4634.

[AutSufMatchErr] P. Jokinen and E. Ukkonen, Two algorithms for approximate string matching, Lecture Notes in Computer Science, 1991, vol. 520, pp. 240-248,.

[TeseMeidanis] J. Meidanis, Algorithms for problems in computational genetics (PhD thesis), University of Wisconsin-Madison, 1992.

[ICATOOLS] R. Parsons and S. Brenner and M. J. Bishop, Clustering cDNA Sequences, Comp. Appl. Biosc., 8, vol. 1992, pp. 461-466.

[FASTA] W. R. Pearson and D. J. Lipman, Improved tools for biological sequence comparison, Proc. Natl. Acad. Sci. USA, 1988, vol. 85, pp. 2444-2448.

[SanKrusk] D. Sankoff and J. B. Kruskal, Time Warps, String edits, and Macromolecules: the theory and practice of sequence comparison, Addison-Wesley, 1983.

[tetrahedra] B. D. Silverman and R. Linsker, A measure of DNA periodicity, Journal of Theoretical Biology, 1986, vol. 118, pp. 295-300.

[Stryer] L. Stryer, Biochemistry, third edition, W. H. Freeman and Company (publisher), 1988.

[Walsh] S. Tavaré and B. W. Giddings, Some statistical aspects of the primary structure of nucleotide sequences, Mathematical Methods for DNA Sequences, M. S. Waterman (ed.), 1988, CRC Press, pp. 117-132.

[Complex] E. N. Trifonov, Making Sense of the Human Genome, Structure & Methods, 1990, vol. 1, pp. 69-77.

[WatConsensus] M. S. Waterman, Consensus Patterns in sequences, Mathematical Methods for DNA Sequences, M. S. Waterman (ed.), 1988, CRC Press, pp. 93-115.