1. TEDE
  2. Unidade Manaus
  3. Programa de Pós-graduação em Informática
  4. Doutorado em Informática
???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
Full metadata record
DC FieldValueLanguage
dc.creatorVilca, Omar Latorre-
dc.creator.Latteshttp://lattes.cnpq.br/3293662600883484por
dc.contributor.advisor1Feitosa, Eduardo Luzeiro-
dc.contributor.advisor1Latteshttp://lattes.cnpq.br/5939944067207881por
dc.contributor.referee1Collona, Juan Gabriel-
dc.contributor.referee2Nakamura, Fabíola Guerra-
dc.contributor.referee3Onety, Renata da Encarnação-
dc.contributor.referee4Craveiro, Joaquim Maciel da Costa-
dc.date.issued2019-08-23-
dc.identifier.citationVILCA, Omar Latorre. Combinatorial Approaches for the Closest String Problem. 2019. 106 f. Tese (Doutorado em Informática) - Universidade Federal do Amazonas, Manaus, 2019.por
dc.identifier.urihttps://tede.ufam.edu.br/handle/tede/7449-
dc.description.resumoO 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.por
dc.description.abstractThe 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.eng
dc.description.sponsorshipCAPES - Coordenação de Aperfeiçoamento de Pessoal de Nível Superiorpor
dc.formatapplication/pdf*
dc.thumbnail.urlhttps://tede.ufam.edu.br//retrieve/34644/Tese_OmarVilca_PPGI.jpg*
dc.languageporpor
dc.publisherUniversidade Federal do Amazonaspor
dc.publisher.departmentInstituto de Computaçãopor
dc.publisher.countryBrasilpor
dc.publisher.initialsUFAMpor
dc.publisher.programPrograma de Pós-graduação em Informáticapor
dc.rightsAcesso Abertopor
dc.subjectBioinformáticapor
dc.subjectCriptografia de dados (Computação)por
dc.subject.cnpqCIÊNCIAS EXATAS E DA TERRA: CIÊNCIA DA COMPUTAÇÃO: TEORIA DA COMPUTAÇÃO: ANÁLISE DE ALGORITMOS E COMPLEXIDADE DE COMPUTAÇÃOpor
dc.titleCombinatorial Approaches for the Closest String Problempor
dc.typeTesepor
dc.contributor.advisor1orcidhttps://orcid.org/0000-0001-6401-3992por
dc.subject.userCombinatorial Optimizationeng
dc.subject.userInteger Programmingeng
dc.subject.userHeuristicseng
Appears in Collections:Doutorado em Informática

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

Download/Open Preview
Show simple item record Recommend this item


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