Skip navigation
Please use this identifier to cite or link to this item: http://repositorio.unb.br/handle/10482/6088
Files in This Item:
File Description SizeFormat 
2010_ThaynaraAriellydeLima.pdf415,97 kBAdobe PDFView/Open
Title: Representação combinatória e algébrica das permutações na análise do problema de rearranjo de genomas por reversões
Authors: Lima, Thaynara Arielly de
Orientador(es):: Ayala-Rincón, Mauricio
Assunto:: Algoritmos genéticos
Teoria dos grafos
Issue Date: 3-Dec-2010
Citation: LIMA, Thaynara Arielly de. Representação combinatória e algébrica das permutações na análise do problema de rearranjo de genomas por reversões. 2010. 65 f. Dissertação (Mestrado em Matemática)-Universidade de Brasília, Brasília, 2010.
Abstract: 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
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.
Description: Dissertação (mestrado)—Universidade de Brasília, Instituto de Ciências Exatas, Departamento de Matemática, 2010.
Appears in Collections:MAT - Mestrado em Matemática (Dissertações)

Show full item record Recommend this item " class="statisticsLink btn btn-primary" href="/handle/10482/6088/statistics">



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.