AN EFFICIENT ALGORITHM FOR THE CLOSEST STRING PROBLEM

Neste artigo abordamos o Problema da Cadeia de Caracteres mais Próxima (PCCP) que surge na pesquisa web, teoria da codificação e biologia molecular computacional. Para solucioná-lo deve-se encontrar uma string que minimize a máxima distância de Hamming de um determinado conjunto de strings. PCCP é um problema NP-difícil. Neste trabalho, propomos um algoritmo de tempo linear denominado Algoritmo da Primeira Minimização (APM) que resolve instâncias do PCCP com três strings (3-PCCP). Sua ideia principal é identificar tipos coluna-posição na instância de entrada, o que nos permite decompor em cinco tuplas diferentes, correspondendo à posição de cada string no conjunto de strings para, finalmente, determinar todas as colunas-posições não fixadas por simples avaliação através dos diferentes casos. Uma prova formal de corretude e complexidade computacional do algoritmo proposto serão fornecidas. O algoritmo proposto é comparado com uma formulação de programação inteira para o 3-PCCP. Além disso, experimentos computacionais em tabelas de comparação mostrarão a eficácia do algoritmo proposto.