O problema da cadeia de caracteres mais próxima (do inglés Closest String Problem CSP) que surge na bioinformática e na criptografia é encontrar uma cadeia de caracteres que minimize a maior distância de Hamming de um determinado conjunto de cadeias de caracteres, o CSP é um problema NP-difícil. O principal objetivo deste trabalho é propor métodos exatos para este problema, para esse fim, caracterizamos casos especiais para esse problema com ênfase no número de strings. Até agora, nossa contribuição é: algoritmos de tempo linear para o CSP com até três strings e para quatro strings binárias, além de um algoritmo guloso heurístico e um algoritmo exato recursivo para o caso geral. Além disso, para cada algoritmo proposto serão apresentadas provas formais de corretude, também experimentos numéricos mostrarão a eficácia dos algoritmos propostos.
|
