Motivated by the problem in computational biology of reconstructing the series of chromosome inversions by which one organism evolved from another, we consider the proble m of computing the shortest series of reversals that transform one permutation to another, The permutations describe the order of genes on corresponding chromosomes, and a reversal takes an arbitrary substring of elements and reverses their order. For this problem we develop two algorithms: a greedy approximation algorithm that finds a solution provably close to optimal in O(n 2) time and O(n) space for an n element permutation, and a branch and bound exact algorithm that finds an optimal solution in O(mL(n, n)) time and O(n 2) space, where m is the size of the branch and bound search tree and L(n, n) is the time to solve a linear program of n variables and n constraints. The greedy algorithm is the first to come within a constant factor of the optimum, and guarantees a solution that uses no more than twice the minimum number of reversals. The lower and upper bounds of the branch and bound algorithm are a novel application of maximum weight matehings, shortest paths, and linear programming. In a series of experiments we study the performance of an implementation. For random permutations we find that the average difference between the upper and lower bounds is less than 3 reversals for n ≤ 50. Due to the tightness of these bounds we can solve to optimality random permutations on 30 elements in a few minutes of computer time.