Título: Algoritmos quadráticos em tempo subquadrático
Palestrante: Alair Pereira do Lago
Local: Sala 267-A
Data: sexta, 26 de agosto, às 14:00
Resumo:
Um dos problemas mais fundamentais na comparação de seqüências (o que inclui alinhamento de seqüências biológicas ou busca com erros de palavras em textos) é que os algoritmos de programação dinâmica usuais rodam em tempo quadrático, o que pode ser caro demais em alguns casos. Várias heurísticas foram criadas por conta disto, sendo o BLAST uma das mais famosas.
Outro enfoque também bastante eficiente e usado é o da filtragem: a identificação de regiões da matriz de programação dinâmica que sabemos são "mortas" e que portanto são excluidas dos cálculos. Em comparação com as heurísticas, a filtragem tem a vantagem de não eliminar soluções ótimas.
Nesta palestra daremos uma introducão sobre o conceito de q-grams, definido por Ukkonen em 1992, com algumas aplicações passadas e recentes para o problema da filtragem. Dentre estas aplicações incluimos a busca com erros de palavras em textos e a procura de trechos (de comprimento acima de um certo limiar) das seqüências com distância de edição menor que um certo valor.
Todos são bem-vindos!!
Para mais informações sobre o seminário de TCC, visite a página:
http://pronex-focos.incubadora.fapesp.br/portal/seminarios/