Comparação de cadeias restrita por expressões regulares e gramáticas livres de contexto

Processo:	13/19989-2
Linha de fomento:	Bolsas no Exterior - Pesquisa
Vigência (Início):	15 de dezembro de 2013
Vigência (Término):	14 de dezembro de 2014
Área do conhecimento:	Ciências Exatas e da Terra - Ciência da Computação - Teoria da Computação

Pesquisador responsável:	Guilherme Pimentel Telles
Beneficiário:	Guilherme Pimentel Telles
Anfitrião:	Peter F. Stadler

Instituição-sede:	Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brasil
Local de pesquisa :	Leipzig University, Alemanha

Assunto(s):	Biologia computacional Expressões regulares
Resumo Neste projeto propomos estudar os problemas de alinhamento de cadeias restritos por expressões regulares e gramáticas livres de contexto. Esses problemas estão relacionados com o casamento exato de cadeias, com o problema do casamento inexato de cadeias e com o problema do alinhamento de cadeias. Acreditamos que seja possível obter algoritmos mais eficientes em memória e em tempo para esses problemas. Consideramos ainda a possibilidade de obter heurísticas mais rápidas para eles. Esses problemas estão relacionados com a comparação de sequências moleculares concomitantemente à identificação de motifs que possam ser descritos por expressões regulares e gramáticas livres de contexto. (AU)