Arredondamento randômico e o problema da seqüência mais próxima

• Ano de defesa: 2008
• Autor(a) principal: Yamamoto, Keity
• Tipo de documento: Dissertação
• Tipo de acesso: Acesso aberto
• Idioma: por
• Instituição de defesa: Programa de Pós-Graduação em Computação; Computação
• Palavras-chave em Português: Ciência da computação; Biologia computacional; Problema da seqüência mais próxima; Derandomização; Arredondamento randômico; String problem; Computational biology; Derandomization; Randomized round; CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO::TEORIA DA COMPUTACAO::COMPUTABILIDADE E MODELOS DE COMPUTACAO
• Link de acesso: https://app.uff.br/riuff/handle/1/17864

In this work, we first present some basic concepts and definitions normally used in molecular biology. They are used, in order to describe some of most important combinatorial problems posed by the biologists. We will give a special attention to the Closest String Problem (CSP), which consists in the determination of a sequence sH of characters (belong to some alphabet Σ) that is closer to a given set S = {s1,s2,...,sm}of strings of Σ each of length n. The objective in this case is to find a sequence sH such that the maximum distance (according to a given metric) between sH and si for i=1...m is minimized. We study the proof of completeness of the CSP and concentrate our attention in the deterministic and randomized approximation algorithms listed in the literature. In fact, the major part of these techniques are based on probabilistic methods. For this reason, we present the most recent results, and give a detailed description of these strategies such as the randomized rounding procedure and the derandomization techniques, in particular, the method of conditional probability. Finally, we develop a derandomization strategy using pessimistic estimators as proposed by Raghavan in 1988