title: Approximate strip exchanging.
abstract: Genome rearrangements have been modelled by a variety of primitives such as reversals, transpositions, block moves and block interchanges. We consider such a genome rearrangement primitive Strip Exchanges. Given a permutation, the challenge is to sort it by using minimum number of strip exchanges. A strip exchanging move interchanges the positions of two chosen strips so that they merge with other strips. The strip exchange problem is to sort a permutation using minimum number of strip exchanges. We present here the first non-trivial 2-approximation algorithm to this problem. We also observe that sorting by strip-exchanges is fixed-parameter-tractable. Lastly we discuss the application of strip exchanges in a different area Optical Character Recognition (OCR) with an example.
authors.affiliation: IBM India Pvt. Ltd., India Software Lab, Information Management, c/ Embassy Golf Links Business Park, Bangalore, India. swapnoneel.roy@in.ibm.com
authors.forename: Swapnoneel
authors.initials: S
authors.lastname: Roy
authors.forename: Ashok Kumar
authors.initials: AK
authors.lastname: Thakur
mesh_terms: D000465:Algorithms; D019295:Computational Biology; D003198:Computer Simulation; D015321:Gene Rearrangement; D016678:Genome; D008957:Models, Genetic