Publication

Abstract : In today’s rapidly evolving landscape, where genetic research and the optimization of computer networks hold immense importance, understanding genetic mutations and fine-tuning network performance are critical endeavors with profound impacts. Permutations serve as an essential tool in both genomic studies and computer networks, providing versatile methods for understanding genetic variations and enhancing network efficiency. Permutations are used in genomics to represent genomes, where the source genome is denoted by π1 and the target genome by π2. The genomic distance, also known as inter-species distance, quantifies the minimum modifications required to transform π1 into π2. Similarly, permutations are used in computer networks to represent nodes, often visualised through graphs like the Cayley graph, where the graph’s diameter determines the maximum delay between network nodes. Sorting permutation refers to the transformation of a permutation π to its form of identity I. Various operations such as adjacent swaps, block transpositions, prefix transpositions, and transposition trees can be applied for sorting permutations. This research particularly focuses on transposition trees. Sorting of permutations using transposition trees is an NP-hard problem in general. Although, there are effective algorithms that optimally sort certain types of transposition trees such as star, path and brooms, developing such algorithms for more general transposition trees remains a challenge. A notable structure is the balanced starburst, formed by connecting the centers of k stars (k > 2) to a common center vertex (c), for which optimal algorithms and upper bounds are yet unknown. In this paper, we explore the sorting of permutations with the balanced starburst transposition tree, aiming to establish an upper bound