基因组比较分析的算法与软件

发布时间：2020-08-15 14:33

【摘要】：基因组重组,包含了移位、转位、翻转等基本操作,造成了基因组上基因排列顺序的变换。基因重组排序问题是生物信息学中的经典问题之一,即探索不同基因组序列之间的重组过程并计算其最少重组次数。最少重组次数就意味着通过最少的基因重组操作完成两个基因组的相互转化,这对于推断物种的演化过程,获得物种间关系有重要意义。基因组重组排序问题的研究开始于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
【图文】：

基因组中的重复片段是以镶嵌结构存在的，这就意味着基因组中的？组重复逡逑片段可能由一块或者多块重复片段拼接而成。如果直接将ＳＵｑｕｅｓｔ中识别的重复逡逑片段进行赋值，会导致建模出现错误，如遗漏掉一部分重复片段等。因此，需要逡逑将每一个嵌套重复片段中拼接的部分识别出来，根据每个嵌套部分进行切块，之逡逑后根据切块的相似性等特征进行赋值，最终完成建模。建模的过程如下所述：逡逑２．１．邋１重复片段的合并逡逑为了识别序列中的嵌套重复片段，算法将每一个重复片段看作是基因组中的逡逑－个丨ｘ：间，这样根据Ｍ复片段的位置，每一个重复片段被标记在整个基因组区间逡逑中。在基因组中，如果两个重复片段区间之间是重叠的．或者两个重复片段之间逡逑的距离不超过设定的参数（默认为0ｂＰ），那么将其合并，得到一个更大的区间。逡逑当每一个区间个能再扩张时，它将成为一个新的重复片段区间。合并之后的结果逡逑如图２－１所示。逡逑■■■■■逦Ｉ逦１逦■■■■■■逦ｒ—ｒｒｎ逡逑

找与此对应的重复片段进行重复的编号，同时，如果此编号的部分将嵌套的重复逡逑片段分割，那就将分割的剩余部分进行分块与编号。不断的重复上述过程，直至逡逑所有的重复片段完成分割与编号。如图２－２所示例子中，选取最短的重复片段区逡逑间进行编号为Ｃ，并将与之对应的部分都编号为Ｃ，之后将其存在的嵌套重复片逡逑段进行分块并且编号为Ｂ、Ｄ，Ｆ、Ｇ。这就完成了所有重复片段的编号。逡逑；ｂ邋；逦ｃ逦；邋ｄ逦；逦｜ｆ；逦ｃ逦Ｉ邋ｇ逦Ｉ逦Ｉ逦ｂ逦Ｉ邋ｃ邋Ｉｄ；逦ｉ邋ｆ邋；逦ｃ逦；ｇ；逡逑……ｉ；．邋ｎ？；逦

找与此对应的重复片段进行重复的编号，同时，如果此编号的部分将嵌套的重复逡逑片段分割，那就将分割的剩余部分进行分块与编号。不断的重复上述过程，直至逡逑所有的重复片段完成分割与编号。如图２－２所示例子中，选取最短的重复片段区逡逑间进行编号为Ｃ，并将与之对应的部分都编号为Ｃ，之后将其存在的嵌套重复片逡逑段进行分块并且编号为Ｂ、Ｄ，Ｆ、Ｇ。这就完成了所有重复片段的编号。逡逑；ｂ邋；逦ｃ逦；邋ｄ逦；逦｜ｆ；逦ｃ逦Ｉ邋ｇ逦Ｉ逦Ｉ逦ｂ逦Ｉ邋ｃ邋Ｉｄ；逦ｉ邋ｆ邋；逦ｃ逦；ｇ；逡逑……ｉ；．邋ｎ？；逦

【相似文献】

相关期刊论文 前10条

1 冉金玉;张新功;;总加权误工损失的两个代理单机排序问题[J];湖北民族学院学报(自然科学版);2019年01期

2 韩飞;;高中数学一道数列典型题解法的探究[J];数学学习与研究;2016年23期

3 豆俊梅;孙彩贤;;单机排序问题的研究[J];数学学习与研究;2017年24期

4 胡觉亮;杨佳雯;苏晓彤;董建明;;机器带周期性维护时段的加工与运输协同排序问题[J];浙江理工大学学报(自然科学版);2016年06期

5 仲维亚;马晓茹;;带有运输且加工具有灵活性的无等待流水作业排序问题[J];运筹学学报;2016年04期

6 隋楠;罗成新;;具有维护活动及公共工期的加工时间依赖资源的单机排序问题[J];沈阳航空航天大学学报;2016年06期

