基因组装论文数学建模.doc

EAST CHINA INSTITUTE OF TECHNOLOGY论文题目：基因组组装姓名1:姓名1:姓名1:王天宏学号:201120460220 专业:陈翠琳学号:201220360207 专业:程文俊学号:201220360122 专业:信息管理与信息系统数学与应用数学:学与应用数学2014年7月21日基因组组装摘要：基因组测序是生物信息学的核心，有着极其重要的应用价值新的测序技 术大量涌现，产生的reads长度更短，数量更多，覆盖率更大，能直接读取的碱 基对序列长度远小于基因组长度所以测序之前DNA分子要经过复制若干份、随 机打断成短片段要获取整个DNA片段，需要把这些片段利用重合部分信息组织 连接如何在保证组装序列的连续性、完整性和准确性的同吋设计耗吋短、内存 小的组装算法是本题的关键本文就该问题提出了一种新的重叠群生成算法该算法基于debruijn阁，将从 多头测序转化成在debruijn图的欧拉路径问题，并采用启发式搜索，能够快速 地处理大量测序数据，而且能得到质量较高的重叠群本文详细叙述了该问题的算法以及实现过程确定k-mer长度后，将这些k-mer 存入de bruijn图中，发现重叠关系式并不需要所有reads之间进行两两比对， 只要寻找de bruijn阁或子阁中的一条欧拉路径就可以找到contigo以初始 k-mer为节点，采用贪婪策略获得质量较高的后继k-mer，保证了 contig的高质 量拼接，从而还原基因组。

最终在第二问的实践中也获得了质量较高的contig 序列关键词：基因组组装;de Bruijn ^1；拟合；启发式搜索目录一、 M题的重述与分析 31.1问题背景 31.2问题提出 31.3 H题射斤 41.3.1问题一分析 41.3.2问题二分析 4二、 问题假没与符号说明 52.1问题鎌 52.2符号说明 5三、 数据分析与模型的建立 53.1问题一的模型建立 53.2问题二的模型建立 6四、 模型的求解 64.1问题一的模型求解 64.1.1 逮立 de bruijn 图 64.1.2模型求解 74.2问题二的模型求解 9五、 模型的评价与改进 95.1模型的优缺点 95.2模型的改进 10参考文献： 10隱： 10一. 问题的重述与分析1.1问题背景快速和准确地获取牛.物体的遗传信息对于牛.命科学研究只有重要的意义对每 个生物体来说，基因组包含了整个生物体的遗传信息，这些信息通常由组成基因 组的DNA或RNA分子中碱基对的排列顺序所决定获得目标生物基因组的序列信 息，进而比较全而地揭示綦因组的复杂性和多样性，成为生命科学领域的重要研 宄内容1.2问题提出确定基因组碱基对序列的过程称为测序。

0前能直接读取的碱基对序列长度 远小于棊因组序列长度，因此需要利用一定的方法将测序得到的短片段序列组装 成更长的序列通常的做法是，将基因组复制若干份，无规律地分断成短片段后 进行测序，然后寻找测得的不同短片段序列之间的重合部分，并利用这些信息进 行组装例如，若有两个短片段序列分别为ATACCTTGCTAGCGTGCTAGCGTAGGTCTGA则有可能基因组序列中包含有ATACCTTGCTAGCGTAGGTCTGA这一段由于技术的限制和实际情况的复杂性，最终组装得到的序列与真实基因组序列之间仍可能存在差异，甚至只能得到若干条无法进一步连接起来的序列对组装 效果的评价主要依据组装序列的连续性、完整性和准确性连续性要求组装得到 的(多条)序列长度尽可能长；完整性要求组装序列的总长度占棊因组序列长度 的比例尽可能大；准确性要求组装序列与真实序列尽可能符合利用现有的测序技术，可按一定的测序策略获得长度约为50 - 100个碱基对的 序列，称为读长(reads)基因组复制份数约为50 - 100基因组组装软件可根 据得到的所有读长组装成基因组，这些软件的核心是某个组装算法一个好的算 法应具备组装效果好、时间短、内存小等特点。

新一代测序技术在高通量、低成 本的同时也带来了错误率略有增加、读长较短等缺点，现有算法的性能还有较大 的改善空间具体解决问题如下：(1) 建立数学模型，设计算法并编制程序，将读长序列组装成基因组你的算 法和程序应能较好地解决测序中可能出现的个别碱基对识别错误、基因组中存在 重复片段等复杂情况2) 现有一个全长约为120,000个碱基对的细菌人工染色体，采用Hiseq2000 测序仪进行测序，测序策略以及数据格式的简要说明见附录一和附录二，测得的 读讼数据见附录三，测序深度约为70X,即基因组每个位置平均被测到约70次 试利用你的算法和程序进行组装，并使之具有良好的组装效果1.3问题分析1.3.1问题一分析本题是基于新一代测序技术的基因组组装算法问题，要求设计算法针对性的解 决新一代测序技术带来的一些弊端1) reads长度较短，数量较多 de brui jn图新一代测序技术所得的reads长度较短，数量较多，不易发现reads之间的重叠 关系可以将reads转化成定长的k-mcr，然后寻找k-mer之间的重叠关系然 后建立de brui jn图，把短序列拼接问题转化为de brui jn图中的欧拉路径问题。

