Ron Y. Pinter (email@example.com)
Steven Skiena (firstname.lastname@example.org)
Department of Computer Science,
Technion -- Israel Institute of Technology,
Haifa 32000, Israel
Department of Computer Science, State University of New York at Stony Brook, Stony Brook, NY 11794-4400, USA
Current algorithmic studies of genome rearrangement ignore the length of reversals (or inversions); rather, they only count their number. We introduce a new cost model in which the lengths of the reversed sequences play a role, allowing more flexibility in accounting for mutation phenomena. Our focus is on sorting unsigned (unoriented) permutations by reversals; since this problem remains difficult (NP-hard) in our new model, the best we can hope for are approximation results. We propose an efficient, novel algorithm that takes (a monotonic function f of) length into account as an optimization criterion and study its properties. Our results include an upper bound of O(f(n) lg2 n) for any additive cost measure f on the cost of sorting any n-element permutation, and a guaranteed approximation ratio of O( lg2n) times optimal for sorting a given permutation. Our work poses some interesting questions to both biologists and computer scientists and suggests some new bioinformatic insights that are currently being studied.