Approximation Algorithms For Sorting By Singleton Moves

In the 1980s,evidence was found that some species have essentially the same set of genes,but their gene order differs.Some biologists believe that these same genes are likely to come from the common ancestors of different species,and that genome rearrangements have occurred during evolution.In addition,the rearrangement of the genome can also lead to some diseases(such as Waardenburg syndrome).Therefore,in the past thirty years,the problem of genome rearrangement has attracted the interest of many biologists and computer scholars,and becomes one of the hot topics in comparative genomics.In 1992,David Sankoff et al.proposed the three basic operations of genome rearrangement,i.e.,reversals,transpositions and translocations.People are most interested in the minimum number of genome rearrangement operations that transform one genome into another,which is called the rearrangement distance between the two genomes.Each genome rearrangement operation corresponds to its own rearrangement distance.Now,finding the parsimonious sequence of rearrangement operations has become a typical optimization problem in the literature of combinatorial algorithms.Block move is a basic genome rearrangement operation.A block move moves one gene segment in the genome to another location.Equivalently,a block move swaps two adjacent genome segments in the genome.However,in the actual genome evolution process,there is scarcely movement of large segments,also it is unlikely that a segment is moved far away from its original location.Therefore,Heath et al.proposed the restricted block move operation,which requires the total length of two segments swapped is bounded.Among them,the most famous restricted block move operation is called short block move,which requires one of the two segments to be exchanged is of length 1,while the length of the other segment is at most 2.In this thesis,we generalize the short block move operation and propose a new restricted block move operation,called singleton move,which requires one of the two segments to be exchanged is of length 1,while the length of the other segment is bounded by some constant c,with c?3.We observe the exact sorting sequence of three special sub-permutations,following which,we present the lower bound of the singleton move sorting distance for any permutation.Then,we design a polynomial time approximation algorithm with an approximate ratio of(?).For the woven double-strip permutation,we devise an algorithm to recognize it in O(n2)time.Also,we designed a polynomial time approximation algorithm for sorting woven double-strip permutations by singleton move,which guarantees an approximate ratio of(?).