Upper Bounds to Genome Rearrangement Problem using Prefix Transpositions

Abstract

A Genome rearrangement problem studies large-scale mutations on a set of DNAs newlinein living organisms. Various rearrangements like reversals, transpositions, translocations, newlinefissions, fusions, and combinations and different variations have been studied newlineextensively by computational biologists and computer scientists over the past four newlinedecades. From a mathematical point of view, a genome is represented by a permutation. newlineThe genome rearrangement problem is interpreted as a problem that transforms newlineone permutation into another in a minimum number of moves under certain newlineconstraints depending on the chosen rearrangements. Finding the minimum number newlineof moves is equivalent to sorting the permutation with the given rearrangement. A newlinetransposition is an operation on a permutation that moves a sublist of a permutation newlineto a different position in the same permutation. A Prefix Transposition, as the name newlinesuggests, is a transposition that moves a sublist which is a prefix of the permutation. newlineIn this thesis, we study prefix transpositions on permutations and present a better newlineupper bound for sorting permutations with prefix transpositions. A greedy algorithm newlinecalled the generalised sequence length algorithm is defined as an extension of the newlinesequence length algorithm where suitable alternate moves are also considered. This newlinealgorithm is used to sequentially improve the upper bound to nand#8722;log3.3 n and nand#8722;log3 n. newlineIn the latter part of the thesis, we defined the concept of a block. We used it along newlinewith the greedy moves of the generalised sequence length algorithm to get an upper newlinebound of n and#8722; log2 n to sort permutations by prefix transpositions. newline