Transposition

Transpositions are large-scale mutational events that occur when a block of genes moves from a region of a chromosome to another region within the same chromosome. The transposition distance problem is the minimum number of transpositions required to transform one genome into another. Recently, Bulteau, Fertin and Rusu proved that finding the transposition distance is a NP-Hard problem. Some approximation algorithm for this problem have been presented to date. Here we focus on developing heuristics to provide an improved approximated solution. Our approach outperforms other algorithms on small sized permutations. Our algorithm keeps the good performance on longer permutations.