基因组重组,是基因组更改变换基因排列次序的行为,可形式化为翻转、移位、转位等基本操作。基因组重组,也是导致生命特征演化的典型结构变异行为。基因组重组排序,目的是找到最短的重组操作序列,将一个给定的基因组转化为另外一个基因组。这是推断生命演化过程,比较生命亲缘关系的组合优化问题模型。每个基因在基因组中仅限重复一次的基因组重组排序,已有广泛而深入的算法研究进展。Berman等给出的近似性能比为1.375的无向基因组的翻转排序算法,是当前最好的。Hannenhalli等对有向基因组序列构造断点图,并根据图中的特殊结构及其数量给出了翻转排序的多项式算法,Bader等人设计出计算翻转距离的时间复杂度为O(n)的算法,以及获取翻转之后新序列的时间复杂度为O(n2)的算法。对于有向基因组移位排序问题,Li等人给出了一个时间复杂度为O(n)的计算移位距离的算法;对于无向基因组移位排序,Cui等设计了时间复杂度为O(n2)、近似度为1.75的近似算法,目前Pu等给出的1.375近似算法,是解答该问题最好的算法。基因在基因组中通常会重复多次。然而目前针对允许基因重复多次的全基因组结构差异比较,还缺少有效的组合优化问题模型和算法。本文建立了一个组合优化问题模型,用于刻画两个基因重复基因组之间的重组距离。两个基因重复的基因组的翻转排序可描述为如下组合优化问题:给定一个源基因序列π和一个目标基因序列σ,两个基因序列的元素构成相同,目标是通过对基因序列进行一定次数的翻转操作,输出一个新的基因序列π’,消除基因序列π和σ之间的全部断点且满足操作的翻转次数最少。我们总将基因序列表示为一个字符序列,其中一个字符表示一个基因。本文给出两个解答基因重复基因组翻转排序问题的算法。(1)设计给出一个近似比为4、时间复杂度为O(n3)的翻转排序的近似算法。我们利用断点、邻接概念定义了基因序列中的块、同位置匹配块、和异位置匹配块。分类讨论执行不同的翻转操作对同位置匹配块和异位置匹配块的影响,对消除同位置匹配块和异位置匹配块以外的断点设计了特定的翻转操作。给出消除基因序列中所有断点的近似算法,并证明每两次翻转操作至少可以消除一个断点,从而证明算法近似性能比不超过4。(2)定义了表达两个基因重复基因组翻转距离的断点图。给出一个当断点图为无交叉图时,基因重复基因组翻转排序的精确算法。分析了无交叉图的三种简单结构,对无交叉图三种简单结构进行任意翻转操作并根据翻转子串的不同位置分类讨论,给出由无交叉图参数表达的翻转距离的上界。证明任意无交叉图可约减为简单结构的无交叉断点图。从而证明前面的翻转距离上界适用于任意无交叉断点图。我们设计的算法所得到的翻转距离恰好等于前面给出的上界,因此算法能够求到最优的基因重复基因组的翻转距离。本文的主要创新点:1.建立了含重复基因的基因组重组排序的问题模型,在此之前人们只对不含重复基因的基因组进行重组排序问题的相关研究。2.发现并定义了基因序列中的’块’,由此设计出一个近似性能比为4的翻转排序的近似算法。3.建立了表达两个含重复基因的基因组重组距离的断点图模型,给出无交叉断点图表达的基因组翻转排序的多项式精确算法,并证明其最优性。