暑期数模培训作业

《暑期数模培训作业》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、实用标准文案基因组组装摘要快速和准确地或其生物提的遗传信息对生命科学研究具有重要的意义。测序技术从第一代到现在普遍应用的第二代以及正在兴起的第三代，能直接读取的碱基对序列长度远小于基因组长度。所以测序之前DNA分子要经过复制若干份、随机打断成短片段。要获得整个DNA片段，需要把这些片段利用重合部分信息组装连接。如何在保证组装序列的连续性、完整性和准确性的同时设计耗时短、内存小的组装算法是本题的关键。对于第一问，我们根据题目所给的一些方法再结合了相应的资料，最终我们依据基于Hamilton路径的拼接算法利用用优化后的Phrap算法并根据Phrap算法的内容选取了Smith-Waterman

2、算法以及Tarjan算法等算法对问题建立了数学模型。对于第二问，我们根据第一问所建立的模型根据算法过程对题目所给的数据进行了预处理，然后编写了Java程序，把处理后的数据输入程序得到相应结果。关键词Hamilton图；Phrap算法；DNA拼接一、问题重述快速和准确地获取生物体的遗传信息对于生命科学研究具有重要的意义。对每个生物体来说，基因组包含了整个生物体的遗传信息，这些信息通常由组成基因组的DNA或RNA分子中碱基对的排列顺序所决定。获得目标生物基因组的序列信息，进而比较全面地揭示基因组的复杂性和多样性，成为生命科学领域的重要研究内容。测序技术始于20世纪70年代，伴随着人类基因组计

3、划的实施而突飞猛进。从第一代到现在普遍应用的第二代，以及近年来正在兴起的第三代，测序技术正向着高通量、低成本的方向发展。利用现有的测序技术，可按一定的测序策略获得长度约为50–100个碱基对的序列，称为读长（reads）。基因组复制份数约为50–100。基因组组装软件可根据得到的所有读长组装成基因组，这些软件的核心是某个组装算法。常用的组装算法主要基于OLC（Overlap/Layout/Consensus）方法、贪婪图方法、deBruijn图方法等。一个好的算法应具备组装效果好、时间短、内存小等特点。新一代测序技术在高通量、低成本的同时也带来了错误率略有增加、读长较短等缺点，现有算法的

4、性能还有较大的改善空间。问题一：试建立数学模型，设计算法并编制程序，将读长序列组装成基因组。你的算法和程序应能较好地解决测序中可能出现的个别碱基对识别错误、基因组中存在重复片段等复杂情况。问题二：现有一个全长约为120,000个碱基对的细菌人工染色体（BAC），采用Hiseq2000测序仪精彩文档实用标准文案进行测序，测序策略以及数据格式的简要说明见附录一和附录二，测得的读长数据见附录三，测序深度（sequencingdepth）约为70×，即基因组每个位置平均被测到约70次。试利用你的算法和程序进行组装，并使之具有良好的组装效果。二、问题分析伴随着人类基因组计划的实施和突飞猛进，基因组

5、测序组装的研究意义越来越重要。如果不能快速、准确的获取信息，基因组的研究将会是举步维艰，人类基因组计划也难以进行下去。所以，建立合理有效的基因组组装模型迫在眉睫。对于问题一，首先，我们通过DNA(RNA)分子中碱基对的互补特征，确定基因拼接方式，即将DNA分子中的一条链的互补链与其对应的另一条链比对，找到阈值允许范围内个数的相同碱基序列将单个基因片段记录并相连。其次，根据Hamiltom图论原理，将拼接上的特征子串看做是一个个结点，并将这些结点根据其中信息的联系通过有向线段连接，然后在这些所有的有向线段中找到一条最长、通过结点最多的路径，次路径就是我们要找到的基因链。最后，基于对拼接中的

6、deBruijn图结构的研究，为使repeat结构拼接准确性更高，讨论的deBruijn图中错位数对拼接结果的影响。将之前的模型进一步优化三、模型的假设与符号的说明四、模型的建立与求解对于问题一的求解本题是基于新一代测序技术的基因组装算法问题，要求设计算法针对性的解决新一代测序技术带来的一些弊端。1.先是通过DNA(RNA)分子中碱基对的互补特征，确定基因拼接方式DNA（RNA）分子中碱基对的互补特征[1]：在DNA分子结构中，由于碱基之间的氢键具有固定的数目和DNA两条链之间的距离保持不变，使得碱基配对必须遵循一定的规律，这就是Adenine（A，腺嘌呤）一定与Thymine（T，胸腺

7、嘧啶）配对，Guanine（G，鸟嘌呤）一定与Cytosine（C，胞嘧啶）配对，反之亦然。碱基间的这种一一对应的关系叫做碱基互补配对原则。腺嘌呤与胸腺嘧啶之间有两个氢键，鸟嘌呤与胞嘧啶之间有三个氢键，即A＝T,G≡C。基因拼接方式[2]：由于碱基间的这种一一对应的关系碱基互补配对原则，而当前测序仪的准度不能超过500bp(basepair，碱基对)的序列具有很高的准确性。所以对于长的基因（如人类基因组DNA长达30亿bp），在生物