O cálculo do número mínimo de eventos de rearranjo de genomas que transformam o genoma de uma espécie em outra é usado para inferir o grau de parentesco entre duas espécies. Devido ao fato da reversão ser, muitas vezes, o único evento de rearranjo de genomas presente em um único cromossomo, o Problema Ordenação po Reversões (MIN-SBR) têm sido estudado, principalmente, nos últimos anos. Nessa disertação estudamos as duas versões de MIN-SBR: a versão orientada, representada por uma permutação orientada, isto é, quando conhecemos a orientação dos genes em relação ao cromossomo, e a versão não-orientada, representada por uma permutação não-orientada, quando não conhecemos essa orientação. Para a versão orientada, Hannenhalli e Pevzner (HP95) descreveram um algoritmo polinominal, que, dada uma permutação orientada'VET.pi' com n elementos, determina uma seqüência mínima de reversões que ordenam 'VET.pi'em tempo O('n IND.5'). Posteriormente, uma versão mais eficiente desse algoritmo foi descrita por Kaplan, Shamir e Tarjan {KST97} cujo tempo é O(n'alfa'(n)+nr), onde 'alfa'(n) é o inverso da função de Ackerman e d é o número mínimo de reversões que ordena 'VET.pi'. Descrevemos uma versão para esse algoritmo que gasta tempo O(nd). Mostramos também, resumidamente, os trabalhos de Meidanis, Walter e Dias [MWD97] que determinam o valor do diâmetro por reversões em permutações orientadas, e formalizam a versão orientada do problema em permutações orientadas circulares, modeladas para estudar o número mínimo de reversões que transformam um cromossomo circular em outro. Para a versão não-orientada do problema, descrevemos o algoritmo polinomial aproximado de Bafna e Pevzner [BP93] que encontra uma seqüência de reversões (que ordenam uma permutação não-orientada 'pi' com n elementos) de tamanho menor ou igual a 7/4 do tamanho da seqüência mínima de reversões que ordena 'pi', e o valor do diâmetro por reversões em ) permutações não-orientadas. Por fim, descrevemos a prova de Caprara [Cap96] de que a versão não orientada de MIN-SBR é NP-difícil

The calculus of the minimal number of genome rearrangements'events that turn the genome of one specie into another is used to infer the level of relationship among two specie. Because the reversal is, many times, the only genome rearrangements'events present in only one chomosome, the problem of sorting by reversals (MIN-SBR) have been studie, mainly, in the last years. In the dissertation, we studied the two MIN-SBR versions: the signed version, represented by a signed permutation, that is, when we know the relationship between the orientation of the genes and the chromosome, and the unsigned version, represented by a unsigned permutation, when we do not know this orientation. For the signed version, HP95 described a polinomial algorithm that given a signed permutation 'VET.pi' with n elements determine a minimal sequence of reversals that sorting 'VET.pi' in O('n IND.5') time. Later, a more efficient version of this algorithm was described by KST97, whose time is O(n'alfa'(n)+nr), where 'alfa'(n) is the inverse of Ackerman's function, and d is the minimal number of reversals that sorts 'VET.pi'. We describe a version of this algorithm that runs in O(nd) time. We also show, briefly, the work of MWD97 that determine the value of reversal diameter of signed permutations, and formalize the signed version of the circular signed permutations problem, modeled to study the minimal number of reversals that turn one circular chromosome into another. For the unsigned version of problem, we describe the approximation polinomial algorithm by BP93 that finds a reversal sequence (that sorts aunsigned permutation 'pi' with n elements)wich size is at the most7/4 of minimal reversals sequence size that sort 'pi', and the value of reversal diameter in unsigned permutation. Finally, we describe the Caprara's proof[Cap96] of theNP-hardness of the MIN-SBR unsigned version