26 fev 2025
14:00 Defesa de Doutorado Sala 85 do IC 2
Tema
E-NFA Pequeno para Alinhamento de Sequências Restrito por Expressão Regular
Aluno
Lise Rommel Romero Navarrete
Orientador / Docente
Guilherme Pimentel Telles
Breve resumo
O alinhamento de sequências é um problema fundamental na biologia molecular, usado para avaliar as semelhanças estruturais e funcionais entre sequências biológicas. Uma versão interessante deste problema é o alinhamento restrito por expressão regular (RECSA, do inglês regular expression constrained sequence alignment), onde um subalinhamento deve corresponder a uma expressão regular.
Expressões regulares podem ser usadas para representar padrões biológicos, incluindo aqueles definidos pelo PROSITE.
Para resolver o problema RECSA, autômatos são usados como reconhecedores de sequências.
Este trabalho aborda o problema RECSA focando na melhoria da construção de autômatos e na sua integração com o alinhamento de sequências restrito. Ele está organizado em três partes.
Na primeira parte propomos, analisamos e implementamos uma versão simplificada da construção de Thompson para resolver o problema RECSA, introduzindo listas de estados ativos para os padrões PROSITE como uma restrição. Apresentamos os resultados de experimentos comparativos entre nossa abordagem e outras da literatura.
Na segunda parte exploramos a construção de Thompson focando nas condições sob as quais um autômato de tamanho linear em relação ao tamanho da expressão regular pode ser construído. Introduzimos o conceito de expressão regular composta e a construção de um autômato a partir de uma expressão regular que isola subexpressões que levam a autômatos grandes, permitindo, em certos casos, a construção de um E-free NFA de tamanho linear. Esses casos incluem padrões PROSITE e outras expressões regulares que possuem símbolos epsilon e fechos de Kleene, que tipicamente resultam em autômatos grandes.
Na terceira parte exploramos o autômato de Glushkov baseado nos conjuntos first, last e follow, e introduzimos a follow matrix como um novo formalismo para representar expressões regulares. Mostramos propriedades das follow matrices, incluindo sua capacidade intrínseca de eliminar componentes redundantes e triviais da representação da expressão regular, proporcionando assim uma representação mais eficiente e compacta das linguagens regulares. Exploramos o uso da follow matrix para simplificar e reduzir o tamanho de um E-free NFA, apresentando ideias para um algoritmo de construção de E-free NFA baseado na follow matrix.
Banca examinadora
Titulares:
| Guilherme Pimentel Telles | IC/UNICAMP |
| Maria Emília Machado Telles Walter | IE/UnB |
| Said Sadique Adi | FACOM/UFMS |
| João Meidanis | IC/UNICAMP |
| Lehilton Lelis Chaves Pedrosa | IC/UNICAMP |
Suplentes:
| Zanoni Dias | IC/UNICAMP |
| Marcelo Keese Albertini | FACOM/UFU |
| Nalvo Franco de Almeida Junior | FACOM/UFMS |