• JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
 
  Bookmark and Share
 
 
Mémoire de Maîtrise
DOI
https://doi.org/10.11606/D.100.2019.tde-17122018-112356
Document
Auteur
Nom complet
Gilmar Pereira dos Santos
Adresse Mail
Unité de l'USP
Domain de Connaissance
Date de Soutenance
Editeur
São Paulo, 2018
Directeur
Jury
Machado-Lima, Ariane (Président)
Castro Junior, Amaury Antônio de
Lauretto, Marcelo de Souza
Rozante, Luiz Carlos da Silva
Titre en portugais
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
Mots-clés en portugais
Classificação
Gramáticas
Métodos Adaptativos
Métodos Sintáticos
Pseudonós
Reconhecimento de Padrões
RNA
Resumé en portugais
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
Titre en anglais
Earley's syntactic analyzer for adaptive context-free grammars and its application in the characterization of RNA families with pseudoknot
Mots-clés en anglais
Adaptive Methods
Classification
Grammars
Pattern Recognition
Pseudoknot
RNA
Syntactic Methods
Resumé en anglais
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
 
AVERTISSEMENT - Regarde ce document est soumise à votre acceptation des conditions d'utilisation suivantes:
Ce document est uniquement à des fins privées pour la recherche et l'enseignement. Reproduction à des fins commerciales est interdite. Cette droits couvrent l'ensemble des données sur ce document ainsi que son contenu. Toute utilisation ou de copie de ce document, en totalité ou en partie, doit inclure le nom de l'auteur.
Date de Publication
2019-01-24
 
AVERTISSEMENT: Apprenez ce que sont des œvres dérivées cliquant ici.
Tous droits de la thèse/dissertation appartiennent aux auteurs
CeTI-SC/STI
Bibliothèque Numérique de Thèses et Mémoires de l'USP. Copyright © 2001-2024. Tous droits réservés.