The Distance Of Sorting Permutations By Short Block Moves And Fragment Assembly

With the research on the genome further and gradually deciphering, great changes have taken place in our life. Especially in the medical field, along with the people to the understanding of genome has reached a new stage, causes of many diseases are gradually revealed, which help the medical workers to work out drugs more scientifically and effectively. It make through gene therapy to treat some of the current medical means still incurable disease come true. Even through controlling some biochemical properties of human, we can achieve the aim that restoration or repair of human cells and organs function. Therefore we can even change the course of human evolution through the genome information operation. In the field of crops, people can control the genome toimprove the qualities of fruits and vegetables.We can expect that there will be more and more transgenic plants, animals and foods were published. In the new century, humans may cultivate more super crops. Thus it can be seen that technology develops so rapidlyin present, the genome research has become an very interesting field for many scientists.The computational biology rise in response to the proper time and conditions.Scientists analysis the related operations in the genome through mathematical modeling and computer simulation calculation methods, to deal with the data of genome and obtain biological information. The typical problems include computing the distance of genomic recombination、repeat classification and fragment assembly、using biological sequencing technology to gain the superfluous or missing information of genomic. But because of the greater numbers of genes and mutations, which lead to the similarity problem. Therefore most of the problems of computational biology are NP-hard, which requires scientists of computational biology spending more attention on designing the polynomial time approximation algorithms.This thesis mainly focuses on computing recombination distance of genome、repeat classification and fragment assembly.For the distance of sorting permutations by short block moves, we use the transposition. A transposition is also called a block-move. The short block-move is the most common case of block-moves. A short block-move is a block-move whose segments are moved from its original position at most two positions, so its another name is 3-bounded transposition. For the problem of the distance of sorting permutations by short block moves, we present an implicit lower bound. In this paper, we use a special permutation called "double increasing permutation" and gain a new lower bound through analyzing the double increasing permutation. On this basis, we analyse all the maximal double increasing sub-permutations of the original permutations, and then simply sum the lower bounds to obtain a new lower bound for the distance of sorting permutations by short block moves, which improves Health and Vergara’s result greatly, so that we will lay a foundation of the design of a better approximate algorithm.For therepeat classification and fragment assembly based on A-Bruijn graph, this thesis introduces the RepeatGlueralgorithm to solve a genomic sequence rearrangement in detail. At the same time, we explain some codes. We hope through the discussion and realization to find a better approach to resolve the problem of fragment assembly.