## Genomic Sorting with Length-Weighted Reversals

Ron Y. Pinter[1] (pinter@cs.technion.ac.il)

Steven Skiena[2] (skiena@cs.sunysb.edu)

[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

### Abstract

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)* lg^{2} *n*)
for any additive cost measure f on the cost of sorting any *n*-element
permutation, and a guaranteed approximation ratio of *O( lg*^{2}n) 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.

*Japanese Society for Bioinformatics*