O problema do alinhamento de segmentos - Lima, Leandro Ishi Soares de (2013)
Dentre a variedade de problemas de otimização existentes, aqueles que envolvem sequências destacam-se por sua aplicabilidade em vários campos de pesquisa. Nesta dissertação apresentamos um estudo detalhado de um novo problema de otimização combinatória envolvendo sequências, denominado Problema do Alinhamento de Segmentos (PASG). Esse estudo envolve a de nição formal desse problema e a descrição de um algoritmo e ciente, baseado na técnica de programação dinâ- mica, que o resolve. Ademais, formalizamos uma versão múltipla do PASG, denominada Problema do Alinhamento de Segmentos Múltiplo (PASGM). Para essa versão do problema, nós provamos que ela é NP-Completa e que é muito improvável existir um algoritmo de aproximação com uma boa razão para ela. Com base nesse resultado, propomos três heurísticas para tratar o PASGM e as avaliamos experimentalmente através de testes arti ciais. Por m, as implementações das soluções propostas neste trabalho foram aplicadas na tarefa de identi cação de genes. A aplicabilidade dos nossos programas nessa tarefa foi atestada através dos bons resultados obtidos por eles em um conjunto de instâncias de testes reais.