论文部分内容阅读
基因组是生物体中携带遗传信息的遗传物质的总和，大部分生物的基因组由DNA组成。DNA分子是由脱氧核糖核苷酸（A腺嘌呤、G鸟嘌呤、T胸腺嘧啶、C胞嘧啶）连接成的碱基序列。对基因组的研究有助于提高人们对各种生命现象的认识，而基因组研究的第一步就是获取基因组碱基序列信息。由于测序技术的限制，测序仪器每次只能获得DNA分子上较短子序列（几百bp到上千bp）的碱基信息，从而使得以测序数据为输入获取原始基因组序列的基因组序列拼接算法研究成为基因组研究中一个重要步骤。 针对各种测序仪器获得数据特性不同，研究人员提出了各种与之相适应的拼接算法。本文主要关注以高通量、低成本、短读段为特点的二代测序数据(Next GenerationSequencing)和以超长读段为特点的酶切图谱数据(Optical Mapping)。现有的基于以上两种数据的拼接方法中存在一些弊端: (1)单独使用二代数据的方法，由于二代数据自身数据读段短的原因，很难跨过长的重复序列区域，导致拼接结果短; (2)现有的使用酶切图谱数据和二代数据的混合拼接方法多基于联配“搭桥”的策略，没有使用二代数据拼接过程中已有的连接信息，拼接结果存在空位(gap)。 本课题为克服现有缺点，提出了全新的基于二代数据和酶切图谱数据的混合拼接策略，获得以下成果: (1)提出了基于蒙特卡洛树搜索(MCTS，Monte Carlo Tree Search)的路径搜索算法 本文将给定酶切图谱数据获取其对应碱基路径的问题，转化为在二代拼接图中的路径寻找问题。通常使用的局部最优的贪心方法得到路径的准确率过低;而全局最优的暴力搜索方法在运行时间上难以承受。本文采用蒙特卡洛树搜索算法求解该问题，获得了很好的运行时间和准确率上的平衡。在模拟数据集上，该算法获得了优于暴力搜索方法约十倍的运行效率，而准确率只有稍许下降;相对贪心方法，该算法则在运行时间可以承受的基础上，获得五倍以上的准确率提升。 (2)开发了基于二代测序数据和酶切图谱测序数据的混合拼接软件nanoARCS2 nanoARCS2以二代数据和酶切图谱数据为输入获取最终的拼接结果。算法流程分为预处理、路径搜索和后处理三步。算法充分考虑了两种数据各自的读长，通量以及错误类型等特点，融合了两种数据各自的优势，在测试数据集上得到的拼接结果contigN50是只使用二代数据拼接得到结果的2.1倍。