片段组装教材课件

DNA片段组装2012/10/09DNA片段组装2012/10/09内容n多序列比对n片段组装q背景q模型q算法q启发式方法内容多序列比对多序列比对n通过插入空位，使多个序列中大多数相同或相似碱基放入同一列，并保持每个序列碱基顺序不变n5个短序列的比对结果1 23456789 10CT G G A A-G A TCT G G-G A T CA G G A A CG A T CT-G G A CA A G CA G G A A CA A T多序列比对通过插入空位，使多个序列中大多数相同或相似碱基放入多序列比对n序列组装，构建基因组序列n比较基因组学研究，通过不同物种中多条序列的比较，发现保守与变异的部分，了解基因家族的特征，如motif，保守区域等n描述一个同源基因之间的亲缘关系远近，是分子进化分析中构建进化树的必须步骤n构建profile，打分矩阵等多序列比对序列组装，构建基因组序列多序列比对n比对计分qSP(Sum-of-pairs function)度量：列中所有符号对的配对计分和qij为对si,sj的配对比分，k为多序列比对中第k列的配对比分，若p(-,-)=0，则n比对方法：动态规划算法、启发式算法多序列比对比对计分内容n多序列比对n片段组装q背景q模型q算法q启发式方法内容多序列比对片段组装n根据测序的短序列推断目标DNA的完整序列，把碱基对等的列对齐n寻找片段之间的交叠，通过调整片段位置，得到一个排列片段组装根据测序的短序列推断目标DNA的完整序列，把碱基对等鸟枪法测序鸟枪法测序片段组装n具有附加特征的多序列比对n每个片段既可以直接序列加入，也可以逆补序列加入n序列本身通常远远大于比对序列（外部空隙罚分低于内部空隙罚分）片段组装具有附加特征的多序列比对片段组装n1995年，Craig Venter和他的团队利用鸟枪法测序了流感嗜血杆菌（Haemophilus influenzae)，并组装完成，基因组大小为1.8Mn以覆盖整个基因组的BAC收集方式为基础，用鸟枪法测序这些BAC的每一个，整个人类基因组计划因此而增速运转片段组装1995年，Craig Venter和他的团队利用鸟Eugene Myersn为BLAST方法的发展做出了重要贡献n提出了人类基因组的鸟枪法测序(shotgun sequencing）n开发了段枪法测序的装配程序Eugene Myers为BLAST方法的发展做出了重要贡献人类基因组n最初测定人类基因组的策略是把基因组克隆成细菌人工染色体（bacterial artificial chromosome，BAC）n人工构建一个重叠的BAC库，包含整个基因组（30,000BAC）n2001年，人类基因组合作组织和Celera基因组公司同时完成了人类基因组序列的测序工作（故人类基因组有两份稍微不同的版本）人类基因组最初测定人类基因组的策略是把基因组克隆成细菌人工染片段组装背景n理想情形n复杂情形n评估标准n测序补充方法片段组装背景理想情形理想情形n表决序列(consensus sequence)n表决是由一列中所有碱基的多数表决机制决定的理想情形表决序列(consensus sequence)复杂情形n碱基识别错误：替换、插入、删除n重复序列n序列方向未知n覆盖缺乏n其他：宿主或载体DNA污染、嵌合片段复杂情形碱基识别错误：替换、插入、删除碱基识别错误n测序错误率q替换1%3%q插入删除：13ACCGTACCGT-ACCGT-ACCGT-CGTGCCGTGC-CGTGC-CGTGCTTACTTACTTAC-TTAC-T TG GCCGTCCGT-T-TG GCCGT-CCGT-替换替换TTACCGTGCTTACCGTGCACCGTACCGT-ACC-ACC-GT-GT-C CA AGTGCGTGC-C-CA AGTGCGTGCTTACTTACTTAC-TTAC-TACCGTTACCGT-TACC-TACC-GT-GT-插入插入TTACCGTGCTTACCGTGCACCGTACCGT-ACCGT-ACCGT-CGTGCCGTGC-CGTGC-CGTGCTTACTTACTTAC-TTAC-TACGTTACGT-TAC-TAC-GT-GT-删除删除TTACCGTGCTTACCGTGC碱基识别错误测序错误率ACCGT-ACCGT-CGTGC未知朝向序列n片段可能来自DNA的任一单链CACGTCACGT CACGT-CACGT-ACGTACGT-ACGT-ACGT-ACTACGACTACG-CGTAGT-CGTAGT-GTACTGTACT-AGTAC-AGTAC-ACTGAACTGA-ACTGA-ACTGACTGACTGA-CTGA-CTGA CACGTAGTACTGA CACGTAGTACTGA未知朝向序列片段可能来自DNA的任一单链CACGT CAC重复序列n人类基因组中包含许多自身重复的序列n人类T细胞受体基因座包含胰蛋白酶原基因（4kb）的五个相邻定位的重复，每个拷贝间仅有3%5%的不同n人类基因组包含不少于一百万个Alu重复体(300bp）和200,000个LINE重复体n25%的基因有其完全相同的拷贝重复序列人类基因组中包含许多自身重复的序列重复区域nX1和X2近乎相同n顺向重复段n逆向重复段重复区域X1和X2近乎相同逆向重复段覆盖缺乏n位置i的覆盖指在目标序列位置i的片段数量n对每一个连续的覆盖区有一个排列，成为连叠（contig）contig覆盖缺乏位置i的覆盖指在目标序列位置i的片段数量contig覆盖缺乏n一个或多个位置覆盖为0，则缺乏足够的信息来组装完全的目标序列n交叠很少n覆盖不足通常由更多的采样解决Target:覆盖缺乏一个或多个位置覆盖为0，则缺乏足够的信息来组装完全的嵌合片段和DNA污染n来自目标分子不同部分的两个正常片段相连，产生一个不连续的片段，称为嵌合片段n由于纯化不完全，测序片段中出现宿主或载体分子的DNAACCGTACCGT-ACCGT-ACCGT-CGTGCCGTGC-CGTGC-CGTGCTTACTTACTTAC-TTAC-TACCGTTACCGT-TACCGT-TACCGT-TTATGCTTATGCTTACCGTGCTTACCGTGCTTA-TGCTTA-TGC嵌合片段和DNA污染来自目标分子不同部分的两个正常片段相连，片段组装评估n熵计分：列一致性的程度，熵越低越好qmax(E）=-5*0.2*log(0.2)=log5qMin(E)=0n覆盖：一个片段f(l,k)覆盖一列i，则l i kq最大覆盖：5q最小覆盖：1q平均覆盖：43/11片段组装评估熵计分：列一致性的程度，熵越低越好片段组装评估n连锁：片段在排列中的连接方式n片段间应有交叠段，以显示连锁的证据片段组装评估连锁：片段在排列中的连接方式片段组装背景n理想情形n复杂问题n评估参数n测序补充方法片段组装背景理想情形DNA测序补充方法n有向测序：填补鸟枪法测序的剩余小空隙，价格昂贵q从连叠的终端导出一个特殊引物q测序新片段，得到连叠的相邻序列q扩展这个序列q不断重复，直到能够覆盖当前连叠与下个连叠的空隙DNA测序补充方法有向测序：填补鸟枪法测序的剩余小空隙，价格DNA测序补充方法n双端测序q插入片段通常大于读出部分q测序长度是单端测序的两倍q随着反应轮数增加，序列长度和质量均有所下降，为基因组进一步拼接提供定位信息q填补空隙时非常有效DNA测序补充方法双端测序杂交测序法n给定一个短探针（830bp的单链合成DNA片段）和一条单链靶DNA片段，如果探针是靶片段互补链的子序列，靶片段和探针杂交，检测未知的靶DNA并确定它的l-元组组成n1988年，杂交测序（sequencing by hybridization，SBH）出现，将数千个短DNA片段附着在芯片表面杂交测序法给定一个短探针（830bp的单链合成DNA片段）杂交测序法n通用DNA整列包含长度为l的全部4l个探针n用组合算法根据l-元组重构靶DNA序列杂交测序法通用DNA整列包含长度为l的全部4l个探针片段组装模型n最短公共超串q无错且序列方向已知qNP-难题n重构q容许错误和未知序列方向q不能处理重复序列，覆盖缺乏n多连叠q增加了连锁概念q可以处理错误和未知序列方向片段组装模型最短公共超串最短公共超串n给定一个字符串集合F，求出一个最短的字符串S，使得对于所有属于F 的字符串f，S是 f 的超串（或者 f 是 S 的子串）n设F=ACT，CTA，AGT，则S=ACTAGT 是 F 的最短公共超串最短公共超串给定一个字符串集合F，求出一个最短的字符串S，使最短公共超串n最短公共超串未必是真实生物分子n重复区域最短公共超串最短公共超串未必是真实生物分子重构n考虑到片段的误差和未知方向的问题n设 是一个介于0和1之间的数，称串f 是在误差 下S 的近似子串，如果 ds(f,S)f nds为子串编辑距离重构考虑到片段的误差和未知方向的问题重构n重建模型：给定一个字符串集合F，求一个最短的字符串S，使得对于所有属于F的字符串f，下式成立：min(ds(f,S),ds(f,S)f 其中 f 是 f 的反向互补串。重构重建模型：给定一个字符串集合F，求一个最短的字符串S，使LCS与编辑距离nLCS：计分系统及转移公式-ATCG-00000A01-2-2-2T0-21-2-2C0-2-21-2G0-2-2-210 0T TG GC CA AT TA A0 00 00 00 00 00 00 00 0A A0 00 00 00 01 10 01 1T T0 01 11 11 11 12 22 2C C0 01 11 12 22 22 22 2T T0 01 11 12 22 23 33 3G G0 01 12 22 22 23 33 3A A0 01 12 22 23 33 34 4T T0 01 12 22 22 24 44 4LCS与编辑距离LCS：计分系统及转移公式-ATCG-000编辑距离n编辑距离：d(v,w)=n+m-2*s(v,w)-ATCG-01111A10111T11011C11101G111100 0T TG GC CA AT TA A0 00 01 12 23 34 45 56 6A A1 12 23 34 43 34 45 5T T2 21 12 23 34 43 34 4C C3 32 23 32 23 34 45 5T T4 43 34 43 34 43 34 4G G5 54 43 34 45 54 45 5A A6 65 54 45 54 45 54 4T T7 76 65 56 65 54 45 5编辑距离编辑距离：d(v,w)=n+m-2*s(v,w)-子串编辑距离n子串编辑距离dsqS(b)表示b的所有子串集合qd是经典编辑距离qds(a,b)ds(b,a)qa=GCGATAG,b=CAGTCGCTGATCGTACG ds(a,b)=2 =0.29子串编辑距离子串编辑距离ds多连叠模型n如果其最弱连接的交叠长度至少为 t，称一个多重序列比对是 t-contig（t-连叠）n如果能够根据序列片段集合F构造一个t-contig，称F允许一个t-contign多连叠模型：给定一个片段集合F和一个整数 t（0），将F分割为最小数目的子集Ci，1ik，每个Ci允许一个t-contig目标序列目标序列序列碎片序列碎片不连续区域多连叠模型目标序列不连续区域多连叠模型n设设 F=GTAC，TAATG，TGTAA 多连叠模型设 F=GTAC，TAATG，TGTAA 内容n多序列比对n片段组装q背景q模型q算法q启发式方法内容多序列比对片段组装算法n贪婪算法n无环子图方法n适用范围q无错且序列方向已知q集合内无子串片段组装算法贪婪算法交叠多重图n序列片段覆盖图（交叠多重图）OM（F）是一个有向图，其中图中的各个顶点代表F的一个字符串n如果序列f、g F，并且f 的t个字符的后缀与g的t个字符的前缀相同，则图中存在一条权值为t的有向边。n一条通路（不包含重复顶点的路径）构成一个超串交叠多重图序列片段覆盖图（交叠多重图）OM（F）是一个有向图序列片段覆盖图序列片段覆盖图通路nP为OM(F)中的通路，A表示P中所包含的片段集合，由P导出的公共超串成为 S(P)nA的全长、通路的权及超串的长之间的关系n遍历所有顶点的通路即哈密顿通路，最小化|S(P)|即最大化(P)通路P为OM(F)中的通路，A表示P中所包含的片段集合，由P贪婪算法n简化交叠图，对每一对顶点仅考虑权值最大的边，而去掉其它的边，称经过处理后的新图为F的覆盖图，记为OG(F)n核心思想：逐步加入满足哈密顿路径条件的最大权值的边 q无回路q节点出度为1q节点入度为1 贪婪算法简化交叠图，对每一对顶点仅考虑权值最大的边，而去掉其贪婪算法ATCACAGTGCAT22TGCAT ATCA CAGTGCATCAG3CATGAG不一定能得不一定能得到最优解到最优解TGCAT ATCA CATCAGTGCATCAG ATCA期望结果期望结果TGCAT ATCA CATGAGTGCATCATCAG贪婪算法ATCACAGTGCAT22TGCAT3CATGAG无环子图方法n当一个无环图有一个哈密顿通路时，这个通路是唯一的n无环图包含一个哈密顿通路，只能至多有一个源（入度为0的节点）n拓扑排序算法：不断地从图中移出源无环子图方法当一个无环图有一个哈密顿通路时，这个通路是唯一的无环子图方法n利用无环子图求解哈密顿路径，生成节点的拓扑 排序:w z u x ywzuxy43439无环子图方法利用无环子图求解哈密顿路径，生成节点的拓扑 排序无环子图方法n表决序列长度37，最弱连接为3wzuxy43439无环子图方法wzuxy43439贪婪算法n表决序列长度36，最弱连接为0wzuxy43439贪婪算法wzuxy43439片段组装总结n对于给定的片段集合F，首先去掉那些是子串的序列，形成新的片段集合Fn根据F生成交叠多重图n求权值最高的哈密顿路径，由此得到最短的公共超串n形成组装结果片段组装总结对于给定的片段集合F，首先去掉那些是子串的序列，启发式方法n发现交叠n构造排列n计算表决序列启发式方法发现交叠发现交叠n检查所有片段及其逆补片段是是否与某一片段的前缀或后一个片段的后缀匹配n动态规划方法的半全局匹配n发现前缀-后缀相似性：第一个序列（列序列）的后部及第二个序列（行序列）的前部空格没有罚分 发现交叠检查所有片段及其逆补片段是是否与某一片段的前缀或后一发现交叠发现交叠排序片段n构造通路q每个通路有一个对应的补通路q环通常表示出现了重复片段q不均衡的覆盖与重复片段有关排序片段构造通路比对与表决n由带错误的通路构造一个好排列qf和g之间的半全局优化比对q最优比对比对与表决由带错误的通路构造一个好排列比对与表决n表决序列与大多数片段吻合n对已建立的排列进行局部比对比对与表决表决序列与大多数片段吻合nThanks for your attention!nQuestion?Thanks for your attention!习题n第四章习题 2、4、6、12习题第四章习题 2、4、6、12