Faster Algorithms For Sorting By Short Block-moves

An organism is uniquely determined by its genomes,and genome rearrangement will occur in the process of biological evolution.Genome rearrangement refers to the process of changing the sequence or direction of genes,segments or chromosomes in the genome.This process can create new genes,change gene expression and regulation,and thus has a significant impact on biological evolution.With the development of genome sequencing,comparative genomics,cytogenetics and other technologies,genome rearrangement has been widely studied,and gene rearrangement operations have also been widely applied in biology,computer science,organic chemistry,preclinical medicine and other fields.In 1992,Sankoff et al.first proposed three basic genome rearrangement operations,namely,reversal,translocation and transposition.Transposition is also known as block-move and one block-move exchanges the positions of two adjacent genomic segments in the genome.In the actual process of genome evolution,a gene segment that breaks at its original location will mostly recombine with the genome at a location closer to its original location.Therefore,Heath and Vergara proposed the operation of short block-move.If the total length of two adjacent genome segments used to be exchanged in the block-move operation does not exceed 3,then such block-move operation is a short block-move operation.Therefore,the problem of sorting genomes by short block-moves is introduced,that is,using the least number of short block-move operations to transform one genome into the other.On the problem of sorting genomes by short block-moves,Heath and Vergara proposed an exact algorithm for woven double-strip permutation,which runs in O(n3 log n)time,and an approximate algorithm with an approximation ratio of 4/3 and the time complexity being O(n3)for general permutation.Firstly,in this paper,we proposes an algorithm that can recognize the woven double-strip permutation and divide the woven double-strip permutation into two increasing subpermutations,the time complexity of which is O(n).This algorithm provides data processing support for subsequent research on the problem of sorting genomes by short block-moves for the woven double-strip permutation.Then,on the problem of sorting genomes by short blockmoves for the woven double-strip permutation,we redesign the strategy of erasing inversions in permutation by using the tool of matching graph.For the woven double-strip permutation with perfect matching in the matching graph,we devise an exact algorithm,improving the time complexity from O(n3 log n)to O(n2)by use of the perfect matching of the matching graph;for the woven double-strip permutation without perfect matching in the matching graph,we devise an exact algorithm,improving the time complexity from O(n3 logn)to O(n2)by use of the maximum matching of the matching graph.Finally,on the problem of sorting genomes by short block-moves for general permutations,the idea of solving this problem is to convert the general permutation into the woven double-strip permutation by correcting hop,and then complete the whole sorting work by using the short block-move sorting algorithm for arbitrary woven double-strip permutation.Based on the above idea,we devise an approximation algorithm with an approximation ratio of 4/3,and the time complexity is improved from O(n3)to O(n2).