Genome rearrangement operations on permutations and strings

Abstract

The problem of sorting by a genome rearrangement event asks for the minimum number of that event required to sort the elements of a given permutation. In this thesis, we study some variants of the rearrangement event called pre x and su x transreversal, pre x and su x block-interchange, and pre x and su x versions of transposition and reversal. A transreversal is an operation which reverses the rst block before exchanging two adjacent blocks in a permutation. A pre x (su x) transreversal always reverses and moves a pre x (su x) of the permutation to another location. Interestingly, we will apply transreversal not on permutations but on strings over an alphabet of xed size. We determine the upper bound for pre x and su x transreversals required to sort the binary and ternary strings, with polynomial time algorithms for these sorting problems. Then we focus on applying pre x block-interchanges on binary and ternary strings. A block-interchange operation exchanges two blocks of a permutation which are not necessarily adjacent and in a pre x block-interchange, one block is always the pre x of that permutation. We present the upper bounds to group and sort a given binary/ternary string. We also provide uppper bounds for a di erent version of block-interchange operation which we call `restricted pre x block-interchange'. When we apply restricted pre x block-interchange operations on binary strings, we observe that our obtained upper bound is better than that of other genome rearrangement operations to group fully normalized binary strings. Consequently, we provide a linear-time algorithm to solve the problem of grouping binary normalized strings by restricted pre x block-interchanges. We also provide a polynomial time algorithm to group normalized ternary strings. We provide a classi cation for ternary strings. Finally, we study the variations of transposition and reversal events which we call pre x and su x breakpoint removal by transposition and reversal operations, and present a new (2+ )-approximation algorithm for this problem. We propose a new su cient condition to improve approximation ratio for sorting an unsigned permutation using genome rearrangement events. We also present experimental results to support our analyses with a naive polynomial time algorithm which runs in O(n2), where n is the number of elements in the permutation. We observe from experimental results over both real genomic data and simulated genome (in silico) data that the approximation ratio of our algorithm is far better under the proposed conditions. We further present an improved implementation technique to reduce the running time of our proposed algorithm.