Please use this identifier to cite or link to this item: http://repositorio.unicamp.br/jspui/handle/REPOSIP/334401
Type: DISSERTAÇÃO DIGITAL
Degree Level: Mestrado
Title: Ordenação de permutações com sinais por reversões e transposições
Title Alternative: Sorting signed permutations by reversals and transpositions
Author: Brito, Klairton de Lima, 1991-
Advisor: Dias, Zanoni, 1975-
Abstract: Resumo: Neste trabalho, apresentamos três heurísticas para melhorar os resultados de algoritmos para o problema de Ordenação de Permutações com Sinais por Reversões e Transposições. Nossas heurísticas foram aplicadas tanto na versão clássica do problema quanto nas versões restrita a operações de prefixo e restrita a operações de prefixo ou sufixo. A nossa primeira heurística é chamada de Sliding Window, executa em tempo linear e fornece bons resultados. A nossa segunda heurística, Look Ahead, possui tempo de execução mais elevado dependendo do estimador de distância que é utilizado, mas seus resultados são mais expressivos. Nossa última heurística é chamada de Iterative Sliding Window e apresenta melhor custo-benefício entre o tempo de execução e a qualidade da solução em comparação com as duas primeiras heurísticas. Mostramos que as heurísticas Look Ahead e Sliding Window podem ser combinadas visando fornecer resultados ainda melhores. Para verificar o comportamento de nossas heurísticas, implementamos diversos algoritmos da literatura e realizamos experimentos práticos onde observamos melhorias em relação aos algoritmos originais. Efetuamos ainda um comparativo de desempenho entre nossas próprias heurísticas. Investigamos também o problema de Ordenação de Permutações com Sinais por Reversões e Transposições Ponderadas, adotando os pesos 2 e 3 para os eventos de reversão e transposição, respectivamente. Conseguimos apresentar limitantes inferiores para o problema e quatro algoritmos de aproximação. Dois desses algoritmos adotam uma estratégia gulosa e apresentam fatores de aproximação 3 e 2, enquanto os outros dois utilizam a estrutura de grafo de ciclos para ordenar a permutação e apresentam fatores de aproximação 5/3 e 3/2. Realizamos experimentos práticos com diferentes grupos de permutações com características distintas. Estendemos nossa investigação para considerar outras relações de peso entre os eventos de transposição e reversão. Mostramos também uma análise que considera essas relações distintas de peso e apresentamos o melhor fator de aproximação obtido para cada uma dessas relações

Abstract: In this work, we present three heuristics to improve existing solutions for the Sorting Signed Permutations by Reversals and Transpositions problem. To assess the heuristics, we implemented algorithms described in the literature to provide initial solutions. We investigated the classical version of the problem as well as versions restricted to prefix operations and restricted to prefix or suffix operations. The first heuristic is called Sliding Window, it runs in linear time and provides good results. The second heuristic is called Look Ahead and showed remarkable results, but its execution time increases depending on the distance estimator used. Our last heuristic is called Iterative Sliding Window and it showed better results when we consider solution quality and execution time. We showed that the heuristics Look Ahead and Sliding Window can be combined to further improve the solutions. We performed the experiments and showed the improvement obtained by our heuristics compared with the solutions provided by the original algorithms. We also compared the three heuristics among themselves. We also investigated the Sorting Signed Permutations by Weighted Reversals and Weighted Transpositions problem using weights 2 and 3 for reversals and transpositions, respectively. We showed lower bounds and developed four approximation algorithms for the problem. Two of these algorithms use a strategy based on breakpoints and have approximation factors 3 and 2. The other two algorithms resort to a structure called cycle graph to sort the permutations and achieved the approximation factors 5/3 and 3/2. We executed these algorithms in five groups of permutations with different characteristics. To conclude this work, we made an analysis that considers different weights for reversal and transposition events and showed the best approximation factor obtained in each case
Subject: Biologia computacional
Genomas
Heurística (Computação)
Algoritmos de aproximação
Language: Português
Editor: [s.n.]
Citation: BRITO, Klairton de Lima. Ordenação de permutações com sinais por reversões e transposições. 2018. 1 recurso online (95 p.). Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação, Campinas, SP.
Date Issue: 2018
Appears in Collections:IC - Tese e Dissertação

Files in This Item:
File SizeFormat 
Brito_KlairtonDeLima_M.pdf1.29 MBAdobe PDFView/Open


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