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

Registro completo de metadados
MetadadosDescriçãoIdioma
Autor(es): dc.contributorMartinhon, Carlos Alberto de Jesus-
Autor(es): dc.contributorhttp://lattes.cnpq.br/2822582595834942-
Autor(es): dc.contributorLeitão, Helena Cristina da Gama-
Autor(es): dc.contributorhttp://buscatextual.cnpq.br/buscatextual/visualizacv.do?id=K4785003Z6-
Autor(es): dc.contributorLavor, Carlile Campos-
Autor(es): dc.contributorhttp://lattes.cnpq.br/2019624495480547-
Autor(es): dc.contributorProtti, Fábio-
Autor(es): dc.contributorhttp://lattes.cnpq.br/5898801580033554-
Autor(es): dc.creatorYamamoto, Keity-
Data de aceite: dc.date.accessioned2024-07-11T17:40:17Z-
Data de disponibilização: dc.date.available2024-07-11T17:40:17Z-
Data de envio: dc.date.issued2021-03-10-
Data de envio: dc.date.issued2008-05-06-
Data de envio: dc.date.issued2021-03-10-
Fonte completa do material: dc.identifierhttps://app.uff.br/riuff/handle/1/17864-
Fonte: dc.identifier.urihttp://educapes.capes.gov.br/handle/capes/755085-
Descrição: dc.descriptionIn 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-
Descrição: dc.descriptionNeste trabalho, apresentamos inicialmente alguns conceitos básicos e definições presentes na biologia molecular, visando uma maior compreensão de alguns dos problemas combinatórios mais freqüentes descritos na literatura. Daremos uma atenção especial ao problema da seqüência mais próxima (PSMP), que consiste na determinação de uma seqüência de caracteres que mais se aproxima, segundo uma dada métrica, de um conjunto pré-definido S de seqüências. Assim, dado um conjunto S = {s1,s2,...,sm} de seqüências (todas de tamanho n) sobre um alfabeto Σ, deseja-se determinar uma seqüência sH de tamanho n que minimize a maior distância entre sH e si, para todo i E {1...m}. Estudamos a prova de NP-Completude do PSMP e fizemos uma análise detalhada dos principais algoritmos aproximativos, determinísticos e randômicos, existentes na literatura. Na verdade, a grande maioria dos procedimentos existentes para o problema são baseados em métodos probabilísticos. Desta forma, fazemos uma descrição mais detalhada das técnicas de arredondamento randômico e derandomização, em particular o método das probabilidades condicionais, mostrando os avanços mais recentes obtidos até o momento. Desenvolvemos finalmente, uma estratégia de derandomização baseada no método de estimadores pessimistas introduzida por Raghavan em 1988-
Formato: dc.formatapplication/pdf-
Idioma: dc.languagept_BR-
Publicador: dc.publisherPrograma de Pós-Graduação em Computação-
Publicador: dc.publisherComputação-
Direitos: dc.rightsAcesso Aberto-
Direitos: dc.rightsCC-BY-SA-
Palavras-chave: dc.subjectCiência da computação-
Palavras-chave: dc.subjectBiologia computacional-
Palavras-chave: dc.subjectProblema da seqüência mais próxima-
Palavras-chave: dc.subjectDerandomização-
Palavras-chave: dc.subjectArredondamento randômico-
Palavras-chave: dc.subjectString problem-
Palavras-chave: dc.subjectComputational biology-
Palavras-chave: dc.subjectDerandomization-
Palavras-chave: dc.subjectRandomized round-
Palavras-chave: dc.subjectCNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO::TEORIA DA COMPUTACAO::COMPUTABILIDADE E MODELOS DE COMPUTACAO-
Título: dc.titleArredondamento randômico e o problema da seqüência mais próxima-
Tipo de arquivo: dc.typeDissertação-
Aparece nas coleções:Repositório Institucional da Universidade Federal Fluminense - RiUFF

Não existem arquivos associados a este item.