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.
