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 | Ayala-Rincón, Mauricio | - |
Autor(es): dc.creator | Lima, Thaynara Arielly de | - |
Data de aceite: dc.date.accessioned | 2021-10-14T18:05:52Z | - |
Data de disponibilização: dc.date.available | 2021-10-14T18:05:52Z | - |
Data de envio: dc.date.issued | 2010-12-03 | - |
Data de envio: dc.date.issued | 2010-12-03 | - |
Data de envio: dc.date.issued | 2010-12-03 | - |
Data de envio: dc.date.issued | 2010 | - |
Fonte completa do material: dc.identifier | http://repositorio.unb.br/handle/10482/6088 | - |
Fonte: dc.identifier.uri | http://educapes.capes.gov.br/handle/capes/623453 | - |
Descrição: dc.description | Dissertação (mestrado)—Universidade de Brasília, Instituto de Ciências Exatas, Departamento de Matemática, 2010. | - |
Descrição: dc.description | Na genômica comparativa soluções algoríıtmicas eficientes para o problema da dist ância de rearranjo de genomas são uma ferramenta importante para o desenvolvimento de software que permite estabelecer relacionamento evolutivo entre organismos, por exemplo para a constr~ção de árvores filogenéticas de organismos. Existem diversas operações sobre palavras que modelam mutações ocorridas nos genes dos seres vivos (e.g. reversões, transposições, troca de blocos, etc.). Restritos à operação de reversão o problema de rearranjo de genomas ´é NP-difícil. Sendo assim, é plausível considerar algoritmos de aproximação. O algoritmo conhecido que melhor aproxima a solução do problema de rearranjo via reversões tem raio de 1.375. No seu artigo seminal, Bafna e Pevzner apresentam soluções O(n2) de raios de aproximação 1.5 para permutações com sinal e 7 4 para permutações sem sinal. Neste trabalho propõ-se um uso cuidadoso e discriminado entre as representações combinatória (palavras e grafos de pontos de quebra) e algébrica (ciclos de permuta ções) das permutações, que contribuirão para analisar com precisão e de maneira adequada diversas características do problema da distância de reversão e das soluções apresentadas por Bafna e Pevzner. _________________________________________________________________________________ ABSTRACT | - |
Descrição: dc.description | Efficient algorithmic solutions to the problem of genome rearrangements in comparative genomics are an important tool for the development of software allowing one to estabilish the evolution link between organisms, for instance the construction of phylogenetic trees. There are several string operations modelling mutations occurring inside genes (e.g. reversals, transpositions and block interchange, etc.). When restricted to the reversal operation, the problem of genome rearrangement is NP-hard. Thus, polynomially bounded approximated algorithms are considered to be admissible solutions. The best known approximated algorithm to solve the rearrangement problem through reversals has approximation ratio of 1.375. In their seminal paper, Bafna and Pevzner presented O(n2) solutions of ratio 1.5 for signed permutations and 7 4 for unsigned permutations. This work proposes a careful discrimination between the combinatory (strings and breakpoint graphs) and the algebraic (cycles of permutations) representations of permutations to analyse precisely, and in an adequate way, many of the problem characteristics and solutions presented by Bafna and Pevzner. | - |
Formato: dc.format | application/pdf | - |
Direitos: dc.rights | Acesso Aberto | - |
Palavras-chave: dc.subject | Algoritmos genéticos | - |
Palavras-chave: dc.subject | Teoria dos grafos | - |
Título: dc.title | Representação combinatória e algébrica das permutações na análise do problema de rearranjo de genomas por reversões | - |
Tipo de arquivo: dc.type | livro digital | - |
Aparece nas coleções: | Repositório Institucional – UNB |
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: