A new upper bound for sorting permutations with prefix transpositions
Abstract
Permutations are discrete structures that naturally model a genome where every gene occurs exactly once. In a permutation over the given alphabet Σ, each symbol of Σ appears exactly once. A transposition operation on a given permutation π exchanges two adjacent sublists of π. If one of these sublists is restricted to be a prefix then one obtains a prefix transposition. The symmetric group of permutations with n symbols derived from the alphabet Σ={0,1,2,…,(n−1)} is denoted by Sn. The symmetric prefix transposition distance between π⋆∈Sn and π#∈Sn is the minimum number of prefix transpositions that are needed to transform π⋆ into π#. It is known that transforming an arbitrary π⋆∈Sn into an arbitrary π#∈Sn is equivalent to sorting some π′∈Sn. Thus, upper bound for transforming any π⋆∈Sn into any π#∈Sn with prefix transpositions is simply the upper bound to sort any permutation π∈Sn. The current upper bound is n−log(72)n for prefix transposition distance over Sn. In this paper, we improve the same to n−log3n.
