对于基因组的排序问题在近几年得到了广泛的研究.新的断点图的方法被发现并对算法的设计起了重要的作用.在这篇论文中,主要研究了基因组排序问题中三种不同操作的排序问题的算法,这三个问题的难度有所不同.反转操作是将一个基因序列的一个子序列的顺序反转过来.反转排序有O(n2)的多项式时间算法.转位操作是将一个基因序列中的两段相邻的子序列交换位置.转位问题现在只有近似比为3/2的近似算法.移位操作是将两个基因序列在中间断开,在将分属两个基因序列的子序列重新连接起来,形成两个新的基因序列.移位排序也有多项式时间算法.本文主要对于有向基因组移位排序问题进行了研究,对于有向染色体组移位排序问题,Kececioglu与Ravi首先给出近似性能比为2的多项式时间近似算法,Hannenhalli利用断点图的性质,证明了一个重要的二元定理,并由此证明了该问题有多项式时间算法.Hannenhalli于1996年给出的移位排序算法的时间复杂度为O(n<3>),2001年朱大铭,马绍汉将Hannenhalli算法的时间复杂度改进为O(n<2>logn).本文的主要成果和创新点如下:·给出了寻找断点图中所有最小子排列的O(n<2>)算法.·发现了断点图中的最右灰边并证明了其特殊性质.·给出了基于最右灰边的线性的无用顶点删除算法.·给出寻找有效合理移位的线性算法,并在此基础上,最终给出了基因组移位排序问题的O(n<2>)的快速算法,这也是目前为止,该问题的最好算法.本文本文的组织如下:第一章为背景介绍,第二章介绍有向染色体反转排序问题的多项式时间算法,第三章介绍染色体转位排序问题的3/2近似算法,第四章,讨论了染色体移位排序问题的二元定理的证明过程,以及以前的多项式时间的算法,并给出基因组移位排序问题的O(n<2>)的快速算法,第五章进行总结.