Combinatorial Approaches for the Closest String Problem

• Ano de defesa: 2019
• Autor(a) principal: Vilca, Omar Latorre
• Outros Autores: http://lattes.cnpq.br/3293662600883484
• Tipo de documento: Tese
• Tipo de acesso: Acesso aberto
• Idioma: por
• Instituição de defesa: Universidade Federal do Amazonas; Instituto de Computação; Brasil; UFAM; Programa de Pós-graduação em Informática
• Palavras-chave em Português: Bioinformática; Criptografia de dados (Computação); CIÊNCIAS EXATAS E DA TERRA: CIÊNCIA DA COMPUTAÇÃO: TEORIA DA COMPUTAÇÃO: ANÁLISE DE ALGORITMOS E COMPLEXIDADE DE COMPUTAÇÃO; Combinatorial Optimization; Integer Programming; Heuristics
• Link de acesso: https://tede.ufam.edu.br/handle/tede/7449

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.