基因组重组问题是计算生物学中的常见问题，基因组重组算法对分子生物学中生物进化的研究具有重要意义。早在六十年前，Dobzhansky和Sturtevant发表了一篇重要论文，证明了两种不同物种Drosophilia pseudoobscura和Miranda的染色体基因序列可以通过基因组的17次反转操作相互转换。 染色体由基因组成，基因组是染色体组成的集合。基因组重组是微生物、植物、动物进化的一种重要模式。虽然基因组重组过程非常复杂，但根据基因重新排列的方式最终可将其归结为几种基本操作。其中，变异过程中的主要操作为：反转(reversal)、移位(translocation)和转位(transposition)。移位是哺乳动物进化过程中最常见的基因组重组操作之一。移位操作将基因组中的两条染色体各自断为两段并相互交换其中的一段，形成两条新的染色体。基因组排序问题可描述为：给定两个基因组，计算出从一个基因组转化到另外一个基因组所需操作的最少次数以及对应的最短重组序列。 本论文主要讨论基因组的移位排序算法及其实现过程。对于该问题，Kececioglu与Ravi首先给出近似性能比为2的多项式时间近似算法，并进一步给出近似性能比为3／2的移位与反转同时存在的计算重组距离的近似算法，最终在1996年由Hannenhalli给出复杂度为O(n~3)的移位排序的多项式算法。在此基础上，2001年，朱大铭、马绍汉将其复杂度降为O(n~2logn)。2005年，王鲁生、朱大铭又进一步将其复杂度降到了O(n~2)，这也是目前世界上最快的移位排序算法。本文对该问题的研究，首先发现了原有算法中存在的错误。原有的移位排序算法中均未考虑可行灰边会产生偶隔离带的情况。如果移位排序过程中出现这种情况，根据原有算法计算会得到错误的移位序列。本文给出了这种情况的实例，并设计新算法修正了这一错误。另外，在修正算法的基础上，设计了详细的数据结构和实现方法，对复杂度分别为O(n~3)、O(n~2logn)和O(n~2)的三个移位排序多项式时间算法分别进行了实现和验证。并用其中效率最高的复杂度为O(n~2)的算法实现与前人的移位排序程序进行了对比。在输入长度为100，000个基因的情