• 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
 
 
Dissertação de Mestrado
DOI
10.11606/D.100.2019.tde-17122018-112356
Documento
Autor
Nome completo
Gilmar Pereira dos Santos
E-mail
Unidade da USP
Área do Conhecimento
Data de Defesa
Imprenta
São Paulo, 2018
Orientador
Banca examinadora
Machado-Lima, Ariane (Presidente)
Castro Junior, Amaury Antônio de
Lauretto, Marcelo de Souza
Rozante, Luiz Carlos da Silva
Título em português
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
Palavras-chave em português
Classificação
Gramáticas
Métodos Adaptativos
Métodos Sintáticos
Pseudonós
Reconhecimento de Padrões
RNA
Resumo em português
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
Título em inglês
Earley's syntactic analyzer for adaptive context-free grammars and its application in the characterization of RNA families with pseudoknot
Palavras-chave em inglês
Adaptive Methods
Classification
Grammars
Pattern Recognition
Pseudoknot
RNA
Syntactic Methods
Resumo em inglês
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
 
AVISO - A consulta a este documento fica condicionada na aceitação das seguintes condições de uso:
Este trabalho é somente para uso privado de atividades de pesquisa e ensino. Não é autorizada sua reprodução para quaisquer fins lucrativos. Esta reserva de direitos abrange a todos os dados do documento bem como seu conteúdo. Na utilização ou citação de partes do documento é obrigatório mencionar nome da pessoa autora do trabalho.
Data de Publicação
2019-01-24
 
AVISO: Saiba o que são os trabalhos decorrentes clicando aqui.
Todos os direitos da tese/dissertação são de seus autores
CeTI-SC/STI
Biblioteca Digital de Teses e Dissertações da USP. Copyright © 2001-2019. Todos os direitos reservados.