2) 个别碱基对识别错误一一多重对比纠错通过将多个reads放在一起比对来发现错误.(3) 基因组中存在大量重复片段重复片段可能导致拼接错误，或者导致不连续的较短ccmtig出现重叠片段 类型主要有以下儿种，如下图所示重复片段问题可以用如下问题解决：通过对比，可先将重复片段隔离开来，较 高的覆盖度有利于重复片段的隔离，但是，较多的测序错误将不利于该过程的进 行如果重复片段比reads长，可利用pared end reads来解决；如果重复片 段比reads短，那么该reads又被称为spanner, 一个spanner就是一个重复 片段W端再加儿个碱基组成利用spanner解决重复片段问题需耍如下两个信 息：一是重复片段两端配对的reads ,这两个reads必须不相同；二是重复片 段中的一个配对reads，只要知道一个即可，另一个配对reads可以不在重复 片段中通过分析己知的基因组，可获得有关重复片段的更多信息，如，重复片 段的长度，重复片段的模式等原基因组： t t t 女A R B R A拼接之后： * > kARB R原墓因组 ► ► > ►A R B R R C R拼接之后： 卜 • r kB R D A CD原基因组： i i 嘲 A B C B A拼接之后 • M 1.3.2问题二分析本题题H提供全长约为120, 000个碱基对的细菌人工染色体，采用新一代的 Hiseci2000测序仪进行测序。

附件提供了筛选好的定K: reads数据文件使用第 一题设计的基于de bruijn图的组装算法对reads数据进行组装，并对结果进行误差分析二、问题假设与符号说明2.1问题假设(1) 假设测序过程中没有其他因素的干扰；(2) 假设题目所给定的序列相对位置的碱基全部遵循GU-AC法则；⑶假设题A中所有的序列都是正常可判别的序列，没有出现序列的基因突变等 情况；(4) 假设一个完整基因组，打断成500bp的片段是随机的；(5) 假设基因组每个位置被测到的几率是等可能的；(6) 所冇片段上的碱基都已经被识别出来，不存在未知碱基2.2符号说明reads:利用现有的测序技术，可按一定的测序策略获得长度约为50 - 100个碱基 对的序列，称为读长；contig(C):由reads经过一定算法拼接产生3kb〜10Mb以lAl的一些棊因组片段; k-mer：长度力k的一段DNA片‘段；quality (Q):侮一个reads都含有一个质量值，该值能反映该reads的正确率 质量值越高，reads的正确率越高三、数据分析与模型的建立对测序仪测出的数据进行分析，有如下特征：(1) 棊因组中有些位置被较多reads所覆盖，有些位置被较少reads所覆盖，这 些位置是随机的，不可预知。

2) 每个reads的每个碱基都有一个质量值，该质量值能反映该碱基的正确率 质量值越高，则碱基的正确率越高3) 有些reads上某个碱基含量过高(超过90%),其至所冇碱基都是某一个碱基， 这样的reads错误率较高，在併接过程中应尽力避免使用该类reads3.1问题一的模型建立根据新一代测序过程，木文建立了如下模型：分别从500bp片段的两端，对 两条单链进行测序，测得的读长记为readsl，reads2reads 1, reads2的长度均为 88bp，且该对reads相距500bp由reads2通过碱基互补配对原则川得reads3,再把碱基ATCG分别记为1、2、3、4,则可构成1 x88的矩阵通过reads 1与reads3 的矩阵和减可判断该条单链是否可以重组，另一条单链可由碱基互补配对获得， 再对数据进行拟合，通过拟合的效果可判断组装的正确率Genome2 | 5OObp88bpireadl3 .read：5OObp3.2问题二的模型建立建立de brui jn图(1) 将k值定为4把上述readl文件中的序列存入库中，开始建立read条目 的数据结构和k-mer条目的数据结构。

预读数据，逐条读取read数据，每条 readTD进行升序保存；生成该read上所有k_mer (共85个k_mer)，统计这些 k-mer出现的次数，填写k-mer结构中的mnn字段相关数据录入程序源代码见 附录2) 遍历de brui jn图，根据上一步统计的k_mer数量，申请readlDpos数组 所需要的内存空间依次读取每一个read,填写readID_pos数组中的第cur行， 填好之后把cur值加13) 将碱基替换成2位二进制数{A=00, C=01, G=10, T=ll}o模型的求解4.1问题一的模型求解4.1.1 建立 de bruijn 图(1)将k值定为4把上述readl文件中的序列存入库中，开始建立read 条目的数据结构和k-mer条目的数据结构预读数据，逐条读取read数据，每 条read ID进行升序保存；生成该read上所有k-mer (共85个k-mer),统计这些k-mer出现的次数，填写k_mer结构中的mim字段如阁所示，为相关代码片 段和关数据录入程序源代码见附录2) 遍历debruijn图，根据上一步统计的k-mer数量，申请readID_pos数组 所需要的N存空间。

依次读取每一个read,填写readll)_pos数组中的第cur行， 填好之后把cur值加13) 将碱基替换成2位二进制数{A=00, C=01, G=10, T=ll}o4.1.2模型求解由于数据非常庞大，演算拼接过程不能完整的展示，接下来将列举一段算法 拼接的过程：(1 )初始 k-mer 定为 AAAC 即 00000001，该 k-mer 出现在 4 条 read 上，且 k-m。