Approximate strip exchanging.
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.
Roy
Swapnoneel
S
IBM India Pvt. Ltd., India Software Lab, Information Management, c/ Embassy Golf Links Business Park, Bangalore, India. swapnoneel.roy@in.ibm.com
Thakur
Ashok Kumar
AK
D000465:Algorithms; D019295:Computational Biology; D003198:Computer Simulation; D015321:Gene Rearrangement; D016678:Genome; D008957:Models, Genetic