Orientador: Zanoni DiasDissertação (mestrado) - Universidade Estadual de Campinas, Instituto de ComputaçãoResumo: Rearranjos de Genomas, diferentemente das mutações mais comuns que afetam pontualmente o genoma, são eventos de mutação globais que agem sobre grandes trechos do genoma, e são um desafio para a Teoria da Computação, uma vez que, na maioria dos casos, computar a distância entre dois genomas considerando operações globais resultam em problemas NP-Difíceis. De forma similar, podemos definir o Problema da Ordenação de Genomas, em que buscamos calcular o número mínimo de eventos de rearranjos necessários para ordenar blocos conservados de genomas, 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. Dentre os eventos de rearranjo mais comuns, podemos citar as reversões e as transposições. Modelos considerando os dois eventos, separadamente, já possuem vasta bibliografia. Entretanto, modelos considerando os dois eventos em conjunto ainda são pouco explorados. Nesta dissertação, apresentamos diversas heurísticas para ordenação de permutações por reversões e transposições considerando permutações com sinais e permutações sem sinais. Para tanto, diversas métricas compatíveis com o problema foram utilizadas em heurísticas, que mais tarde foram testadas com um grande conjunto de permutações aleatórias. As métricas que obtiveram os melhores resultados foram utilizadas em uma heurística denominada Heurística de Grafo de Ciclos. Além disso, foram criados bancos de configurações que auxiliam esta heurística no processo de ordenação de uma permutação. Os resultados obtidos pela Heurística de Grafo de Ciclos foram comparados com algoritmos já existentes na literatura, tanto os que permitem reversões e transposições, bem como os que consideram apenas um dos eventos, evidenciando que a Heurística de Grafo de Ciclos produz os melhores resultados para todos os conjuntos de permutações com sinais, e em grande parte dos conjuntos de permutações sem sinaisAbstract: Genome rearrangements, unlike most common mutations that affects only one nucleotide, are global mutation events that affect large fragments of genomes and present a challenge to the Computational Theory Field, since in most cases, computing the distance between genomes considering global operations results in NP-Hard problems. Moreover, the Sorting Permutations by Genome Rearrangements problem seeks to compute the smallest number of rearrangement events needed to sort conserved blocks of genomes, with genomes represented by permutations. A rearrangement model determines which rearrangement events are allowed to sort a permutation or to transform a permutation into another. The two most common rearrangement events are reversals and transpositions. Rearrangement models considering reversals and transpositions separately have an extensive bibliography. However, models considering both events are still little explored. In this dissertation, we present some heuristics that sort permutations by reversals and transpositions considering signed and unsigned permutations. To do this, various metrics that are compatible with the problem were used. These heuristics were later tested with a large set of random permutations. Metrics that have achieved the best results were used in a heuristic named Cycle Graph Heuristic. In addition, cycle configurations were created and stored in a database in order to help our heuristic in the sorting process. The results obtained from Cycle Graph Heuristic were compared with existing algorithms in the literature, showing that our heuristic produces the best results for all sets of signed permutations and in many of the sets of unsigned permutationsMestradoCiência da ComputaçãoMestre em Ciência da Computação147337/2013-5CNPQ