Genomic Sorting with Length-Weighted Reversals

Ron Y. Pinter[1] (
Steven Skiena[2] (

[1]Department of Computer Science, Technion -- Israel Institute of Technology, Haifa 32000, Israel
[2]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.

[ Full-text PDF | Table of Contents ]

Japanese Society for Bioinformatics