A Practical Exponential-Time Algorithm on Sorting by Short Block-Moves

Sorting by short block-moves is one of the several approaches recently used for genome rearrangement, and most of the minimum sorting questions by these approaches have been proved to be NP-complete or NP-hard or even PSPACE-complete. Nevertheless, the complexity of minimum sorting by block-moves remains unsolved, and approximation algorithms for it and polynomial-time algorithms on special permutations for it are continuously devised. This paper gives an exponential-time algorithm of minimum sorting by short block-moves, and verifies its practicability by a set of test data.