基因重组是生物进化的重要方式,如果对每个基因,用一个有符号的整数代替,则对基因重组的研究就演变为对排序算法的研究.用排序算法模拟基因组的重组时,在模拟和生物学数据上得到了令人惊异的准确结果.因此,基因重组算法的研究是对分子生物学中研究生物进化有重要的意义.本文讨论了基因重组问题中的2个问题——有符号排列的反转排序问题(Sort Signed Permutation By Reversals)和移位排序问题(Sort By Translocations).这两个问题分别是对于单条染色体基因重组和染色体组基因重组的模拟.有符号排列的反转排序问题.将单条染色体用有符号整数表示,从而使染色体通过反转变异的分子生物学问题演变为研究有符号整数排列通过反转排序的计算机算法问题.该问题目前对于计算反转距离,有时间复杂度为O(n<2>)的算法,对计算反转步骤,有时间复杂度为O(n)的算法.本文对于该问题的研究,主要是总结,验证了前人的研究成果,提出了经过优化的算法实现和数据结构,对算法进行了实验.实验结果显示,本文的算法实现比对照算法实现快7-10倍,并且将可计算的输入长度改进为仅受限于计算机硬件条件.移位排序问题.将含有多条染色体的染色体组用几组有符号整数的排列表示,从而模拟了染色体组通过移位变异的分子生物学问题.该问题目前的研究成果,对于计算移位距离,有时间复杂度为O(n<2>)的算法,对计算移位步骤,其算法的时间复杂度为O(n<2>logn).本文总结了前人的研究成果,并对计算移位距离的问题进行了深入的研究,大大改进了其时间复杂度,提出一个计算移位距离的时间复杂度为O(n)的算法.然后,设计了数据结构,提出了算法的实现,取得了实验数据,验证了算法.本文的算法实现,在计算50000个基因的移位排序时,用时为30秒.本文的研究,1)总结并详细叙述了有符号排列的反转排序问题的算法前人研究中的错误,予以更正,并给出了优化的实现方法;2)改进了有符号染色体组的移位排序问题算法,同样给出了高效的实现方法.本文的研究成果和实验数据,对于将其应用于实际工作具有重大的意义.