Please use this identifier to cite or link to this item: http://repositorio.unicamp.br/jspui/handle/REPOSIP/276511
Type: DISSERTAÇÃO
Degree Level: Mestrado
Title: Distancias de transposição entre genomas
Title Alternative: Transposition distances between genomes
Author: Fortuna, Vinicius Jose
Advisor: Meidanis, João, 1960-
Abstract: Resumo: Uma das principais formas de se medir a distância evolutiva entre espécies é avaliando-se quão transformado um genoma foi em relação a outro. Tais transformações são conhecidas como rearranjos de genoma. Neste trabalho estaremos analisando o rearranjo chamado de transposição, evento que troca de posição dois blocos consecutivos de genes de um mesmo cromossomo. Mais especificamente, buscamos encontrar o número mínimo de transposições que transforma um cromos somo em outro, valor conhecido como distância de transposição. Matematicamente, consideramos os cromossomos como permutações e o problema de se transformar uma permutação em outra pode ser visto como uma ordenação. Em nosso estudo, introduzimos uma operação de remoção de elementos, ferramenta ainda pouco explorada no estudo da distância de transposição, mas que nos possibilitou obter um limite superior para a distância de transposição. Também sugerimos novas formas de se utilizar a remoção de elementos e a análise de subseqüências de permutações. Como forma de se tentar obter novos conhecimentos sobre o problema da distância de transposição, consideramos a variação do problema em que somente transposições de prefixo são permitidas. Zanoni Dias propôs um algoritmo polinomial que transforma qualquer permutação de comprimento n em sua reversa em f3n/41 passos, porém sem uma prova completa. Modificamos esse algoritmo, mantendo o número de passos, e apresentamos uma prova completa da correção do algoritmo modificado. Ainda no problema de distância de transposição de prefixo, analisamos as permutações cujas distâncias se igualam ao limite inferior de distância de pontos de quebra. Tais permutações são fáceis de serem ordenadas por transposições de prefixo em tempo polinomial, pois possuem ordenação ótima única e bem definida. Ao final chegamos à conclusão que as permutações que são fáceis de se ordenar no problema de transposições de prefixo também são fáceis no problema de transposições, o que prova que a variação do problema auxilia no estudo do problema original

Abstract: One of the main ways of measuring the evolution distance among species is to evaluate how large chunks have moved when comparing two genomes. Such changes are know as genome rearrangements. In this work we analyze a rearrangement event called transposition that changes the position of two consecutive blocks of genes in a chromosome. More specifically, we look for the minimum number of transpositions needed to transform a chromosome into another. This value is called the transposition distance. Mathematically, chromosomes are regarded as permutations and changing one genome into another can be seen as a sorting problem. In our study, we introduce an operation of element removal from permutations, which has not been fully explored, but allowed us to find an upper bound for the transposition distance. We also suggest new ways of making use of element removal and the analysis of permutation subsequences. In the hope of obtaining new knowledge about the problem of transposition distance, we considered the variation of the problem where we allow prefix transpositions only. Zanoni Dias developed a polynomial algorithm that changes any permutation into its reverse using f3n/41 steps, but without a proof of its correctness. We have modified this algorithm, keeping the number of steps, and presented a complete proof of the correction of the modified algorithm. Still about the prefix transposition distance, we have analyzed those permutations whose distance equals the breakpoint lower bound. Such permutations are easily sorted by prefix transpositions in polynomial time, since they have a unique and well-defined optimum sorting. Finally, we concluded that the permutations that are easily sorted in the prefix transposition problem are also easily sorted in the transposition problem, which proves that the variation of the problem helps the study of the original problem
Subject: Teoria da computação
Filogenia
Genomas
Language: Português
Editor: [s.n.]
Date Issue: 2005
Appears in Collections:IC - Tese e Dissertação

Files in This Item:
File SizeFormat 
Fortuna_ViniciusJose_M.pdf2.26 MBAdobe PDFView/Open


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