比较基因组学是生物信息学的一个重要研究分支,计算两个基因组的量化距离是比较基因组学的基本问题,应用于构建进化树、探索基因功能、分析疾病致病原理等实践中。基因组是一个染色体集合,染色体为一个基因序列,每个基因表示为一个整数。基因组分有向和无向两种数据形式,每个基因相对所在染色体中的相邻基因,均有两个方向,在有向基因组中,采用“+”和“-”分别表示-个基因的两个方向。基因组的重组揭示了基因组改变基因排列次序的行为,在基因组重组排序问题中表述为改变基因排列次序的操作,有翻转(Reversal)、移位(Translocation)、转位(Transposition)等基本形式。给定两个基因组A、B,基因组重组排序要求寻找将A转化为B的一组有序操作,最小化操作次数,将A转化为B的最小重组次数即为A与B的重组距离。沿着由简而繁的路线,人们讨论了多种形式的基因组重组排序问题,和它们的算法与复杂性。Bafna和Pevzner首先给出有向基因组翻转排序近似度为1.5的多项式算法,Hannenhalli和Pevzner设计出O(n5)时间精确算法,Kaplan、Shamir和Tarjan将算法时间复杂度改进为O(n2)。对于基因组的移位排序问题,Hannenhalli首次设计出O(n3)时间精确算法,朱大铭和马绍汉将该算法的时间复杂度改进为O(n2logn),王鲁生、朱大铭、刘晓文和马绍汉进一步将算法的时间复杂度改进为O(n2),李国君、亓兴勤、王骁力和朱滨海给出了计算移位距离的O(n)时间算法。对于基因组转位排序问题,Bafana与Pevzner最早给出近似度为1.5的O(n2)时间算法。Hartman和Shamir又给出近似度为1.5的更为简洁的近似算法。Elias和Hartman将近似度改进为1.375。最近Bulteau、Fertin和Rusu证明该问题是NP-hard问题。我们将包含多种操作形式的基因组重组排序称为基因组的复合重组排序问题。因复合重组排序更具一般性,所以显得更有应用价值。Walter、Dias和Meidanis给出基因组的翻转和转位排序近似度为2的近似算法。Gu、Peng和Sudborough给出了基因组的翻转、转位和反转位排序问题近似度为2的近似算法。Hartman和Sharan给出基因组的翻转和反转位排序问题近似度为1.5的近似算法。Hannenhalli和Pevzner设计出基因组的翻转和移位排序问题的多项式时间精确算法。尹晓和朱大铭给出这一问题的一个新多项式算法。尹晓和朱大铭于2010年设计出基因组的移位、分断和连接排序的精确算法,时间复杂性为O(n(?))。人们还发现在基因组的重组演化中,伴有插入与删除基因片段的动作,许多分子生物学实践需要人们在基因组中实施插入与删除基因片段的操作。亓兴勤、李国君、李曙光等首次讨论了有向基因组的移位和删除排序问题,他们给出了有向基因组移位和删除排序的多项式算法,近似度达到OPT+2, OPT为两个基因组的移位删除距离。另外,亓兴勤、李国君、李曙光等描述了基因组的移位、插入和删除排序问题,并给出了解决该问题的一个启发式算法。我们仍然讨论有向基因组的移位、插入与删除排序算法。问题的输入数据为两个有向基因组A和B,移位删除排序要求寻找将A转化为B的移位、删除操作序列,使移位、删除次数最小化；移位插入删除排序问题要求寻找将A转化为B的移位、插入、删除操作序列,使移位、插入、删除次数最小化。首先讨论有向基因组移位和删除排序问题的求解算法。仍然利用圈图表达两个基因组的基因排列次序差异。圈图中含有一种被称为极小子排列的特殊结构子图,其数目和相对位置是影响有向基因组移位删除距离的关键因素。可将圈图中的极小子排列和它们相邻关系表示为一个森林。我们进一步根据圈图中描述极小子排列的森林的不同结构特征,分34种情况分别给出了有向基因组移位删除距离的精确数值。亓兴勤等给出的移位删除距离含有基因数目、染色体条数、圈的数目、偶隔离带存在性和极小子排列奇偶性辅助参数、间接圈数目、间接极小子排列数目,共6个参数。我们重新观察了圈图结构性质,引入两个新的特征参数：不可消除间接极小子排列数和打破间接极小子排列的间接普通圈数后,把所有情况下最小的移位删除次数统一为移位删除距离计算公式。推导移位删除距离公式的过程,自然地给出基因组的移位删除精确算法。(第3章)有向基因组移位插入删除排序求解,可先利用移位删除算法构造一个中间基因组,然后将源基因组由插入操作得到中间基因组,再调用移位删除算法将中间基因组变换为目标基因组而完成。由有向基因组的移位删除距离公式,我们给出了有向基因组移位插入删除距离的计算公式。(第4章)继续讨论了包含副本染色体和副本基因的有向基因组翻转,移位,转位,块交换,分断,连接排序的求解方法。划分为删除副本、同尾化基因组、规范化基因组重组排序三个功能模块,得到基因组复合重组排序的一个实用计算软件。最后给出初步的实验结果。(第5章)本文创新点可以归纳如下：1).首次给出了基因组的移位和删除距离公式,并给出求解该距离值及对应重组序列的一个多项式时间精确算法。2).将有向基因组移位和删除排序的时间复杂度由O(n3)时间改进到O(n2)时间。3).首次给出了基因组的移位、插入和删除距离公式,同时给出有向基因组移位插入删除排序的一个新多项式时间精确算法。