Web server incorporating various genome rearrangement operations

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.