Title: Approximate strip exchanging

Authors: Swapnoneel Roy, Ashok Kumar Thakur

Addresses: IBM India Pvt. Ltd., India Software Lab, Information Management, c/ Embassy Golf Links Business Park, Bangalore, India. ' IBM India Pvt. Ltd., India Software Lab, Information Management, c/ Embassy Golf Links Business Park, Bangalore, India

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.

Keywords: strip exchanges; genome rearrangement; sorting primitives; approximation algorithms; optical character recognition; OCR; gene sequesnces.

DOI: 10.1504/IJCBDD.2008.018712

International Journal of Computational Biology and Drug Design, 2008 Vol.1 No.1, pp.88 - 101

Published online: 14 Jun 2008 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article