基因组组装模型论文
图4-5-4.2局部拼接填充gaps
为了加快拼接速度，我们在实际操作时选择从gaps两端同时相向拼接，即在相邻contigs对应的两末端同时开始在悬浮reads表和De Bruijn图的引导下对gaps进行填充。在填充gaps的同时，需要时刻检测这两条contigs之间的gaps信息，一旦gaps的大小接近0时就停止填充，以防止过填充情形的出现。
4.5 算法的小结
本节详细介绍了基于reads引导的基因组序列拼接算法，该算法的实施具体包括reads拼接和contigs组装两个阶段。reads拼接阶段主要有数据的预处理、De Bruijn图的建立和contigs构建等几部分，其中重点介绍了拼接时下一个kmer的选择策略，即以配对reads数据为拼接导航、综合考虑整条reads参与拼接的累计信息，并结合reads数据的区域特征提出打分机制，对待选的所有kmer进行打分，取得分最大者。contigs组装阶段主要介绍了contigs相对位置的确定、contigs连接和gaps填充等几方面的内容，就contigs之间序列交叠overlap和间隙gaps的界定，以及contigs末端出错碱基的处理及纠正等做了深入的探究。高效的数据结构，巧妙的拼接组装策略等，为该算法的成功实施提供了重要保障。
五.模型中算法的验证
在基于reads引导的基因组序列拼接算法理论的指导下，我们结合实际应用的需要，开发出一套基因组序列拼接系统，该序列拼接系统被命名为SRGA，经数据测试取得了不错的效果，从而验证了算法的正确性。
图5-1是用相关软件做出的基因组比对相似度的一部分。
13
基因组组装模型论文
图5-1.基因组的相似度比对
5.1算法的输入与输出
SRGA序列拼接系统主要包括两个大的功能模块，reads拼接模块和contigs组装模块。这两个模块相对独立，作用于输入数据的不同处理阶段，reads拼接模块生成的contigs是contigs组装模块的输入。在算法实现时，我们选择了C语言作为系统开发语言，并将软件在linux环境下发布。
14
基因组组装模型论文
新一代测序技术的快速发展，产生了大量的配对reads数据，而这些配对reads的数据文件就是系统的初始输入。如图4-1所示，reads配对数据通常分布在两个数据文件，在每个单独的文件里，每4行作为一个基本单位，记录着一条reads的序列信息和碱基质量信息。其中，第1行和第3行是测序信息，第2行是reads的碱基序列，第4行是reads每个碱基的质量值，reads的碱基序列和碱基质量值是基因组序列拼接所需要的数据信息。配对reads所分布的两个文件里对应的reads相互配对，即第一个文件里的第1条reads与第二个文件的第1条reads配对，第一个文件里的第2条reads与第二个文件的第2条reads配对，依次类推。
就系统的初始输入而言，除了配对reads数据文件，还有一个重要的参数需要人为设定，即K值。K值表征kmer的大小，在不同K值条件下，基因组序列的拼接效果往往相差很大。K值的选择还没有通用的方法，一般是通过综合考虑reads长度、数据覆盖度、目标基因组长度等因素而设定。
图5-2reads拼接阶段生成的contigs示意
初始输入的配对reads经过SRGA的reads拼接功能模块处理后，会生成大量的长度更长的序列片段contigs。如图4-2所示，生产的contigs包括contigs的编号，contigs的长度及contigs的碱基序列等。contigs只是序列拼接的中间结果，将与初始输入的配对reads一起作为系统contigs组装模块的输入。
15
基因组组装模型论文
图5-3 contigs组装阶段生成scaffolds示意
reads拼接模块生成的contigs和初始输入的配对reads数据经过contigs组装功能模块的作用后，会生成若干条序列长达几十kbp甚至几百kbp的基因组序列片段scaffolds。如图4-3所示，生成的scaffolds包括scaffolds的编号，拼接成scaffolds的contigs数目及scaffolds碱基序列等。
scaffolds是SRGA序列拼接系统生成的最终输出结果，scaffolds数据生产后，科研人员就可以在对其进行一系列数据分析操作，比如查找功能相似的基因序列、分析单碱基变异等，为生命科学的研究提供帮助。
六 评价结果及分析：
模型在建立过程中，经过严密的运算和验证后，总结出其优点如下：
⑴在reads拼接方面，从整体reads的角度入手，综合考虑拼接过程中的累计信息，同时又参考了reads的数据特征，为contigs的拼接提供了全面而客观的评分标准。并优先考虑有配对的reads数据，能够高精确性地为contigs的拼接导航，避免了传统的基于k-mers的拼接计算
⑵在contigs组装方面，提出了PEN数组的概念，用于contigs之间相对位置的确定。相邻contigs连接时，采用启发式搜索策略，进行线性扩展，降低了计算复杂度。并用序列对比的方法来检测contigs之间的overlap，对contigs末端的碱基错误进行纠正，较好地消除了contigs末端拼接错误的影响，大大提高了contigs组装的准确性。
16
基因组组装模型论文
⑶在空间和时间复杂度上，本算法都优于其它的算法，较低些。 本文提出并实现了基于reads引导的基因组序列拼接算法，经数据验证，该 算法表现出色，但仍然存在以下不足之处，有待在后续研究工作中加以改进。其不足之处如下：
⑴该算法不支持多配对文库。配对数据在序列拼接时有着重要应用，多组配对数据的使用能大大提高序列的拼接质量。但目前系统的输入只能是一个配对文库，需要加以扩展。
⑵选择下一个kmer的打分函数不够精确。当数据覆盖度较高时，由于决策表被锁定的reads会很多，造成同时多个待选kmer的得分值都很大，难以取舍，需要在区域得分设置及总分量化等方面进一步优化。
七.参考文献：
参考学位论文：
[1]韩东涛.基于概率模型的基因组从头测序算法研究. 哈尔滨工业大学，2012 [2]曾培龙. 基于reads引导的基因组序列拼接. 哈尔滨工业大学,2012。
[3]杨帆 .基于 BWT 的 DNA 重叠群序列合并算法研究,哈尔滨工业大学，2012。 [4]范建蕊. 基于双向de Bruiin图的序列拼接并行化研究与实现，中南大学，2012。
[5]林勇. 面向下一代测序技术的 de novo 序列拼接工具综述,上海理工大学，2012.
参考书籍： 《数学模型》（第三版）姜启源 谢金星 叶俊 编，高等教育出版社。
《全国大学生数学建模竞赛优秀论文汇编》 全国大学生数学建模竞赛组委员会编，中国物价出版社。
《基因工程》 梁文蔚等编，高教出版社，2011.
八.附录
另一文件夹有相关的程序和基因组装软件以及数据。
17