基因组重组,包含了移位、转位、翻转等基本操作,造成了基因组上基因排列顺序的变换。基因重组排序问题是生物信息学中的经典问题之一,即探索不同基因组序列之间的重组过程并计算其最少重组次数。最少重组次数就意味着通过最少的基因重组操作完成两个基因组的相互转化,这对于推断物种的演化过程,获得物种间关系有重要意义。基因组重组排序问题的研究开始于20世纪90年代。1993年,Sankoff等人首次定义了基因翻转排序问题,并且提出了一个解决翻转排序问题的贪心算法。1997年,Capara将最大欧拉圈分解问题规约到无向基因组的翻转排序问题,从而证明了无向基因组的翻转排序问题是NP-hard的。2001年,Bader设计了一个可以获得翻转后基因序列,并计算翻转距离的算法。在2015年,Shao等人提出了一个运行时间更短的能够测算模拟基因序列的断点距离的算法,之后一年,他们又将算法应用到了有重复基因的模拟基因组数据之上。2018年,Zhai等人为带重复基因的基因组翻转排序问题设计了一个近似性能比为4的近似算法。但是,之前有关基因组重组的研究大都停留在理论或者模拟数据上,并不能通过重组排序的操作分析真实基因组上各个染色体之间的潜在关系。并且,之前重组排序的研究很少涉及到重复片段序列上,从而探索染色体上重复片段的关系。重复片段作为基因组中发生基因重组和基因突变的热点区域,研究重复片段中的基因组重组操作对探索基因组进化历程具有重要意义。随着测序技术的提高,目前很多大型基因组中的重复片段信息都已经被检测并公开。本文的研究将基因组重组模型扩展至真实基因组数据的重复片段序列上,研究不同基因组的重复片段之间的重组过程,进而分析物种间的进化距离。本文利用最新重复片段检测算法SDquest识别出不同基因组之间共有的重复片段信息,并设计合理的算法计算两个基因组重复片段序列间的重组操作过程以及次数。本文的研究目标是通过尽可能少的基因组重组操作,消除两条序列之间的所有断点。本文用人类与猩猩真实基因组数据进行实验,分析可能影响种族关系的对应染色体。本文给出的实现过程如下所示:(1)将SDquest的识别结果对重复片段进行编号,从而将染色体序列建模成重复片段序列。并且引入了邻接块的概念,对序列进行分块,减少重组操作过程中破坏的邻接。(2)设计了一个利用贪心策略的删除算法,通过比较位置得分,删除数量不对称的重复片段;将两条序列邻接块分成同位置匹配、异位置匹配和特殊情况(插入),并设计了一个翻转算法,消除序列之间的所有断点,同时记录重组的过程。(3)将人类和猩猩最新染色体数据进行分组实验,并对结果的重组操作次数进行统计与分析。本文的主要创新点:1.设计并且实现一个基于贪婪策略的删除算法,以删除人类与猩猩染色体中不对称的重复片段信息。2.实现近似性能比为4的翻转排序算法,消除两个基因组重复片段序列的所有断点,匹配两条序列间的所有邻接。3.将重组排序问题扩展到人类和猩猩基因组的重复片段上,设计合理的重组排序模型,并利用重组排序算法计算人与猩猩基因组中重复片段的重排次数,以此来近似估计物种间的进化距离。