O problema do alinhamento de segmentos

• Ano de defesa: 2013
• Autor(a) principal: Lima, Leandro Ishi Soares de
• Orientador(a): Adi, Said Sadique
• Tipo de documento: Dissertação
• Tipo de acesso: Acesso aberto
• Idioma: por
• Palavras-chave em Português: Otimização Combinatória; Combinatorial Optimization; Algorítmos Genéticos; Genetic Algorithms; Programação Dinâmica; Dynamic Programming
• Link de acesso: https://repositorio.ufms.br/handle/123456789/1893

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.