Advanced search options

Advanced Search Options 🞨

Browse by author name (“Author name starts with…”).

Find ETDs with:

in
/  
in
/  
in
/  
in

Written in Published in Earliest date Latest date

Sorted by

Results per page:

You searched for subject:(Bioinform tica). One record found.

Search Limiters

Last 2 Years | English Only

No search limiters apply to these results.

▼ Search Limiters

1. Vilca, Omar Latorre. Combinatorial Approaches for the Closest String Problem.

Degree: 2019, Universidade Federal do Amazonas

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.

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.

CAPES - Coordena??o de Aperfei?oamento de Pessoal de N?vel Superior

Advisors/Committee Members: Feitosa, Eduardo Luzeiro, 5939944067207881, http://lattes.cnpq.br/5939944067207881, Collona, Juan Gabriel, Nakamura, Fab?ola Guerra, Onety, Renata da Encarna??o, Craveiro, Joaquim Maciel da Costa, [email protected], https://orcid.org/0000-0001-6401-3992.

Subjects/Keywords: 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

Record DetailsSimilar RecordsGoogle PlusoneFacebookTwitterCiteULikeMendeleyreddit

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6th Edition):

Vilca, O. L. (2019). Combinatorial Approaches for the Closest String Problem. (Doctoral Dissertation). Universidade Federal do Amazonas. Retrieved from https://tede.ufam.edu.br/handle/tede/7449

Chicago Manual of Style (16th Edition):

Vilca, Omar Latorre. “Combinatorial Approaches for the Closest String Problem.” 2019. Doctoral Dissertation, Universidade Federal do Amazonas. Accessed February 20, 2020. https://tede.ufam.edu.br/handle/tede/7449.

MLA Handbook (7th Edition):

Vilca, Omar Latorre. “Combinatorial Approaches for the Closest String Problem.” 2019. Web. 20 Feb 2020.

Vancouver:

Vilca OL. Combinatorial Approaches for the Closest String Problem. [Internet] [Doctoral dissertation]. Universidade Federal do Amazonas; 2019. [cited 2020 Feb 20]. Available from: https://tede.ufam.edu.br/handle/tede/7449.

Council of Science Editors:

Vilca OL. Combinatorial Approaches for the Closest String Problem. [Doctoral Dissertation]. Universidade Federal do Amazonas; 2019. Available from: https://tede.ufam.edu.br/handle/tede/7449

.