On Token Swapping in Labeled Tree

Abstract

Calculating the permutation distance, which is the number of steps needed to transform a permutation to another under a particular operation, is of great value in many areas like genetics, interconnection networks, game theory, robot motion planning etc. In genomics, a permutation can formally model a genome sequence and the list of nucleotide in any living organism. A biological mutation alters the nucleotide sequence from its initial state. Recombination, transposition and mutation are the three important processes that leads to these genomic changes. Computation of evolutionary distance between two genomes by considering genome rearrangements is need of the hour. Many operations have been studied to transform the permutations, among which transposition trees are widely discussed. Transforming any permutation <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\Pi\in S_{n}$</tex> into <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\Pi^{\prime}\in S_{n}$</tex> is equivalent to sorting some <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\Pi^{\ast}=((\Pi^{\prime})^{-1})\Pi\in S_{n}$</tex> . Therefore, finding the bound for sorting permutations has many practical applications. Researchers have attempted to provide upper and lower bound limits for sorting permutations under various operations. The first part of the paper discusses about the upper bound for sorting permutations using transposition trees and the second part is about the lower bound for sorting permutations on various trees.