Abstract:
A vintage problem in comparative genomics is to find the minimum running time and the
shortest sequence of evolutionary operations that transform one genome into another. There
exists different genome rearrangement operators such as reversals, transpositions, prefix
transpositions, double cut and join (DCJ) etc. In this thesis we incorporate reversals with
transpositions to achieve less number of operations than only reversal operation. We also
apply reversal operation with meta heuristics approach to find optimal solution. Besides,
we consider prefix transposition using permutation tree to obtain better running time. Experimental
results confirm that incorporation of reversal with transposition is successful to
acquire less number of operations than only reversal. Moreover, the application of meta
heuristics on reversal operation provides possible optimal solution. Thus, this application
of meta heuristics on reversal operation is a new addition in the era of genome rearrangement.
Also, use of permutation tree in prefix transposition achieves minimum running time
of O(nlogn) and proves to be a successful approach. Furthermore, we develop a web tool
named GRIMM-Ex where we incorporate reversal, reversal with transposition, prefix transposition
without permutation tree, prefix transposition with permutation tree and reversal
operation using meta heuristics approach. Additionally, we perform comparative analysis
among these genome rearrangement operators using our web tool.
