Analisador sintático de Earley para gramáticas livres de contexto adaptativas e sua aplicação na caracterização de famílias de RNAs com pseudonós

Autor: Santos, Gilmar Pereira dos
Jazyk: portugalština
Rok vydání: 2018
Předmět:
Druh dokumentu: Dissertação de Mestrado
Popis: A teoria das linguagens formais é amplamente utilizada nos processos de solução de problemas de naturezas diversas, uma vez que tem poder de lidar tanto com as linguagens artifiais quanto com as linguagens naturais. As gramáticas, formalismos capazes de sintetizar as linguagens, podem também ser utilizadas no âmbito do problema de reconhecimento de padrões por poderem modelar as hierarquias dos componentes da linguagem, decompondo padrões em subestruturas. Seguindo essa linha, o arcabouço GrammarLab, cujo objetivo é facilitar a implementação, geração e testes de diferentes classificadores de sequências baseados em gramáticas, permitia em sua implementação anterior o uso de gramáticas regulares e livres de contexto. No entanto, alguns problemas necessitam de formalismos presentes apenas em gramáticas de níveis superiores na hierarquia de Chomsky. O problema encontrado ao se subir a hierarquia de gramáticas é a complexidade de tempo necessária para a análise sintática. Enquanto o reconhecimento de sequências por gramáticas regulares e livres de contexto pode ser feito em tempo polinomial, o problema geral de reconhecimento por gramáticas sensíveis ao contexto é um problema NP-completo e o de gramáticas irrestritas é considerado indecidível no caso geral. No entanto, o uso de métodos adaptativos possibilita que uma gramática altere seu conjunto de regras de produção durante a geração de sentenças, adicionando sensibilidade ao contexto a gramáticas originalmente livres de contexto, sem prejudicar a complexidade de análise polinomial. Desta forma, este trabalho teve como foco a inserção de métodos adaptativos no arcabouço GrammarLab e a criação de uma versão adaptativa do algoritmo de Earley de análise sintática. Como forma de verificar sua aplicação em problemas reais, foi realizado um estudo preliminar do uso do arcabouço na caracterização de famílias funcionais de RNAs com estrutura conservada, incluindo pseudonós. Os pseudonós apresentam relações de dependências cruzadas entre os nucleotídeos de uma sequência de RNA, relação esta que exemplifica dependência de contexto, sendo portanto um bom caso para o uso do modelo com adaptatividade em sua constituição. Os resultados obtidos com duas famílias de RNAs com pseudonós mostraram que a abordagem é altamente promissora
The theory of formal languages is widely used to solve problems of different natures as it can deal with artificial and natural languages. The grammars, formalisms able to synthesize languages, can also be used in pattern recognition problems due to the ability to model the language components hierarchies, decomposing patterns in substructures. Based on this idea, the framework GrammarLab was designed to facilitate the work involved in implementing, generating and testing different grammar based sequence classifiers, providing regular and context free grammar in the prior version. However, some problems need a formalism that can be found only in higher classes of grammars in the Chomsky hierarchy. The problem of using a higher class of grammar is the high computational time complexity for parsing. While the problem of recognizing sequences using regular and context free grammars is solved at polynomial time, the same problem in general case is NP-Complete for context sensitive grammars and undecidable for unrestricted grammars. Nevertheless, the use of adaptive methods allows a grammar to alter the set of production rules during sentences generation, including context sensitivity even to grammars that were designed to be context free, without increasing the polynomial parsing complexity. This work was focused in improving the GrammarLab framework by including the ability to deal with adaptive methods and in the creation of an adaptive version of Earleys algorithm. To test the solution in real world problems, it was conducted a preliminary study of the use of the framework in characterizing RNA functional families with conserved secondary structure, including pseudoknots. The pseudoknot pattern, represented by crossing dependences among RNA sequence nucleotides, is an example of context dependence, so it is a good test case for the use of a model that consider adaptability in the constitution. The obtained results with two families of RNAs with pseudoknots show that the approach is promising
Databáze: Networked Digital Library of Theses & Dissertations
Externí odkaz: