An improved heuristic algorithm for sorting genomes with inverted block-interchanges

A classic problem in comparative genomics is finding sequence of evolutionary operations that transform one genome into another. Analysis of genome evolving by different types of genome rearrangement operators such as reversals, transpositions, translocations, block interchange, double cut and join(DCJ) etc. leads to a shortest sequence of different types of operations that sorts one genome into another. In this paper we consider reversals and block-interchanges simultaneously and incorporate inverted block-interchange, which inverts one or both of two swapped segments of a block-interchange. Experimental results show that using inverted block-interchange, previous heuristic algorithm finds better or equal sorting sequence.