???item.export.label??? ???item.export.type.endnote??? ???item.export.type.bibtex???

Please use this identifier to cite or link to this item: https://tede.ufam.edu.br/handle/tede/7449
Tipo do documento: Tese
Título: Combinatorial Approaches for the Closest String Problem
Autor: Vilca, Omar Latorre 
Primeiro orientador: Feitosa, Eduardo Luzeiro
Primeiro membro da banca: Collona, Juan Gabriel
Segundo membro da banca: Nakamura, Fabíola Guerra
Terceiro membro da banca: Onety, Renata da Encarnação
Quarto membro da banca: Craveiro, Joaquim Maciel da Costa
Resumo: 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.
Abstract: The closest string problem (CSP) that arises in computational molecular biology and coding theory is to find a string that minimizes the maximum Hamming distance from a given set of strings, the CSP is an NP-hard problem. The main aim of this work is to propose exact methods for this problem, for this purpose, we characterize special cases for this problem with emphasis in the number of strings. Until now our contribution is: linear-time algorithms for CSP with up to three strings and for four binary strings, in addition to an heuristic greedy algorithm and a recursive exact algorithm for CSP for the general case. Furthermore, for each proposed algorithm formal proofs will be presented, also numerical experiments will show the effectiveness of the proposed algorithms.
Palavras-chave: Bioinformática
Criptografia de dados (Computação)
Área(s) do CNPq: CIÊNCIAS EXATAS E DA TERRA: CIÊNCIA DA COMPUTAÇÃO: TEORIA DA COMPUTAÇÃO: ANÁLISE DE ALGORITMOS E COMPLEXIDADE DE COMPUTAÇÃO
???metadata.dc.subject.user???: Combinatorial Optimization
Integer Programming
Heuristics
Idioma: por
País: Brasil
Instituição: Universidade Federal do Amazonas
Sigla da instituição: UFAM
Departamento: Instituto de Computação
Programa: Programa de Pós-graduação em Informática
Citação: VILCA, Omar Latorre. Combinatorial Approaches for the Closest String Problem. 2019. 106 f. Tese (Doutorado em Informática) - Universidade Federal do Amazonas, Manaus, 2019.
Tipo de acesso: Acesso Aberto
URI: https://tede.ufam.edu.br/handle/tede/7449
Data de defesa: 23-Aug-2019
Appears in Collections:Doutorado em Informática

Files in This Item:
File Description SizeFormat 
Tese_OmarVilca_PPGI2,37 MBAdobe PDFThumbnail

Download/Open Preview


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.