计算生物学是现今世界的热门学科，计算生物学研究的有关成果直接影响着人类在生物进化、基因制药等领域的研究进展。生物学、化学、数学、计算机科学等各领域专家学者都在关注着计算生物学的发展。 20世纪80年代末，Jeffrey Palmer及其同事在对比甘蓝与芜菁甘蓝的基因序列时发现，排列形成两种基因序列的分子几乎完全相同，只是这些分子在两种基因中的排列顺序不一样．这一发现以及其后的研究表明，基因重组是生物演化过程中的一个基本特征，是微生物、植物、动物进化的一种重要模式．自此以后，与基因重组有关的技术与理论研究成为计算生物学研究中的一个热点，其在生物种族进化研究、生物分类学研究、生物制药研究等研究领域中显示出重要的研究价值。 一条染色体由一个基因序列组成，一个基因组是染色体的集合。显然，染色体可以看作是由单条染色体构成的基因组。基因序列可以呈线状(1inear)或环状(circular)分布。若基因序列中每个基因的方向是已知的，则称此序列是带符号的(signed)，否则称为无符号的(unsigned)。同理可定义带符号的基因组和无符号的基因组。虽然基因组的重组过程十分复杂，但是只存在几种基本的操作。在变异的过程中，这几种变换为；反转(reversal)，移位(translocation)和对换(transposition)。生物物种之间的进化实际上就是生物基因的变异过程。生物之间的进化关系可以通过基因组之间的变换来描述。给定两个基因组Ⅱ和г，在规定了可以使用的变换的集合之后，寻找从Ⅱ到г的最短的变换序列的问题称为基因组重组排序问题。一般情况下，基因组重组排序问题可以进行以下的简化：即假设基因组中不存在重复的基因。在这一简化下，对于一个含有n个基因的基因组，我们通常用一个定义在{1，2…，n}上的排列(n-排列)来表示。若此基因组含有多个染色体，这个n-排列将被分成多个连续的“块”，其中每个块表示一个染色体。 基因组的重组排序问题在近几年得到了广泛的研究，已有大量的结果。对应的三种不同的操作的排序问题难度有所不同。反转操作是将一个基因序列的一个子序列的顺序反转过来，对带符号的基因序列则同时改变子序列中每个基因的符号。带符号基因序列的反转排序问题已证明有多项式时间算法[21]，后人则努力降低算法运行的时间[22，23，24]，目前最快的算法可在(二)(n平方根nlogn)时间内完成[24]。而无符号基因序列的反转排序问题已证明是NP-hard的[19]。Christie[17]给出了此问题的一个1。5-近似算法，目前该问题最好的近似算法是P.Berman等人给出的1.375-近似算法[18]．移位操作是将两个基因序列分别在某处断开，再将分属两个基因序列的子序列重新连接起来，形成两个新的基因序列。带符号基因组的移位排序问题有多项式时间算法[33，35，36]。无符号基因组的移位排序问题的复杂性一直以来都没有得到解决，直到最近朱大铭和王鲁生证明此问题也是NP-hard的[38]，目前该问题最好的近似比是1.75[40]．对换操作是将一个基因序列中的两段相邻的子序列交换位置。对于对换排序问题，已有多个1.5-近似算法[28，29，31]，此问题目前最好的近似比为1.375[32]，但它的复杂性仍然未知。本文主要对以下三个与基因组重组排序有关的问题进行了研究： (1)带符号基因序列的固定长度的反转排序问题。 (2)无符号基因序列的赋权对换排序问题． (3)带符号基因组的移位、删除(或移位、插入)排序问题。 下面我们逐一说明这些问题并列出我们的主要成果。带符号基因序列的固定长度的反转排序问题“传统”的反转排序问题在排序过程中允许任何长度的反转，与之对应的就是反转排序的“限制”模型，即只允许满足一定条件的反转。在1996年，Chen和Skiena[42]将这种条件定义为“长度为后”，即在反转过程中只允许长度正好为k的反转(记为k-反转)，研究了对无符号的长度为n的排列(记为n-排列)进行排序的问题。实际上，并不是所有的n-排列都可以被k-反转调整为(1，2，3，…,n)，相反的，若仅通过k-反转，某个n-排列可能永远不会被调整为另一个n-排列．例如，以(1，3，2)开头的所有的n-排列(1，3，2，…)不可能通过3-反转调整为(1，2，3，…，n)，因为3-反转总是交换具有相同奇偶性的位置上的元素。若两个n-排列可以通过k-反转相互得到，则我们称他们在k-反转下属于同一个等价类。在[42]中，Chen和Skiena对所有无符号的n-排列(线状或环状)被k-反转划分的等价类进行了详细的刻画。并且，他们提出了下面的open问题：带符号的n-排列在k-反转下的等价类是什么样的? 的确，因为带符号基因序列上的反转不仅改变基因的顺序，而且要改变基因的符号，这使得此问题变得很困难。例如，带符号的n-排列(+1，+3，+2，+4，．．．，+n)不可能通过2-反转变换为(+1，+2，+3，+4，．．．，+n)，但当不考虑他们的符号时，是可以的。在第二章中，当k是偶数的时候，我们解决了这个历时10年的问题．对带符号的n-排列(线状或环状)在k-反转下的等价类进行了详细的刻画．主要结果可见下表，其中N<,1>(k，n)表示所有带符号的n-线状排列在k-反转下的等价类的个数，N<,c>(k，n)表示所有带符号的n-环状排列在k-反转下的等价类的个数． 当k是奇数的时候，此问题仍然没有得到解决，值得我们进一步的研究。无符号基因序列的赋权对换排序问题 以往对基因序列的对换排序问题或者反转排序问题的研究都基于这样的假设：每步操作的消费是单位费用1，而与操作的长度(即其作用的片断的长度)无关．这样的假设，在生物学上并不完全具有实际意义．实验表明，操作的长度在进化过程中扮演了重要的角色，某种操作发生的概率依赖于其作用的片断的长度．自然的，人们开始将操作的长度考虑在内，将操作的费用定义为是它的长度的函数，而一个操作序列的费用则是序列中所有操作的费用之和。赋权的反转排序问题就是求将序列Ⅱ变成г的费用最小的反转序列，此问题在[44，45，46]中已有深入研究。 受赋权反转排序问题的启发，在第三章我们考虑赋权的对换排序问题。这是首次对对换排序问题考虑赋权模型．我们考虑了一类消费函数，即f(ι)=ι<α>，这里α≥0，ι表示对换的长度。对不同的α值，我们分别给出了相应的足够将任何0/1序列调整为0…01…1或者将任何n．排列调整为(1，2，．．．，n)的最小费用的上下界。当0≤α<1，α=1和1<α<2时，我们给出了相应的赋权对换排序问题的近似算法；当α≥2时，我们证明Bubble sort是此问题的O(n<2>)精确算法。我们的结果归纳在下表，其中佗表示序列的长度。 对换的赋权模型使人们更深入的了解对换在基因重组过程中如何发挥作用。带符号基因组的移位、删除(或移位、插人)排序问题基因组移位距离是多条基因序列组成的基因组(源基因组)通过移位操作变换为另一个基因组(目标基因组)所需的最少的变换次数，它是揭示生物种族之间亲缘关系疏密程度的一个重要指标．该指标对生物种族进化研究具有重要意义。带符号基因组间移位排序问题的多项式时间算法首先由Hannenhalli给出[33]，但遗憾的是，Hannenhalli给出的这个算法，调整策略上存在着错误．在2005年，AnneBergeron等人[36]重新研究丁这个问题，并给出了一个正确的移位排序算法。 值得注意的是，一个基因组若可以仅通过移位操作变换为另一个基因组，那么这两个基因组首先必须有相同的基因集合。即移位排序算法“工作”的前提是输入的基因组有相同的基因集合。但在生物学实际中，这种情况非常少见。所以我们需要考虑一般的情形：即当两个基因组含有不同的基因集合时。很明显，在这种情况下，“插入”或“删除”将成为必需的操作。我们的目标仍然是通过最少的操作(移位、插入或删除)，将源基因组Ⅱ变换为目标基因组D。 将在Ⅱ和D中都出现的基因集合记作A，将只出现在Ⅱ中和只出现在D中的基因集合分别记作AⅡ和AD．我们假设A中的基因在Ⅱ和r中都只出现一次。在第四章，我们将考虑如何推广移位排序问题的多项式时间算法，使之能够处理含有不同基因集合的基因组Ⅱ和r。当An≠θ，Ar=θ时，我们给出了此问题的一个渐进最优的近似算法。由此算法得到的操作(移位、删除)序列的长度至多为OPT+2，这里OPT是将基因组Ⅱ变换为D所需的最少的操作(移位、删除)的个数．并且，只需将Ⅱ和r的角色互换，此算法也可用来处理当A<,Ⅱ>=θ，Ar≠θ时的情形(即通过最少的移位和插入将Ⅱ变换为r)。 本文的主要结果和创新点归纳如下： (1)部分解决了1996年Chen和Skiena提出的open问题。当k是偶数时，对带符号的n－排列(线状或环状)在к－反转下的等价类进行了详细的刻画。 (2) 首次提出了对换排序的赋权模型。考虑了一类消费函数：f(l)＝l,<α>，这里α≥0，l表示对换的长度，对不同的α值，分别给出了足够调整任何排列或任何0/1序 列的最小费用的上下界；同时对不同的α值，给出相应的赋权对换排序问题的 近似或精确算法。赋权模型的建立，为更好的了解对换在基因进化过程中发挥 的作用提供了一个新的思路。 (3) 首次考虑了当“源”基因组和“目标”基因组包含不同的基因集合时的移位排序 问题。特别的，当“目标”基因组的基因集合是“源”基因组集合的子集(或者反 之)时，我们给出了一个渐进最优的近似算法，由此算法可得到一个将“源”基因组调整为“目标”基因组的移位、删除(或者移位、插入)序列，且此序列 的长度与最优序列的长度之差不超过2。