7 林浩;何程;;关于工期分配与加权误工数的双指标排序问题（英文）[J];工程数学学报;2017年01期

8 赵传立;张蕾;;带有交货期窗口和加工时间可控的排序问题[J];沈阳师范大学学报(自然科学版);2016年04期

9 王申重;杜海龙;;具有学习效应和遗忘效应的单机排序问题研究[J];枣庄学院学报;2017年02期

10 陈蕾;张安;陈永;陈光亭;;资源定时投放的单机排序问题[J];杭州电子科技大学学报(自然科学版);2017年02期

相关会议论文 前10条

1 张莲珠;;关于六角链的极值和排序问题的一些结果[A];中国运筹学会第六届学术交流会论文集（上卷）[C];2000年

2 吕绪华;杨汉兴;;求解装配式排序问题的归并算法及其性能比研究[A];中国运筹学会第六届学术交流会论文集（下卷）[C];2000年

3 周支立;李怀祖;;有重叠区域的两抓钩周期性排序问题的求解[A];Systems Engineering, Systems Science and Complexity Research--Proceeding of 11th Annual Conference of Systems Engineering Society of China[C];2000年

4 孙世杰;陈跃;;参数可控的排序问题[A];2001年全国数学规划及运筹研讨会论文集[C];2001年

5 张玉忠;;分批排序问题研究[A];中国运筹学会第七届学术交流会论文集（上卷）[C];2004年

6 张玉忠;;分批排序问题研究[A];中国运筹学会第七届学术交流会论文集（中卷）[C];2004年

7 胡荣;吕绪华;;3TMF排序问题的计算复杂性及分支定界法[A];中国运筹学会第八届学术交流会论文集[C];2006年

8 柏孟卓;唐国春;;加工时间可控的同时加工排序问题[A];2006年中国运筹学会数学规划分会代表会议暨第六届学术会议论文集[C];2006年

9 樊保强;;带仓储约束的准时排序问题[A];中国运筹学会第九届学术交流会论文集[C];2008年

10 吴翠连;;有尺寸的单机分批排序问题的近似算法[A];中国企业运筹学[2011（1）][C];2011年

相关重要报纸文章 前3条

1 杨文波;浅谈方位词“东、西、南、北”的词语排序问题[N];语言文字周报;2018年

2 山东 赵玉勇;小博士编程[N];电脑报;2004年

3 何靖;全国计算机应用技术证书考试（NIT）[N];中国电脑教育报;2003年

相关博士学位论文 前10条

1 李融奇;在线排序和批排序问题研究[D];浙江大学;2018年

2 沈佳煜;不确定情形下若干排序问题的研究[D];南京理工大学;2017年

3 高园;新型排序问题的计算复杂性研究[D];郑州大学;2018年

4 殷娜;依赖于资源分配的排序问题研究[D];上海大学;2015年

5 李好好;若干排序问题研究[D];浙江大学;2014年

6 王吉波;工件加工时间可变的现代排序问题[D];大连理工大学;2005年

7 罗润梓;平行机半在线排序问题[D];上海大学;2005年

8 季敏;当代工业中的若干排序问题研究[D];浙江大学;2006年

9 叶德仕;通讯网络中排序问题的若干在线和高性能算法[D];浙江大学;2005年

10 李文华;关于分批排序问题的研究[D];郑州大学;2006年

相关硕士学位论文 前10条

1 曹移林;平行多阶段作业排序问题的研究[D];华东理工大学;2019年

2 王亚男;具有退化维护和资源分配的单机排序问题[D];沈阳师范大学;2019年

3 李石;与资源相关加工时间可变的单机排序问题[D];沈阳师范大学;2019年

4 姜晓燕;MapReduce排序问题的若干算法研究[D];北京邮电大学;2019年

5 康宇红;具有错位限制的重新排序问题研究[D];重庆师范大学;2019年

6 罗鼎晖;大金山岛不同植物群落下土壤动物群落特征[D];华东师范大学;2019年

7 郭亚敏;饲粮能量水平对藏羊瘤胃氮素转运及利用效率的影响[D];兰州大学;2019年

8 王睿智;基因组比较分析的算法与软件[D];山东大学;2019年

9 丛稳;工件可拒绝的单机重新排序问题[D];郑州大学;2019年

10 潘婷婷;带资源、学习效应、恶化效应、维护活动和工期窗口的排序问题的研究[D];苏州大学;2018年

本文编号：2794243