论文摘要
基因组重组,包含了移位、转位、翻转等基本操作,造成了基因组上基因排列顺序的变换。基因重组排序问题是生物信息学中的经典问题之一,即探索不同基因组序列之间的重组过程并计算其最少重组次数。最少重组次数就意味着通过最少的基因重组操作完成两个基因组的相互转化,这对于推断物种的演化过程,获得物种间关系有重要意义。基因组重组排序问题的研究开始于20世纪90年代。1993年,Sankoff等人首次定义了基因翻转排序问题,并且提出了一个解决翻转排序问题的贪心算法。1997年,Capara将最大欧拉圈分解问题规约到无向基因组的翻转排序问题,从而证明了无向基因组的翻转排序问题是NP-hard的。2001年,Bader设计了一个可以获得翻转后基因序列,并计算翻转距离的算法。在2015年,Shao等人提出了一个运行时间更短的能够测算模拟基因序列的断点距离的算法,之后一年,他们又将算法应用到了有重复基因的模拟基因组数据之上。2018年,Zhai等人为带重复基因的基因组翻转排序问题设计了一个近似性能比为4的近似算法。但是,之前有关基因组重组的研究大都停留在理论或者模拟数据上,并不能通过重组排序的操作分析真实基因组上各个染色体之间的潜在关系。并且,之前重组排序的研究很少涉及到重复片段序列上,从而探索染色体上重复片段的关系。重复片段作为基因组中发生基因重组和基因突变的热点区域,研究重复片段中的基因组重组操作对探索基因组进化历程具有重要意义。随着测序技术的提高,目前很多大型基因组中的重复片段信息都已经被检测并公开。本文的研究将基因组重组模型扩展至真实基因组数据的重复片段序列上,研究不同基因组的重复片段之间的重组过程,进而分析物种间的进化距离。本文利用最新重复片段检测算法SDquest识别出不同基因组之间共有的重复片段信息,并设计合理的算法计算两个基因组重复片段序列间的重组操作过程以及次数。本文的研究目标是通过尽可能少的基因组重组操作,消除两条序列之间的所有断点。本文用人类与猩猩真实基因组数据进行实验,分析可能影响种族关系的对应染色体。本文给出的实现过程如下所示:(1)将SDquest的识别结果对重复片段进行编号,从而将染色体序列建模成重复片段序列。并且引入了邻接块的概念,对序列进行分块,减少重组操作过程中破坏的邻接。(2)设计了一个利用贪心策略的删除算法,通过比较位置得分,删除数量不对称的重复片段;将两条序列邻接块分成同位置匹配、异位置匹配和特殊情况(插入),并设计了一个翻转算法,消除序列之间的所有断点,同时记录重组的过程。(3)将人类和猩猩最新染色体数据进行分组实验,并对结果的重组操作次数进行统计与分析。本文的主要创新点:1.设计并且实现一个基于贪婪策略的删除算法,以删除人类与猩猩染色体中不对称的重复片段信息。2.实现近似性能比为4的翻转排序算法,消除两个基因组重复片段序列的所有断点,匹配两条序列间的所有邻接。3.将重组排序问题扩展到人类和猩猩基因组的重复片段上,设计合理的重组排序模型,并利用重组排序算法计算人与猩猩基因组中重复片段的重排次数,以此来近似估计物种间的进化距离。
论文目录
文章来源
类型: 硕士论文
作者: 王睿智
导师: 朱大铭
关键词: 重复片段,重组排序,邻接,断点
来源: 山东大学
年度: 2019
分类: 基础科学,信息科技
专业: 生物学,计算机软件及计算机应用
单位: 山东大学
分类号: Q811.4;TP301.6
总页数: 58
文件大小: 3087K
下载量: 60
相关论文文献
- [1].目标为最小化工件运输时间和的单台机器带一个维修时间段的排序问题的一个改进算法[J]. 运筹学学报 2019(04)
- [2].具有时间与位置相关的两类平行机排序问题[J]. 运筹学学报 2019(04)
- [3].基于Flexsim的零件加工排序仿真实现方法研究[J]. 新技术新工艺 2020(02)
- [4].总加权误工损失的两个代理单机排序问题[J]. 湖北民族学院学报(自然科学版) 2019(01)
- [5].机器带周期性维护时段的加工与运输协同排序问题[J]. 浙江理工大学学报(自然科学版) 2016(06)
- [6].带有运输且加工具有灵活性的无等待流水作业排序问题[J]. 运筹学学报 2016(04)
- [7].具有维护活动及公共工期的加工时间依赖资源的单机排序问题[J]. 沈阳航空航天大学学报 2016(06)
- [8].关于工期分配与加权误工数的双指标排序问题(英文)[J]. 工程数学学报 2017(01)
- [9].带有交货期窗口和加工时间可控的排序问题[J]. 沈阳师范大学学报(自然科学版) 2016(04)
- [10].具有学习效应和遗忘效应的单机排序问题研究[J]. 枣庄学院学报 2017(02)
- [11].资源定时投放的单机排序问题[J]. 杭州电子科技大学学报(自然科学版) 2017(02)
- [12].有公共交货期的单机分批排序问题(英文)[J]. 重庆师范大学学报(自然科学版) 2017(02)
- [13].在退化维修活动下具有多窗口及退化效应的单机排序问题[J]. 重庆师范大学学报(自然科学版) 2017(03)
- [14].一类资源费用可变的平行机排序问题[J]. 上海第二工业大学学报 2017(02)
- [15].数学规划与约束规划整合下的多目标分组排序问题研究[J]. 运筹学学报 2016(01)
- [16].具有学习效应的排序问题的某些新进展[J]. 沈阳师范大学学报(自然科学版) 2014(04)
- [17].有界平行批处理机的在线排序问题[J]. 河南师范大学学报(自然科学版) 2015(05)
- [18].集思[J]. 福建教育 2020(25)
- [19].高中数学一道数列典型题解法的探究[J]. 数学学习与研究 2016(23)
- [20].单机排序问题的研究[J]. 数学学习与研究 2017(24)
- [21].一个排序问题的解决[J]. 中等数学 2009(07)
- [22].具有多个制造商和分批配送的同类机排序问题[J]. 系统科学与数学 2019(09)
- [23].工件具有加工位置上限最小化加权总误工量的单机排序问题(英文)[J]. 运筹学学报 2020(02)
- [24].具有恶化效应与可控加工时间的工期指派排序问题研究[J]. 沈阳航空航天大学学报 2019(05)
- [25].优化交货期窗口的两阶段供应链排序问题[J]. 运筹学学报 2016(04)
- [26].具有公共流、退化效应与维护和资源分配的单机窗口排序问题[J]. 沈阳航空航天大学学报 2016(05)
- [27].关于总误工损失的两个代理单机排序问题[J]. 运筹学学报 2017(01)
- [28].具有不同生产时区费用的单机可拒绝排序问题[J]. 数学的实践与认识 2017(04)
- [29].具有柔性维护周期的单机误工排序问题[J]. 杭州电子科技大学学报(自然科学版) 2017(03)
- [30].带有多个工期窗口及退化维护的单机排序问题[J]. 重庆师范大学学报(自然科学版) 2017(03)