Atenção: Todas as denúncias são sigilosas e sua identidade será preservada.
Os campos nome e e-mail são de preenchimento opcional
Metadados | Descrição | Idioma |
---|---|---|
Autor(es): dc.contributor | Martinhon, Carlos Alberto de Jesus | - |
Autor(es): dc.contributor | http://lattes.cnpq.br/2822582595834942 | - |
Autor(es): dc.contributor | Leitão, Helena Cristina da Gama | - |
Autor(es): dc.contributor | http://buscatextual.cnpq.br/buscatextual/visualizacv.do?id=K4785003Z6 | - |
Autor(es): dc.contributor | Lavor, Carlile Campos | - |
Autor(es): dc.contributor | http://lattes.cnpq.br/2019624495480547 | - |
Autor(es): dc.contributor | Protti, Fábio | - |
Autor(es): dc.contributor | http://lattes.cnpq.br/5898801580033554 | - |
Autor(es): dc.creator | Yamamoto, Keity | - |
Data de aceite: dc.date.accessioned | 2024-07-11T17:40:17Z | - |
Data de disponibilização: dc.date.available | 2024-07-11T17:40:17Z | - |
Data de envio: dc.date.issued | 2021-03-10 | - |
Data de envio: dc.date.issued | 2008-05-06 | - |
Data de envio: dc.date.issued | 2021-03-10 | - |
Fonte completa do material: dc.identifier | https://app.uff.br/riuff/handle/1/17864 | - |
Fonte: dc.identifier.uri | http://educapes.capes.gov.br/handle/capes/755085 | - |
Descrição: dc.description | 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 | - |
Descrição: dc.description | Neste 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.format | application/pdf | - |
Idioma: dc.language | pt_BR | - |
Publicador: dc.publisher | Programa de Pós-Graduação em Computação | - |
Publicador: dc.publisher | Computação | - |
Direitos: dc.rights | Acesso Aberto | - |
Direitos: dc.rights | CC-BY-SA | - |
Palavras-chave: dc.subject | Ciência da computação | - |
Palavras-chave: dc.subject | Biologia computacional | - |
Palavras-chave: dc.subject | Problema da seqüência mais próxima | - |
Palavras-chave: dc.subject | Derandomização | - |
Palavras-chave: dc.subject | Arredondamento randômico | - |
Palavras-chave: dc.subject | String problem | - |
Palavras-chave: dc.subject | Computational biology | - |
Palavras-chave: dc.subject | Derandomization | - |
Palavras-chave: dc.subject | Randomized round | - |
Palavras-chave: dc.subject | CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO::TEORIA DA COMPUTACAO::COMPUTABILIDADE E MODELOS DE COMPUTACAO | - |
Título: dc.title | Arredondamento randômico e o problema da seqüência mais próxima | - |
Tipo de arquivo: dc.type | Dissertação | - |
Aparece nas coleções: | Repositório Institucional da Universidade Federal Fluminense - RiUFF |
O Portal eduCAPES é oferecido ao usuário, condicionado à aceitação dos termos, condições e avisos contidos aqui e sem modificações. A CAPES poderá modificar o conteúdo ou formato deste site ou acabar com a sua operação ou suas ferramentas a seu critério único e sem aviso prévio. Ao acessar este portal, você, usuário pessoa física ou jurídica, se declara compreender e aceitar as condições aqui estabelecidas, da seguinte forma: