基因组序列组装的理论与方法简介

Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,基因组序列组装,-,理论与方法,北京大学生物信息中心,科学院北京基因组研究所,李松岗,两种测序策略,分级鸟枪法(,BAC TO BAC),基因组,DNA,切成大片段 构建,BAC,文库,挑选 构建小片段,shotgun,文库 测序,组装,BAC,序列 组装基因组序列,全基因组鸟枪法,基因组,DNA,构建不同长度,shotgun,文库 测序 组装基因组序列,基因组测序与组装示意图,基于BAC方法的 优缺点,优点：组装被局限在,BAC,的范围内，受重复序列影响小，对计算能力要求不高；,缺点：需要大量前期生物学研究工作，效率低，成本高。,全基因组鸟枪法优缺点,优点：不需要生物学前期准备，速度快，成本低；,缺点：组装是在全基因组范围内进行，数据量大，易产生错拼；对计算机软硬件要求均高。,对拼接软件的要求,能充分利用正反向测序的配对信息,避免重复序列造成的错误拼接,能处理数以百万甚至千万计的数据,程序并行化,高效率比对,能够采用全基因组鸟枪法的关键技术进步：,毛细管测序仪的普遍使用,计算机能力的迅速提高,Hierarchical Shotgun(HS),Whole Genome Shotgun(WGS),the sequencing of the human genome is likely to be the only large sequencing project carried to completion by the methods described in this issue,.,Maynard V.Olson,The maps:Clone by clone by clone,Nature 409,816-818(2001),Shotgun,法序列拼接,Consensus,Sequence,Gap,Low Base,Quality,Single,Stranded,Region,Mis-Assembly,(Inverted),术语,鸟枪法测序数据的组装,鸟枪法文库：,目标基因组一定长度随机片段克隆的集合。,正反向测序对：,从同一个克隆片段两端分别测序所得到的一对序列。.,插入片段长度：,克隆载体中插入的外源,DNA,片段长度。,片段连接群(,contig)：,用识别互相重叠的方法对测序数据进行拼接的结果。.,Scaffold:,用正反向测序对连接的非重叠片段连接群。,LW-,洞：,由于没有测序数据覆盖而在组装结果中留下的洞,。,重复序列分析,覆盖度：,基因组被测序数据覆盖的次数。,重复数：,一段,DNA,序列在基因组中出现的次数。,深度：,一段,DNA,序列在鸟枪法测序数据集中出现次数。例如一个转座子在基因组中出现,N,次，测序数据集的覆盖度为,C,则这个转座子的平均深度为,N,C。,20-mer,重复序列：,任何深度超过为该数据集确定的重复序列标准的20-,bpDNA,片段。是数学定义的重复序列。,重复序列洞：,由于屏蔽重复序列而在组装结果中留下的洞。,组装结果的评价标准,N50,大小：,把组装出的,contigs,或,scaffolds,从大到小排列，当其累计长度刚刚超过全部组装序列总长度一半时，最后一个,contig,或,scaffold,的大小。,单碱基错误率：,与参考序列比较后发现的小尺度上的不同所占的比例。所谓小尺度，在这里通常指小于标准测序长度，即500,bp。,实际上常常只是几个碱基。,错误组装的,Contig：,测序数据组装中出现的错误。由定义，它涉及的片段一般大于500-,bp。,包括与参考序列相比，插入、删除，以及在方向和次序上不同的片段。,错误组装的,Scaffold：,把非重叠,contig,连接在一起时出现的错误。包括嵌套，错误的方向和顺序等。,R=3 segments w/repeat-termination,“,overlap-layout-consensus”algorithm explores,R!=exponential number of possible solutions,one Euler Path solution,genome sequence of size G,with 4 repeats,O(G,2,)pair-wise comparison,shotgun library construction,Shotgun Sequencing Assembler Concepts,RePS:,全基因组鸟枪法测序数据组装软件包,特点：通过屏蔽在鸟枪法测序数据中发现的重复序列来完成组装。,RePS,的流程图,RePS2,的新流程图,识别重复序列的数学模型,重复序列识别：,若,repeat,有,m,个拷贝，且已知随机序列覆盖深度为0，1，2的概率：,g,0,，,g,1,，,g,2,，,则一次抽样,repeat,覆盖深度为0，1，2，的概率,P,0,，P,1,，P,2,，,为：,n,次抽样，其中,i,次以上深度在,j,以上的概率,P,ij,设一次抽样深度在,j,以上和以下的概率分别为：,P,j,，P,j+,；,n,次抽样，其中,i,次以上深度在,j,以上则认为是,repeat，,此时犯两类错误的概率 为：,设,repeat,在基因组中的比例为,b，,出现概率为,P，,非,repeat,出现概率为,P,*,，,则：,Tradeoff between contig size and accuracy of assembly,重复序列识别效率,MDR(,数学定义的重复序列)与,BDR(,生物定义的重复序列),BDR,(25%),BDR,(50%?),MDR,(42.2%),重复序列的检测与处理,插入片段大小引起的错误组装,Human 4x,Human 4x+2x,Rice 4.2x,Target region Mb,11.9,11.9,430,Masked sequence,17.2%,17.2%,42.2%,#,of contigs by LW,2018,462,59512,Human 4x,Human 4x+2x,Rice 4.2x,Un-masked Phrap,Max memory use Gb,3.085,x,x,Computer time hrs,48,x,x,Number of contigs,2703,x,x,N50 contig size Kb,7.05,x,x,Phrap error estimate,0.099%(0.086%),x,x,BAC discrepancies,0.066%(0.063%),x,x,Contig mis-assembly,5.77%,x,x,Human 4x,Human 4x+2x,Rice 4.2x,Repeat-masked Phrap,Max memory use Gb,0.614,1.040,50,Computer time hrs,1.8,3.4,79,Number of contigs,3536,2219,167975,N50 contig size Kb,5.35,11.12,3.41,Phrap error estimate,0.091%(0.130%),0.043%(0.096%),0.129%(0.145%),BAC discrepancies,0.077%(0.076%),0.044%(0.059%),0.52%(0.78%),Contig mis-assembly,0.51%,0.68%,0.71%,人与水稻基因组中重复序列分布的差别,Contigs:127,550(N50=6,688 bp),Scaffolds:102,444,(N50=11,764 bp),Quality:,546 bp at Q20,插入片段长度的搭配,一般情况下，可采用如下设计：,插入片段,长度(,Kb),0.5,3,8,20,50,合计,插入片段,覆盖度,1.3,10,10,10,10,折合成功测序覆盖度,1.3,3.33,1.25,0.50,0.20,6.6,CAP3（1999）,特点：,删去,read,两端低质量部分；,利用质量数据，识别重叠序列；进行多序列比对，得到一致序列；,利用正反向数据纠正组装错误，构建,scaffold。,使用情况：,仅使用数个,BAC,进行了测试。,果蝇组装软件（2000）,特点：,组装前数据预处理；,用数据库屏蔽重复序列；,采用类似,BLAST,的方法找出重叠部分；,选择不冲突的重叠构建,contigs，,识别重复序列边界；,用正反向信息构建,scaffolds，,填洞。,使用情况：,用于果蝇基因组组装。,用于人类基因组组装时的改进（2001）,构建,contigs,后，利用一个统计模型识别低拷贝重复序列；,采用两种方式利用已公布的人类基因组计划数据，即,1.把人类基因组计划数据分解成“人工,reads”，,进行组装；,2.利用人类基因组计划数据的定位对,shotgun,数据进行分组，然后组装。,ARACHNE（2002）,特点：,组装前通过多序列比对纠正测序错误；,考虑质量数据，对每对重叠,reads,打分；,通过分析,reads,重叠情况识别重复序列的边界，组装的,contigs,避免越过边界；,识别重复序列,contigs；,构建,scaffolds，,填补空洞。,使用情况：使用数个物种，包括人21、22染色体数据进行了检验。,The Phusion Assembler（2003）,特点：,输入数据包括正反向信息，插入片段长度在2-200,kb,之间；,组装前先对数据进行分组，然后并行处理；,使用,phrap,进行组装，组装过程中利用正反向信息对,contig,进行延伸或打断；,根据重叠合并,contigs；,利用正反向信息构建,scaffolds。,使用情况：,用于小鼠基因组，7.5,x，2.6Gb，479 scaffolds,Table 2.,Insert Sizes,Number of Reads and Effective Clone,Coverage for the Mouse WGS Data Set,Insert size range,Millions of reads,Percent of total,Effective clone,coveragea,Less than 3kb,3.16,9.7%,1.3,3,kb,7 kb,19.32,59.5%,15.3,7,kb,12 kb,2.73,8.4%,5.2,12,kb,50 kb,1.05,3.2%,7.4,50,kb,0.39,1.2%,12.7,Total paired reads,26.65,82.0%,41.9,Unpaired reads,5.85,18.0%,Total reads,32.50,100.0%,欧拉图方法（2001）,特点：,放弃传统方法，用图论解决序列组装问题；,每个,read,作为一个顶点，两个,reads,之间有重叠则有边连接。组装问题就化为找一条仅通过每个顶点一次的通路,Hamilton,问题。,把重复序列视为粘在一起的边，可把上述图简化，问题变为找仅通过每条边一次的通路,Euler,问题。,具体步骤,纠正测序错误,把,read,分为长为,L,的字。如果一个字属于,M,个以上,reads，,称为坚固的；否则称为弱的。纠正错误的算法，就是要通过最少的改变，使弱的字变为坚固的。,通过这种方法，纠正了97.7%的测序错误，把每个,read,的平均错误率从4.8降到了0.11。,构建,de Bruijn,图,顶点：长为,L-1,的字,边：长为,L,的字，代表一条从前一个,L-1,字到后一个,L-1,字的有向边,这样，就把测序数据转换成了,de Bruijn,