Publication

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 nn symbols derived from the alphabet Σ={0,1,2,…,(n−1)}Σ={0,1,2,…,(n−1)} is denoted by SnSn. The symmetric prefix transposition distance between π⋆∈Snπ⋆∈Sn and π#∈Snπ#∈Sn is the minimum number of prefix transpositions that are needed to transform π⋆π⋆ into π#π#. It is known that transforming an arbitrary π⋆∈Snπ⋆∈Sn into an arbitrary π#∈Snπ#∈Sn is equivalent to sorting some π′∈Snπ′∈Sn. Thus, upper bound for transforming any π⋆∈Snπ⋆∈Sn into any π#∈Snπ#∈Sn with prefix transpositions is simply the upper bound to sort any permutation π∈Snπ∈Sn. The current upper bound is n−log(72)nn−log(72)n for prefix transposition distance over SnSn. In this paper, we improve the same to n−log3nn−log3n.