计算生物学是当今世界发展最为迅速、最热门的学科之一,计算生物学研究的成果影响着人类在生物进化、基因制药、基因治疗等领域的研究进展。生物学、化学、数学、计算机科学等各领域的专家学者都在参与着计算生物学的研究,并取得了一系列的进展和突破。　　 随着大尺度DNA绘图的出现,基因组排序问题在分子生物学和计算生物学中的地位越来越重要。生物学家通过对整个基因组测序或使用比较物理图谱得到基因次序,并用排列来表示基因组以便于分析不同物种的基因列。推导物种的进化史,一个比较有前途的方法是比较两个基因组中的基因排列顺序。20世纪80年代末,Jeffrey Palmer和同事在对比甘蓝与芜菁甘蓝的基因序列时发现,排列形成两种基因序列的分子几乎完全相同,只是分子在两种基因中的排列顺序不一致。这一发现和以后的一系列研究表明,两个相近的物种往往含有相同的基因集合,只是基因排列的顺序有所不同。在生物进化的过程中,最常见到的基因重排事件是翻转(Reversal),它指在一个染色体中发生的基因重排事件,和移位(Translocation),它指在不同的染色体间发生的基因重排事件。　　 本文就基因组移位.删除排序问题进行了研究,得到了一下两个主要结果:　　 (1)基于时间复杂度为O(n3)的基因组移位-删除算法进行了改进,通过改进其在不同情况下的树结构处理方式和采用的合并、分解操作以及采用时间复杂度更低的移位排序子程序,将该算法的时间复杂度将为O(n2)。　　 (2)受到基因组移位排序算法的启发,我们不在一开始便讨论基因组移位-删除排序中所遇到的各种情况,而是在执行完所有可行性移位之后,对剩余的最小子排列进行归类分析。这样,既可以使讨论的情况更加简单,更具有代表性,又可以给出一个通用的、处理各种复杂情况的处理办法。最终设计出了一种移位-删除排序问题的快速处理算法。