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

基因组序列组装 -理论与方法,北京大学生物信息中心 科学院北京基因组研究所 李松岗 两种测序策略,分级鸟枪法(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,Mis-Assembly (Inverted),术语 鸟枪法测序数据的组装 鸟枪法文库：目标基因组一定长度随机片段克隆的集合。 正反向测序对： 从同一个克隆片段两端分别测序所得到的一对序列。. 插入片段长度： 克隆载体中插入的外源DNA片段长度。 片段连接群(contig)：用识别互相重叠的方法对测序数据进行拼接的结果。. Scaffold: 用正反向测序对连接的非重叠片段连接群。 LW-洞：由于没有测序数据覆盖而在组装结果中留下的洞。,重复序列分析 覆盖度： 基因组被测序数据覆盖的次数。 重复数： 一段DNA序列在基因组中出现的次数。 深度：一段DNA序列在鸟枪法测序数据集中出现次数。例如一个转座子在基因组中出现N次，测序数据集的覆盖度为C, 则这个转座子的平均深度为NC。 20-mer 重复序列：任何深度超过为该数据集确定的重复序列标准的20-bpDNA片段。是数学定义的重复序列。 重复序列洞： 由于屏蔽重复序列而在组装结果中留下的洞。,组装结果的评价标准 N50 大小： 把组装出的contigs 或 scaffolds从大到小排列，当其累计长度刚刚超过全部组装序列总长度一半时，最后一个contig或scaffold的大小。 单碱基错误率： 与参考序列比较后发现的小尺度上的不同所占的比例。所谓小尺度，在这里通常指小于标准测序长度，即500bp。实际上常常只是几个碱基。 错误组装的Contig： 测序数据组装中出现的错误。由定义，它涉及的片段一般大于500-bp。包括与参考序列相比，插入、删除，以及在方向和次序上不同的片段。 错误组装的Scaffold：把非重叠contig连接在一起时出现的错误。包括嵌套，错误的方向和顺序等。,Shotgun Sequencing Assembler Concepts,RePS: 全基因组鸟枪法 测序数据组装软件包,特点：通过屏蔽在鸟枪法测序数据中发现的重复序列来完成组装。,RePS的流程图,RePS2的新流程图,识别重复序列的数学模型,重复序列识别：,若repeat有m个拷贝，且已知随机序列覆盖深度为0，1，2的概率：g0 ， g1 ， g2 ，则一次抽样repeat覆盖深度为0，1，2，的概率P0， P1， P2，为：,n次抽样，其中i次以上 深度在j以上的概率Pij,设一次抽样深度在j以上和以下的概率分别为：Pj，Pj+；,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%),重复序列的检测与处理,插入片段大小引起的错误组装,人与水稻基因组中重复序列分布的差别,Contigs:127,550 (N50=6,688 bp),Scaffolds: 102,444 (N50=11,764 bp),Quality: 546 bp at Q20,插入片段长度的搭配,一般情况下，可采用如下设计：,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-200kb之间； 组装前先对数据进行分组，然后并行处理； 使用phrap进行组装，组装过程中利用正反向信息对contig进行延伸或打断； 根据重叠合并contigs； 利用正反向信息构建scaffolds。 使用情况： 用于小鼠基因组，7.5x，2.6Gb，479 scaffolds,Table 2. Insert Sizes, Number of Reads and Effective Clone Coverage for the Mouse WGS Data Set,欧拉图方法（2001）,特点： 放弃传统方法，用图论解决序列组装问题； 每个read作为一个顶点，两个reads之间有重叠则有边连接。组装问题就化为找一条仅通过每个顶点一次的通路Hamilton问题。 把重复序列视为粘在一起的边，可把上述图简化，问题变为找仅通过每条边一次的通路Euler问题。,具体步骤,纠正测序错误 把read分为长为 L 的字。如果一个字属于M个以上reads，称为坚固的；否则称为弱的。纠正错误的算法，就是要通过最少的改变，使弱的字变为坚固的。 通过这种方法，纠正了97.7%的测