早在上个世纪六十年代，Dobzhansky和Sturtevant发表了一篇重要的论文，其中证明了两个不同物种Drosophilia pseudoobscura和Miranda的染色体基因序列可以通过基因组的17次反转来进行相互转换。在之后的研究证明，基因组的重组是微生物，植物，动物进化的一种重要模式。对这种基因重组问题的研究形成了生物信息学，也称计算生物学中的一个分支——基因重组。 物种的遗传信息是由染色体记录的，一条染色体由一系列基因构成，不同的基因决定着物种不同的性状。一个基因组是由多条染色体构成。在上个世纪八十年代，人们发现不同物种有着基本上相同的基因，只不过这些基因的排列顺序有所不同。生物之间的亲缘和进化关系可以通过比较这些基因的排列顺序得到。生物的进化过程也就看作是一个基因的重组过程，虽然这个过程十分复杂，但是如果只考虑几种基本的操作，比如反转（reversal），移位（translocation），转位（transposition）和块交换（block-interchange）等，就可以简化问题。 基因重组的问题也可以看作是基因排序的问题，给定两个基因组A，B，在规定了可以使用的变换的集合之后，计算A，B之间的距离等价于寻找从A到B的最短变换序列。在过去十几年里，这个领域的问题得到了广泛的研究。其中很重要的一个研究方法就是断点图（break point graph），也称作圈图（cycle graph），的引入。利用这个研究方法，取得了很多理论结果和有用的算法。比如，人们证明无向的反转排序问题是NP—hard的，而有向的反转排序问题则有确定的多项式算法。 本文主要对转位排序问题和块交换排序问题进行研究。转位排序问题是相对比较难的问题，直到现在还不清楚其所属的复杂性类，很长一段时间以来的最好的研究结果都是近似度为1.5的算法，直到最近一个近似度为1.375的算法被提出来。虽然进展缓慢，但是研究该问题的理论不断得到简化，近似算法的时间复杂度也被不断降低。近似度为1.5的算法的最好时间复杂度的算法是由Hartman提出的，其时间复杂度为O(n^3/2(logn^1/2))。块交换比较简单，约十年前Christie就已经提出了时问复杂度为O（n²）的确定算法。