利用遗传信息解答人们关于生命的困惑是人类与自然界共存并与自然界作斗争的重要挑战,利用遗传信息探寻生命规律的每一步都离不开“计算”,因此计算生物学成为近20年来十分活跃的学科。基因组重组是计算生物学的一个重要研究领域。20世纪30年代末,Dobzhansky和Sturtevant证明了两个不同物种Drosophilia pseudoobscura和Miranda的基因组可以通过17次反转相互转换,从而给出了基因组重组存在的有力证据。随后的许多研究表明,基因组重组是生物进化的一种普遍模式,也是微生物、植物、动物呈现多样性的主要原因之一。一条染色体是一个基因序列,基因组是一组染色体的集合。用一个整数表示一个基因。每个基因都有方向。若基因的方向是已知的,在表示基因的整数前增加一个符号(“+”或“-”)表示基因的相对方向。若基因的方向是未知的,则整数前不带符号。有些物种的基因组只包含单条染色体,而高级物种的基因组则由多条染色体构成。若一个基因组(或染色体)中的基因用有符号整数表示,则称这个基因组(或染色体)是有向的或有符号的(Signed);否则,称之为无向的或无符号的(Unsigned)。虽然基因组的重组过程非常复杂,但可归为三种基本操作：反转(Reversal)、移位(Translocation)和转位(Transposition)。一次重组操作可将一个基因组转化为另一个新的基因组。生物物种的进化实际上就是通过各种重组操作将一个基因组转化为另一个基因组的过程。给定两个基因组A和B,基因组重组排序问题要求计算将A转化为B所需的最少重组操作次数以及相应的最短重组操作序列。A转化为B的最少重组操作次数称作A和B之间的重组距离。基于分子生物学的实验数据验证,重组距离是衡量生物种族之间亲缘关系的一个重要指标,对生物种族进化研究具有重要意义。基因组的重组排序问题在近几年得到了广泛的研究,产生了大量的研究成果。只考虑单一操作的排序问题是最基本的重组排序问题,如反转排序、移位排序、转位排序。反转将一条染色体中一段连续的基因序列倒置。有向基因组反转排序问题有多个多项式时间算法,目前最好的时间复杂度为O(n(?))。而无向基因组反转排序问题被证明为Np-hard。目前该问题最好的近似度是1.375。移位将两条染色体分别断开再重新连接,形成两条新的染色体。有向基因组移位排序问题被证明有多项式时间算法,后来又有多个改进算法,目前最好的时间复杂度为O(n(?))。无向基因组的移位排序问题被证明是Np-hard,目前该问题最好的近似度为1.5+ε。转位将一条染色体上两段相邻的基因序列交换位置。转位排序问题的复杂性仍然是未知的,该问题有多个1.5-近似算法。目前该问题最好的近似度是1.375。考虑两种或两种以上操作的组合操作排序的计算结果更为分子生物学研究所接受。其中,反转和移位排序是最自然的组合重组排序问题。Hannenhalli和Pevzner将有向基因组反转和移位排序问题归约到有向基因组反转排序问题,给出了该问题的多项式时间算法,时间复杂度为O(n4)。断点图是研究基因组重组排序算法的重要工具。已经证明,两个基因组的重组距离与断点图中特定的组合结构密切相关。本文主要对基因组重组排序的两个问题进行了研究：(1)有向基因组的一般移位排序问题。交互型移位和非交互型移位均为移位的特殊形式。移位排序问题要求计算从一个包含多条染色体的基因组转化为另一个基因组所需的最少移位次数以及相应的最短移位序列。有向基因组的移位排序问题已有多个多项式时间算法。值得注意的是,已有的移位排序算法都只考虑了交互型移位。一个基因组若仅通过交互型移位转化为另一个基因组,那么这两个基因组必须具有相同的尾基因集合。然而在生物学实际应用中,源基因组和目标基因组往往不包含相同的尾基因。可以认为,两个基因组包含不同的尾基因,是因非交互型移位形成的。因而我们需要考虑更一般的情况,即允许两个基因组包含不同的尾基因。显然,在这种情况下,非交互型移位是必需的操作。将交互型移位和非交互型移位统称为一般移位。Ozery-Flato首先提出了一般移位排序问题,并猜测该问题可以在多项式时间内解决。但一直没有人给出该问题的算法和复杂性研究结果。在第三章和第四章,主要讨论如何推广交互型移位排序的多项式时间算法,使之能够处理包含不同尾基因集合的基因组。本文提出了给源基因组和目标基因组分别添加元素使之包含相同的尾基因,从而用交互型移位排序模拟一般移位排序的思想。根据该思想,可得到一个指数时间算法。为了改进算法的时间复杂度,本文进一步提出用添加元素后的同尾基因组的断点图构造部分图的方法,从而将问题转化为如何在部分图中添加灰边得到断点图,令其交互型移位距离最小。在第三章,给出了一般移位排序的OPT+2-近似算法,这里OPT是将源基因组转化为目标基因组所需的最少一般移位的次数。断点图中圈和最小子排列的数目是交互型移位距离公式中的重要参数。在该算法的设计中,通过讨论部分图中可能导致增加最小子排列的组合结构,给出一种在部分图中添加灰边的方法,可令添加灰边后的断点图的圈数尽可能多,最小子排列数尽可能少,从而使圈数和最小子排列数之差达到最大值。在第四章,给出了一般移位距离的精确计算公式以及一般移位排序的多项式精确算法。证明一般移位距离精确值的关键在于对交互型移位距离公式中的参数f的讨论。因为f的取值与最小子排列数的奇偶性以及是否构成偶隔离带有关,因而是精确计算一般移位距离的一个难点。在该算法的设计中,通过进一步研究部分图的性质,发现了四种可能导致偶隔离带的组合结构。根据这四种结构定义了新的参数,从而证明了一般移位距离的一个精确下界。最后给出一种往部分图中添加灰边的方法,使添加灰边后的断点图的交互型移位距离可以达到这个下界。(2)有向基因组的反转和移位排序问题。Hannenhalli曾通过将该问题归约到有向基因组反转排序问题,给出该问题的一个多项式时间算法。算法中将源基因组的多条染色体连接为一个排列,用排列上的一个反转模拟原来基因组上的一个内反转或交互型移位。由于该算法中每个反转或移位都是由一个反转来模拟的,因而在排序过程中不能将反转和移位区分开。Ozery-Flato曾在论文中提到,能在排序时明确区分反转和移位这两种操作的多项式算法,比Hannenhalli的算法更加自然和实用。在第五章,给出了可在排序时区分反转和移位这两种操作的新的多项式算法,从而对Ozery-Flato提出的问题给予了肯定的回答。断点图中结的数目是影响反转和移位距离的重要参数。若断点图中不包含结,则可利用已有的反转排序和移位排序的理论在多项式时间内求解该问题。因而,算法设计的关键在于如何找一个合理的反转和移位序列消除断点图中所有的结。本文的创新点可归纳如下：(1)首次考虑了当源基因组和目标基因组包含不同尾基因集合的一般移位排序问题,设计了一个OPT+2-近似算法。由该算法可得到一个将源基因组调整为目标基因组的一般移位序列,且此序列的长度与最优序列的长度之差不超过2。(2)首次给出了有向基因组一般移位距离的计算公式以及一般移位排序的多项式时间精确算法。证实了Ozery-Flato关于该问题可以多项式时间解决的猜测。(3)首次给出了能在排序时明确区分反转和移位这两种操作的有向基因组反转和移位排序的多项式时间算法。