Block Sorting: A New Characterization and a New Heuristic

Authors: Swapnoneel Roy, Ashok Kumar Thakur, Minhazur Rahman

Abstract:

The Block Sorting problem is to sort a given permutation moving blocks. A block is defined as a substring of the given permutation, which is also a substring of the identity permutation. Block Sorting has been proved to be NP-Hard. Until now two different 2-Approximation algorithms have been presented for block sorting. These are the best known algorithms for Block Sorting till date. In this work we present a different characterization of Block Sorting in terms of a transposition cycle graph. Then we suggest a heuristic, which we show to exhibit a 2-approximation performance guarantee for most permutations.

Keywords: Block Sorting, Optical Character Recognition, Genome Rearrangements, Sorting Primitives, ApproximationAlgorithms

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1330531

References:

[1] M. Mahajan, R.Rama, V. Raman, and S. Vijaykumar. Approximate block sorting. International Journal of Foundation of Computer Science, to appear.
[2] M. Mahajan, R.Rama, and S. Vijaykumar. Towards constructing optimal block move sequences. In proc. of the 10th International Computing and Combinatorial conference, COCOON 2004, LNCS vol.3106, pages 33-42. Springer-Verlag, Aug 2004.
[3] P. Pevzner. Computational Molecular Biology: An Algorithmic Approach. MIT Press, Cambridge, MA, USA, 2000.
[4] V.Bafna and P.Pevzner. Genome rearrangements and sorting by reversals. SIAM Journal on Computing, 25:272-289, 1996.
[5] V.Bafna and P.Pevzner. Sorting by transpositions. SIAM Journal on Discrete Mathematics 11(2):224-240, may 1998.
[6] W.W. Bein, L.L. Larmore, L. Morales, and I.H. Sudborough. A Polymomial Time 2-Approximation for Block Sorting. Unpublished manuscript, available at http://www.egr.unlv.edu/ bein/pubs/twoblock.ps.
[7] W.W. Bein, L.L. Larmore, L. Morales, and I.H. Sudborough. Block sorting is hard. Intl. Jl. of Foundations of Computer science, 14:425-437, 2003.
[8] G.H Lin and G Xue. Signed genome arrangement by reversals and transpositions: Models and approximations. Theoretical Computer Science, 259:513-531, 2001.