================================================
Seminário de Topicos de Otimização Combinatória
================================================
Título: Algoritmos para alinhamento de seqüências
Palestrante: Said Sadique Adi
Local: Sala 241, Bloco A
Data: quarta-feira, 20 de outubro, às 16:00
Alinhar duas seqüencias $s$ e $t$ consiste em inserir
espaços em locais arbitrários dessas seqüências de modo que
elas fiquem do mesmo tamanho. Dessa forma, $s$ e $t$ podem
ser dispostas uma em cima da outra, criando-se uma
correspondência entre seus caracteres e os espaços nelas
inseridos. Dado um alinhamento entre duas seqüências, uma
pontuação pode ser associada a ele de acordo com o conteúdo
de suas colunas. O problema consiste então em encontrar o
alinhamento de pontuação máxima.
Existe na literatura uma série de algoritmos para
alinhamento de seqüências. Dentre eles podemos citar o
algoritmo de Needleman-Wunsch e o algoritmo de
Smith-Waterman, que determinam, respectivament o melhor
alinhamento global e local entre duas seqüências.
Ultimamente, Huang e Chao desenvolveram um
algoritmo um pouco diferente dos anteriores, cujo objetivo é
alinhar da melhor forma possível duas seqüências contendo
regiões similares separadas por outras não tão
parecidas. Nesse seminário, apresentaremos esse algoritmo e
uma de suas aplicações.
-------------------------------------------------------------
Atividade dentro do projeto PRONEX Complexidade de Estruturas
Discretas (Projeto ProNEx 107/97; Proc. CNPq 664107/1997-4) e
do Projeto Temático ProNEx Foundations of Computer Science:
Combinatorial Algorithms and Discrete Structures (FAPESP/CNPq
Proc. No. 2003/09925-5)
-------------------------------------------------------------