基因组装论文数学建模

《基因组装论文数学建模》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、EASTCHINAINSTITUTEOFTECHNOLOGY论文题目：基因组组装姓名1:姓名1:姓名1:王天宏学号:201120460220专业:陈翠琳学号:201220360207专业:程文俊学号:201220360122专业:信息管理与信息系统数学与应用数学:学与应用数学2014年7月21日基因组组装摘要：基因组测序是生物信息学的核心，有着极其重要的应用价值。新的测序技术大量涌现，产生的reads长度更短，数量更多，覆盖率更大，能直接读取的碱基对序列长度远小于基因组长度。所以测序之前DNA分子要经过复制若干

2、份、随机打断成短片段。要获取整个DNA片段，需要把这些片段利用重合部分信息组织连接。如何在保证组装序列的连续性、完整性和准确性的同吋设计耗吋短、内存小的组装算法是本题的关键。本文就该问题提出了一种新的重叠群生成算法。该算法基于debruijn阁，将从多头测序转化成在debruijn图的欧拉路径问题，并采用启发式搜索，能够快速地处理大量测序数据，而且能得到质量较高的重叠群。本文详细叙述了该问题的算法以及实现过程。确定k-mer长度后，将这些k-mer存入debruijn图屮，发现重叠关系式并不需要所有reads之

3、间进行两两比对，只要寻找debruijn阁或子阁中的一条欧拉路径就可以找到contigo以初始k-mer为节点，采用贪婪策略获得质量较高的后继k-mer，保证了contig的高质量拼接，从而还原基因组。最终在第二问的实践中也获得了质量较高的contig序列。关键词：基因组组装;deBruijn^1；拟合；启发式搜索目录一、M题的重述与分析31.1问题背景31.2问题提出31.3H题射斤41.3.1问题一分析41.3.2问题二分析4二、问题假没与符号说明52.1问题鎌52.2符号说明5三、数据分析与模型的建立53

4、.1问题一的模型建立53.2问题二的模型建立6四、模型的求解64.1问题一的模型求解64.1.1逮立debruijn图64.1.2模型求解74.2问题二的模型求解9五、模型的评价与改进95.1模型的优缺点95.2模型的改进10参考文献：10隱：10一.问题的重述与分析1.1问题背景快速和准确地获取牛.物体的遗传信息对于牛.命科学研究只有重要的意义。对每个生物体来说，基因组包含了整个生物体的遗传信息，这些信息通常由组成基因组的DNA或RNA分子屮碱基对的排列顺序所决定。获得目标生物基因组的序列信息，进而比较全而地

5、揭示綦因组的复杂性和多样性，成为生命科学领域的重要研宄内容。1.2问题提出确定基因组碱基对序列的过程称为测序。0前能直接读取的碱基对序列长度远小于棊因组序列长度，因此需要利用一定的方法将测序得到的短片段序列组装成更长的序列。通常的做法是，将基因组复制若干份，无规律地分断成短片段后进行测序，然后寻找测得的不同短片段序列之间的重合部分，并利用这些信息进行组装。例如，若有两个短片段序列分别为ATACCTTGCTAGCGTGCTAGCGTAGGTCTGA则有可能基因组序列中包含有ATACCTTGCTAGCGTAGGTC

6、TGA这一段。由于技术的限制和实际情况的复杂性，最终组装得到的序列与真实基因组序列之间仍可能存在差异，甚至只能得到若干条无法进一步连接起来的序列。对组装效果的评价主要依据组装序列的连续性、完整性和准确性。连续性要求组装得到的(多条)序列长度尽可能长；完整性要求组装序列的总长度占棊因组序列长度的比例尽可能大；准确性要求组装序列与真实序列尽可能符合。利用现有的测序技术，可按一定的测序策略获得长度约为50-100个碱基对的序列，称为读长(reads)。基因组复制份数约为50-100。基因组组装软件可根据得到的所有读长

7、组装成基因组，这些软件的核心是某个组装算法。一个好的算法应具备组装效果好、时间短、内存小等特点。新一代测序技术在高通量、低成本的同时也带来了错误率略有增加、读长较短等缺点，现有算法的性能还有较大的改善空间。具体解决问题如下：(1)建立数学模型，设计算法并编制程序，将读长序列组装成基因组。你的算法和程序应能较好地解决测序中可能出现的个别碱基对识别错误、基因组中存在重复片段等复杂情况。(2)现有一个全长约为120,000个碱基对的细菌人工染色体，采用Hiseq2000测序仪进行测序，测序策略以及数据格式的简要说明见

8、附录一和附录二，测得的读讼数据见附录三，测序深度约为70X,即基因组每个位置平均被测到约70次。试利用你的算法和程序进行组装，并使之具有良好的组装效果。1.3问题分析1.3.1问题一分析本题是基于新一代测序技术的基因组组装算法问题，要求设计算法针对性的解决新一代测序技术带来的一些弊端。(1)reads长度较短，数量较多debruijn图新一代测序技术所得的reads长度较短，数量较多，