Otimização para o problema da cadeia de caracteres mais próxima

Abstract

Este trabalho aborda o Problema da Cadeia de Caracteres Mais Próxima (PCCP) - Closest String Problem (CSP). O objetivo do problema ´e encontrar uma cadeia de caracteres que minimiza a máxima distancia para um conjunto de cadeias com mesmo comprimento e alfabeto fixo. A métrica utilizada é a distancia de Hamming, que ´e definida como o número de posições nas quais duas sequencias diferem. O CSP tem muitas aplicações, principalmente na biologia computacional e na teoria dos códigos. O objetivo dessa dissertação é implementar dois modelos presentes na literatura que buscam solucionar o CSP por meio de programação linear inteira, e então verificar as vantagens de um modelo em relação ao outro. O primeiro modelo aparece em Meneses et al. (2004, sec. 2.4) e também em Festa (2007, p. 228). Já o segundo modelo ´e proposto por Zornig (2011, p. 5612). Para verificar qual modelo ´e melhor, foram feitas simulações com diversos comprimentos de sequencias, a fim de observar o número de restrições e variáveis nos modelos. O segundo modelo se saiu melhor nos testes, pois o número de restrições e variáveis não depende do comprimento das sequencias. Palavras-chave: Problema da Cadeia de Caracteres Mais Próxima, Distancia de Hamming, Relaxamento LP, Teoria dos códigos, Biologia Computacional.