基因组重组是计算生物学和生物信息学的一个重要研究领域,许多研究表明,基因组重组是生物进化的一种普遍模式,也是植物、哺乳动物及细菌等呈现多样性的主要原因之一。1938年,Dobzhansky和Sturtevant开创了基因组重组的分子生物学分析,他们发表了里程碑式的论文,文中对果蝇基因组提出了含17次反转操作的重组方案。就最简单的形式而言,将一种基因组转换为另一种基因组的重组可以用寻找最小转换次数的组合问题来模拟。随着大规模作图和测序的出现,在不同的领域内有关基因组比较问题的数目迅速增长,这些领域包括病毒、细菌、酵母、植物和动物的进化。在20世纪80年代末,Jeffrey Palmer和他的同事们在植物细胞器中发现了一种有关进化变异不寻常的新的模式。他们比较了甘蓝和芜菁甘蓝的线粒体基因组,两者之间的联系非常紧密(许多基因是99%同源的)。令他们感到惊奇的是,这些分子在基因序列上几乎相同,但在基因排列次序上则有显著的差别。这个发现和后来十年中许多其他的研究令人信服地证明了基因组重组是分子进化的一种模式[49]。基因组是一组染色体的集合,一条染色体是一个基因序列,用一个整数序列来表示。每个基因都有方向。当每个基因的方向在一个有符号基因组中是已知时,用带符号的整数表示该基因组中的基因。当基因的方向在一个无符号基因组中都是未知时,用不带符号的整数表示该基因组中的基因。给定两个基因组,重组排序问题是要计算一个重组操作序列,将其中一个基因组转化为另一个基因组,并使得重组操作次数最少。对于有符号基因组的重组问题,重组操作在改变基因序列的同时也改变基因的符号；对于无符号基因组的重组排序问题,重组排序操作只改变基因序列,不会改变基因的符号。虽然基因组的重组过程十分复杂,但是只存在几种基本的操作：反转,移位和对换。通常情况下,基因组重组问题可以进行如下简化：即假设基因组中不存在重复的基因。在这一简化下,对于一个含有n个基因的基因组,我们通常用定义在{1,2,…,n}上的一个排列来表示。若一个基因组可以仅通过移位操作变换为另一个基因组,那么首先这两个基因组必须有相同的基因集合。但是在生物学实际中,这种情况非常少见。所以我们需要考虑一般的情形：即两个基因组含有不同的基因集合时的情况。显然,在这种情况下,“删除”或“插入”将成为必需的操作。我们的目标仍然是通过最少的重组操作(移位、删除或插入),将源基因组转化为目标基因组。大部分比较基因组学研究假设一条染色体中的基因的排列次序是给定的,但是目前的基因图谱技术,比如重组分析和物理成像等,经常由于缺乏解决的方法,使得基因图谱中几个基因位于同一个位置或者遗漏一些其它的基因,这就使得将它们结合起来仅能产生基因组的一个部分排序而不是全排序。本文主要研究部分排序的基因组重组问题。分四章进行讨论：在第一章中概述基因组重组排序的基本概念及算法。第二章主要研究部分排序基因组断点距离(PBD)问题,即给定两个含有相同基因集合的部分排序基因组Π和Γ,分别找到Π和Γ的一个可能的全序排列L(Π)和L(Γ),使得L(Π)和L(Γ)之间的断点距离db(Π,Γ)最小。在这一章中给出了计算两个部分排序基因组之间断点距离的一个O(n4)启发式算法,其中n为所考虑基因组中基因的个数。文中,我们首先引入了一个新的组合优化问题-最小双断点集问题(MDBVS),并且给出了该问题的一个2(m2+4m-3)-近似算法,其中m是分别构成两个部分排序的基因组所需要的最大基因图谱的个数,然后根据PBD问题和MDBVS问题之间的关系,设计了解决PBD问题的一个启发式算法。它们之间的关系由下面的定理给出：定理设|MDBVS|是最小的双断点集所含元素的个数,|W|是W中元素的个数,n表示Π中所含基因的个数。则db(Π,Γ)=n-1-|W|+|MDBVS|。由上述定理可以看出,如果|W|<n,其中W为我们在本章中定义的所有可能的共同邻接的集合,则由MDBVS问题的一个2(m2+4m-3)-近似算法可以很容易地得出PBD问题的一个2(m2+4m-3)-近似算法。在计算生物学中,如果一组同源基因(即有一个共同祖先的基因)在两个不同的物种中共同存在,则这些基因可能在共同的祖先那里是保持在一起的,并且在以后的进化过程中也不被分开。这样的一组结合在一起的同源基因称为公共区间[32]。因此,最近又出现了另外一个组合优化问题,称为完美排序问题,它是指寻找一组最少的重组操作,使得当由一个基因组转化为另一个基因组时,这些重组操作不破坏所考虑基因组的公共区间。在第三章中,我们推广了Berard等人[5]关于基因反转完美排序问题的一个算法,考虑允许有删除和限制条件的插入(即不允许有重复基因)操作的基因组完美重组问题。在第四章中,我们研究了含有不同基因集合的部分排序基因组重组问题,即给定两个含有不同基因集合的部分排序的基因组,分别找到它们的一个可能的全排序,使得从一个全排序到另外一个全排序所需要的重组操作次数最少。显然,在这种情况下,插入和删除将成为必须的操作。在这一章中,我们推广了zheng等人[70]的算法,设计了一个解决允许有删除和插入操作的部分排序基因组重组问题的算法,并且举例说明该算法的可行性。