《暑期数模培训作业》由会员分享，可在线阅读，更多相关《暑期数模培训作业（28页珍藏版）》请在金锄头文库上搜索。
1、word基因组组装摘要快速和准确地或其生物提的遗传信息对生命科学研究具有重要的意义。测序技术从第一代到现在普遍应用的第二代以与正在兴起的第三代，能直接读取的碱基对序列长度远小于基因组长度。所以测序之前DNA分子要经过复制假如干份、随机打断成短片段。要获得整个DNA片段，需要把这些片段利用重合局部信息组装连接。如何在保证组装序列的连续性、完整性和准确性的同时设计耗时短、内存小的组装算法是此题的关键。对于第一问，我们根据题目所给的一些方法再结合了相应的资料，最终我们依据基于Hamilton路径的拼接算法利用用优化后的Phrap算法并根据Phrap算法的内容选取了Smith-Waterman算法以与
2、Tarjan算法等算法对问题建立了数学模型。对于第二问，我们根据第一问所建立的模型根据算法过程对题目所给的数据进展了预处理，然后编写了Java程序，把处理后的数据输入程序得到相应结果。关键词Hamilton图；Phrap算法；DNA拼接一、问题重述快速和准确地获取生物体的遗传信息对于生命科学研究具有重要的意义。对每个生物体来说，基因组包含了整个生物体的遗传信息，这些信息通常由组成基因组的DNA或RNA分子中碱基对的排列顺序所决定。获得目标生物基因组的序列信息，进而比拟全面地揭示基因组的复杂性和多样性，成为生命科学领域的重要研究内容。测序技术始于20世纪70年代，伴随着人类基因组计划的实施而突飞
3、猛进。从第一代到现在普遍应用的第二代，以与近年来正在兴起的第三代，测序技术正向着高通量、低本钱的方向开展。利用现有的测序技术，可按一定的测序策略获得长度约为50100个碱基对的序列，称为读长reads。基因组复制份数约为50100。基因组组装软件可根据得到的所有读长组装成基因组，这些软件的核心是某个组装算法。常用的组装算法主要基于OLCOverlap/Layout/Consensus方法、贪婪图方法、de Bruijn图方法等。一个好的算法应具备组装效果好、时间短、内存小等特点。新一代测序技术在高通量、低本钱的同时也带来了错误率略有增加、读长较短等缺点，现有算法的性能还有较大的改善空间。问题一
4、：试建立数学模型，设计算法并编制程序，将读长序列组装成基因组。你的算法和程序应能较好地解决测序中可能出现的个别碱基对识别错误、基因组中存在重复片段等复杂情况。问题二：现有一个全长约为120,000个碱基对的细菌人工染色体BAC，采用Hiseq2000测序仪进展测序，测序策略以与数据格式的简要说明见附录一和附录二，测得的读长数据见附录三，测序深度sequencing depth约为70，即基因组每个位置平均被测到约70次。试利用你的算法和程序进展组装，并使之具有良好的组装效果。二、问题分析伴随着人类基因组计划的实施和突飞猛进，基因组测序组装的研究意义越来越重要。如果不能快速、准确的获取信息，基因
5、组的研究将会是举步维艰，人类基因组计划也难以进展下去。所以，建立合理有效的基因组组装模型迫在眉睫。对于问题一，首先，我们通过DNA (RNA)分子中碱基对的互补特征，确定基因拼接方式，即将DNA分子中的一条链的互补链与其对应的另一条链比对，找到阈值允许X围内个数的一样碱基序列将单个基因片段记录并相连。其次，根据Hamiltom图论原理，将拼接上的特征子串看做是一个个结点，并将这些结点根据其某某息的联系通过有向线段连接，然后在这些所有的有向线段中找到一条最长、通过结点最多的路径，次路径就是我们要找到的基因链。最后，基于对拼接中的 de Bruijn图结构的研究，为使repeat结构拼接准确性更高
6、，讨论的 de Bruijn图中错位数对拼接结果的影响。将之前的模型进一步优化三、模型的假设与符号的说明四、模型的建立与求解对于问题一的求解 此题是基于新一代测序技术的基因组装算法问题，要求设计算法针对性的解决新一代测序技术带来的一些弊端。通过DNA (RNA)分子中碱基对的互补特征，确定基因拼接方式DNARNA分子中碱基对的互补特征1：在DNA分子结构中，由于碱基之间的氢键具有固定的数目和DNA两条链之间的距离保持不变，使得碱基配对必须遵循一定的规律，这就是AdenineA，腺嘌呤一定与ThymineT，胸腺嘧啶配对，GuanineG，鸟嘌呤一定与CytosineC，胞嘧啶配对，反之亦然。碱
7、基间的这种一一对应的关系叫做碱基互补配对原如此。 腺嘌呤与胸腺嘧啶之间有两个氢键，鸟嘌呤与胞嘧啶之间有三个氢键，即AT, GC。基因拼接方式2：由于碱基间的这种一一对应的关系碱基互补配对原如此，而当前测序仪的准度不能 超过500bp(base pair，碱基对)的序列具有很高的准确性。所以对于长的基因如人类基因组DNA长达30亿bp，在生物学上普遍采用逆向构造的方法，将较长的序列做多个克隆，用酶将这些克隆随机割成小片段，然后又用测序反响测出小片段上各个位置上的碱基，直观的读出A,C,G,T的序列。通过一定的处理将互相重叠的序列拼接起来，复原出片段克隆的完整序列。而当前广泛采用的拼接方法是Cel
8、er公司的鸟枪法。基因组DNA随机打碎克隆序列序列拼接图1 全基因组鸟枪图法示意图全基因鸟枪法的主要工作包括两局部：shotgun 测序和序列拼接。其中shotgun测序主要流程如下，用途表示如图2.1. DNA的提取和纯化。2. 载体预备：和DNA片段结合，从而能够在细菌中扩增。3. DNA片段的制备：将DNA用超声波切成能够测序的小片段。4. 转化培养：小片段和载体结合，植入细菌中进展扩增。5. 提质粒：从细菌中提取出繁殖好的质粒。6. 电泳检测：检测质量的好坏。7. 测序：用测序仪侧序。DNA整体切成小段小段和载体结合结合进展测序图2 Shotgun 测序流程示意图全基因测序大致包括以下
9、几个步骤。序列测定：使用Sanger的双脱氧链终止法，即通过化学作用是DNA链在每一个碱基处终止，并在终止处染色是终端带放射性物质或荧光物质，通过变性凝胶的电泳和激光照射可以得到终止于不同碱基的DNA 片段的谱带。在激光照射到不同的碱基对上时，会反射不同的颜色，所以得到的谱带一般有四条，它记录的一般是不同颜色的放射光的亮度，测定美国片段的序列。碱基读出：运用计算机独处软件进展图像处理，以确定谱带所蕴含的DNA 序列。四条谱带在测序时被同步保存，处理软件试图按照一定的间隔读出一个碱基。序列拼接：在得到每个片段的序列后，利用这些片段见的重叠，将它们的拼接成原来的序列，或尽可能接近原来序列的几个较长
10、的序列。因为片段数据中含有序列的夺个克隆且片段的打断都是随机而独立的，这给拼接提供了足够的可能性。拼接的关键问题是得到每个片段在一个长序列中的位置信息，这种组合的集合称为contig (contiggoussegment).序列拼接是测序工作的关键所在，序列拼接方法和实现技术的好坏，直接影响到拼接结果的优劣，同时它与其他领域的联系广泛，也成为各学科研究的热点问题。Hamilton路径基于Hamilton路径的拼接算法总共有三个过程：找出序列片段间的的重复信息将存在有重合的片段组合起来形成一个contig结构根据片段中每个碱基的质量值在contig寻找中寻找一条“Consensus最终序列根据上
11、面的三个步骤，我们打算运用Phrap算法来对这个问题进展求解，Phrap算法大致也分为三步：QverlapLayoutConsensus1) 寻找Overlap区域使用实验所得到的基因片段reads作为数据源，片段间两两比照，找到所有的重叠区域，并对其进展筛选得到的所有的符合条件的重叠区域。2) Layout阶段利用在Overlap阶段得到的所有重叠区域，建立序列间的组合关系，称为“contig。3) Consensus阶段使用Layout阶段得到的所有contig结构，在contig结构的根底上建立加权有向图，遍历图得到权重最重的路径，获取与路径相对应的的序列称为“Consensus。一、
12、获得片段间的重要信息OverlapPhrap算法假定两个片段之间如果发生拼接，如此这两个片段之间必定有一局部是重叠局部。在它们重叠的局部上必然有一个最小长度为L的准确匹配区域。Phrap算法中将这个最小长度为L的子序列称为字Word，没一个字的长度为。在Phrap算法中，当一个Word的长度小于min-word时，该算法认为这两个片段不能够进展拼接，而当一个word的长度大于max-word时，Phrap算法认为这两条片段完全一样。即，Phrap算法设置了一个字长的区间用于对重叠区域进展筛选。对所有的reads进展两两比照，在碱基序列集合F中随机找出一个没有被处理过的碱基序列fi，在中寻找所有
13、可能的重叠区域并对区域进展筛选输出符合条件的重叠区域Overlap，直到F中所有序列处理完毕。重叠区域判定条件计算法：1判定条件满足条件的重叠区域就叫Overlap,其意义在于如果，如此表示这两个序列由于重叠区域太短不能进展拼接。如果如此表示重叠区域过长，此时这两个序列视为完全一样的重复序列。由于序列的测量存在误差，因此在进展重叠区域的寻找时应才用模糊匹配，在score(fi,fj)大于阈值的情况下才视两个模糊序列匹配成功，否如此认为这两个序列的重叠区域误差过大，不视为一个Overlap。Phrap算法描述为Input: n reads sequence,F=f1,f2,fnOutput: a
14、ll the Overlaps between any two readsBegin1. Let the minlen,maxlen, be the minimum length,maximum length and a threshold of Overlap respectively;2. Trim of the low qualitys reads;3. Use the Smith-Waterman algorithm to calculate the score of any two reads fi and fj (fiF,fjF,ij and I,j1,n)4. If score
15、(fi,fj and then pute the Largest Likely Ratio (LLR) of fi and fj,and output the Overlap(fi,fj).Else repeat the step 3;Iterate the step3 and 4 until each read of F has been handled.Phrap算法中运用Smith-Waterman算法来准确计算两条片段之间可能存在的重叠并对每一个可能的重叠进展打分，同时，设立一个阈值参数W，当重叠的分值大于阈值参数时我们就认为该重叠为一个Word。输入：具有n个顶点的有向图G，指定顶点v和v 第一步：在G中随机生成大量的各种各样的路径 第二步：去掉所有不以顶点v为起点和不以顶点v为终点的路 第三步：去掉所有没有恰含n个顶点的路 第四步：对于这n个顶点中的每一个顶点v，去掉所有不包含顶点v的路 设G=V,E,W其中V,E,W分别图G的顶
