Sorting Permutations By 2, 4-reversals

In this thesis, we mainly study sorting permutations by 2, 4-reversals. The thesis consists of three chapters.In chapter 1, we give a brief introduction to the background of computational biology and the corresponding basic knowledge. In this chapter, we introduce the basic concept of sequencing DNA chains, assembling them and genome mapping, then we summarize the results of them.In chapter 2, we study sorting permutations by 2, 4-reversals. In the first section, we give a particular introduction to sorting permutations and 2, 4-reversals and summarize some results. In the second section, we show how 2, 4-reversals work through sorting n, n -1, …, 1. In the third section, we sort particular permutation B by 2, 4-reversals. Let π(1)π(2)…π(n) be an arbitrary permutation of 1, 2, …,N. Let B = {π ∈ S_n | for all 1 ≤ i ≤ [n/2] , for all [n/2] +1 ≤ j ≤ n satisfies π(i) > π(j)} In the fourth section, we sort general permutation by 2, 4-reversals.