Please use this identifier to cite or link to this item: http://repositorio.unicamp.br/jspui/handle/REPOSIP/305632
Type: DISSERTAÇÃO DIGITAL
Degree Level: Mestrado
Title: O problema da ordenação por reversões ponderadas
Title Alternative: Sorting by length-weighted inversions
Author: Arruda, Thiago da Silva, 1988-
Advisor: Dias, Zanoni, 1975-
Abstract: Resumo: Rearranjos de genomas são eventos de mutação globais que agem sobre grandes trechos de um genoma, diferentemente das mutações mais comuns que afetam pontualmente o genoma. Na maioria dos casos, computar a distância de rearranjo de genomas entre dois genomas resulta em problemas NP-difíceis. Em um problema da ordenação por Rearranjo de Genomas desejamos calcular a sequência de eventos de rearranjos necessários para ordenar blocos conservados de genomas com custo mínimo, onde os genomas são representados por permutações. Um modelo de rearranjo determina quais eventos de rearranjo são permitidos para ordenar uma permutação ou transformar uma permutação em outra. Neste trabalho abordamos o modelo de eventos de reversão, que ocorre quando um segmento do genoma é revertido. No problema clássico de ordenação por reversões, o custo para qualquer reversão em uma permutação é unitário, independente do tamanho do segmento a ser revertido. Novos estudos mostraram que a mecânica de rearranjo de genomas sugere que reversões com tamanho de segmento menor ocorrem com maior frequência. Desta forma, abordamos neste trabalho o problema de ordenação por reversões ponderadas, onde o custo de cada reversão é igual ao tamanho do segmento revertido. Para obter soluções para o problema, inicialmente nós desenvolvemos um algoritmo heurístico polimomial para a variação do problema em que a orientação dos genes não é considerada (que resulta em uma permutação sem sinal), e obtivemos resultados experimentais superiores aos algoritmos anteriormente conhecidos, considerando todas as permutações de tamanho até 10 e amostras de permutações maiores de tamanho até 100. Em seguida desenvolvemos uma Meta-heurística iterativa que segue a estratégia GRASP (Greedy Randomized Adaptive Search Procedure). Este método foi aplicado também à variação do problema em que a orientação dos genes é considerada (que resulta em uma permutação com sinal). Para ambas variações nós executamos experimentos para amostras de permutações de tamanho no intervalo de 10 a 100 e mostramos que nosso método apresenta resultados significativamente superiores a todas as outras abordagens anteriores

Abstract: Genome rearrangements are global mutation events that act on large stretches of a genome. Those are unlike the more common mutations, that affect the genome punctually. In most cases, the computation of genome rearrangement distance between two genomes induces NP-Hard problems. Genome sorting problems aims to calculate the sequence of rearrangements events required to sort conserved genomes blocks with minimum cost, where genomes are represented by permutations. A rearrangement model determines which rearrangement events are allowed to sort a permutation or transform a permutation in to another. In this work, we deal with inversion events, which occur when a segment of DNA sequence in the genome is reversed. In the classic problem of sorting by inversions, the cost of any inversion in a permutation is unitary, independent of segment size to be reversed. Further studies showed that reversals with lower segment size occur with greater frequency. In this way, we address the sorting by weighted inversions problem and, in our model, each inversion costs the number of elements in the reversed segment. In order to generate solutions for this problem, we initially developed a polinomial heuristic algorithm for the problem variation where the gene orientation is not taken in consideration (where we use unsigned permutations). With this first method we ran experiments, taking as input all permutations of size up to 10 and sample permutations with size up 100, and we obtained results that outperform previously known algorithms. Then we developed an iterative meta-heuristic that follows the GRASP strategy (Greedy Randomized Adaptive Search Procedure). This time the method supported as well the variation of the problem that takes genes orientation in consideration (which results in a signed permutation). For both variations we ran experiments with samples of permutation with size in the range from 10 to 100, and we show that our method provided significantly better results than all the other previously known approaches
Subject: Biologia computacional
Genomas
Algoritmos heurísticos
Meta-heurística
Permutações (Matemática)
Editor: [s.n.]
Date Issue: 2016
Appears in Collections:IC - Tese e Dissertação

Files in This Item:
File SizeFormat 
Arruda_ThiagodaSilva_M.pdf1.13 MBAdobe PDFView/Open


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