Resumo: Ao longo da evolução, eventos de rearranjo podem alterar a ordem e a orientação dos genes de um genoma. O problema de calcular a menor sequência de rearranjos que transforma um genoma em outro é um problema bastante estudado que encontra aplicações em genômica comparativa. Representando genomas como permutações, nas quais os genes aparecem como elementos, esse problema pode ser reduzido ao problema combinatório de ordenar uma permutação utilizando o menor número de rearranjos. Tal problema combinatório, referido como problema da ordenação por rearranjo, varia de acordo com os tipos de rearranjo considerados. Nesta tese, focamos nosso estudo em dois tipos de rearranjo: reversões e transposições. Muitas variações do problema da ordenação por rearranjo que envolvem esses rearranjos têm sido atacadas na literatura e, para a maior parte delas, os melhores algoritmos conhecidos são aproximações ou heurísticas. Em razão disso, apresentamos uma ferramenta, chamada GRAAu, que auxilia a avaliação dos resultados produzidos por esses algoritmos. Além disso, apresentamos uma heurística genérica que pode ser usada para melhorar as soluções produzidas por qualquer algoritmo não exato. Além de apresentar o GRAAu e a heurística de melhoria, os quais possuem um apelo mais geral, apresentamos contribuições relacionadas à variações específicas do problema da ordenação por rearranjo. Primeiro, consideramos o problema da ordenação por transposições e apresentamos resultados teóricos e práticos relacionados a três algoritmos aproximados baseados em uma abordagem alternativa ao grafo de ciclos, que é uma ferramenta padrão para atacar o problema da ordenação por rearranjo. Depois, voltamos nossa atenção à variações que envolvem rearranjos curtos. Mais precisamente, estudamos cinco variações: (i) o problema de ordenar uma permutação linear com sinal por reversões super curtas, (ii) o problema de ordenar uma permutação circular com sinal por reversões super curtas, (iii) o problema de ordenar uma permutação linear com sinal por reversões curtas, (iv) o problema de ordenar uma permutação linear com sinal por rearranjos super curtos e (v) o problema de ordenar uma permutação linear com sinal por rearranjos curtos. Apresentamos algoritmos polinomiais para os problemas (i), (ii) and (iv), um algoritmo 5-aproximado para o problema (iii) e um algoritmo 3-aproximado para o problema (v). Usamos o algoritmo desenvolvido para o problema (ii) para reconstruir a filogenia de genomas de bactérias do gênero Yersinia e comparamos os resultados com as filogenias apresentadas em trabalhos anteriores Ver menos

Abstract: During evolution, rearrangement events may alter the order and the orientation of the genes in a genome. The problem of finding the minimum sequence of rearrangements that transforms one genome into another is a well-studied problem that finds application in comparative genomics. Representing genomes as permutations, in which genes appear as elements, that problem can be reduced to the combinatorial problem of sorting a permutation using a minimum number of rearrangements. Such combinatorial problem, referred to as rearrangement sorting problem, varies according to the types of rearrangements considered. In this thesis, we focus on two types of rearrangements: reversals and transpositions. Many variants of the rearrangement sorting problem involving these rearrangements have been tackled in the literature and, for most of them, the best known algorithms are approximations or heuristics. For this reason, we present a tool, called GRAAu, to aid in the evaluation of the results produced by these algorithms. In addition, we present a general heuristic that can be used to improve the solutions provided by any non-optimal algorithm. Besides presenting GRAAu and the improvement heuristic, which have a more general appeal, we present contributions regarding specific variants of the rearrangement sorting problem. First, we consider the problem of sorting by transpositions and we present experimental and theoretical results regarding three approximation algorithms based on alternative approaches to the cycle graph, which is a standard tool for attacking the rearrangement sorting problem. Then, we turn our attention to variants involving short rearrangements. More precisely, we study five variants: (i) the problem of sorting a signed linear permutation by super short reversals, (ii) the problem of sorting a signed circular permutation by super short reversals, (iii) the problem of sorting a signed linear permutation by short reversals, (iv) the problem of sorting a signed linear permutation by super short rearrangements, and (v) the problem of sorting a signed linear permutation by short rearrangements. We present polynomial-time algorithms for problems (i), (ii) and (iv), a 5-approximation algorithm for problem (iii), and a 3-approximation algorithm for problem (v). We use the algorithm developed for problem (ii) to reconstruct the phylogeny of Yersinia genomes and compare the result with the phylogenies presented in previous works Ver menos