Turn Improvements Of The Sort And Block Exchange Sort Algorithm

As early as 60s in the last century, Dobzhansky and Sturtevant published an important paper, in which they proved that the gene sequences of the chromosomes of Drosophilia pseudoobscura and Miranda can be transformed from one into the other by 17 reversals. Later studies showed that the rearrangement of gene sequence is an important mode in the process of evolution of micro organisms, plants and animals. These studies formed a branch of bioinformatics (also called computational biology) — genome rearrangement.The genetic information is recorded by chromosomes of the species. A chromosome is composed of a serial of genes with different genes determining different characteristics of the species, and a genome is a set of chromosomes. In 1980's, the evidence has been found that different species have nearly the same set of genes just with different gene orders. The kindred and evolution relationship between different species can be unveiled by comparing their gene sequence. The process of evolution is also a process of rearrangement of the genes, which is a complex process. However, this problem can be simplified by only considering several rearranging operations, such as reversal, translocation, transposition and block-interchange, etc.The problems of genome rearrangement can be considered as genome sorting problems, i.e. given two gene sequences A and B and an available operation set, computing the minimum transformation sequence to transform A into B using the operations available. A large body of work has been devoted to this area in the last decade. One of the most important methods is the utilization of break point graph, also called cycle graph, which leads to many theoretical results as well as practical algorithms. For example, the problem of sorting unsigned permutation by reversals is NP-hard, while sorting signed permutation by reversals has a quadratic deterministic algorithm.This paper mainly studied sorting by transpositions and sorting by block-interchanges. The former one is more difficult. Which complexity class it...