chap4_DNA片段组装

DNA片段组装2012/10/09内容多序列比对片段组装背景模型算法启发式方法多序列比对通过插入空位，使多个序列中大多数相同或相似碱基放入同一列，并保持每个序列碱基顺序不变5个短序列的比对结果12345678910ⅠCTGGAA-GATⅡCTGG---GATⅢCAGGAACGATⅣCT-GGACAAGⅤCAGGAACAAT多序列比对序列组装，构建基因组序列比较基因组学研究，通过不同物种中多条序列的比较，发现保守与变异的部分，了解基因家族的特征，如motif，保守区域等描述一个同源基因之间的亲缘关系远近，是分子进化分析中构建进化树的必须步骤构建profile，打分矩阵等多序列比对比对计分SP(Sum-of-pairsfunction)度量：列中所有符号对的配对计分和αij为α对si,sj的配对比分，αk为多序列比对中第k列的配对比分，若p(-,-)=0，则比对方法：动态规划算法、启发式算法()()()ijkijkSPscorescoreSPscore(,,,)(,)(,)(,)(,)(,)(,)SPscoreIIVPIPIIPIVPIPIVPIV内容多序列比对片段组装背景模型算法启发式方法片段组装根据测序的短序列推断目标DNA的完整序列，把碱基对等的列对齐寻找片段之间的交叠，通过调整片段位置，得到一个排列鸟枪法测序片段组装具有附加特征的多序列比对每个片段既可以直接序列加入，也可以逆补序列加入序列本身通常远远大于比对序列（外部空隙罚分低于内部空隙罚分）片段组装1995年，CraigVenter和他的团队利用鸟枪法测序了流感嗜血杆菌（Haemophilusinfluenzae)，并组装完成，基因组大小为1.8M以覆盖整个基因组的BAC收集方式为基础，用鸟枪法测序这些BAC的每一个，整个人类基因组计划因此而增速运转EugeneMyers为BLAST方法的发展做出了重要贡献提出了人类基因组的鸟枪法测序(shotgunsequencing）开发了段枪法测序的装配程序人类基因组最初测定人类基因组的策略是把基因组克隆成细菌人工染色体（bacterialartificialchromosome，BAC）人工构建一个重叠的BAC库，包含整个基因组（30,000BAC）2001年，人类基因组合作组织和Celera基因组公司同时完成了人类基因组序列的测序工作（故人类基因组有两份稍微不同的版本）片段组装背景理想情形复杂情形评估标准测序补充方法理想情形表决序列(consensussequence)表决是由一列中所有碱基的多数表决机制决定的复杂情形碱基识别错误：替换、插入、删除重复序列序列方向未知覆盖缺乏其他：宿主或载体DNA污染、嵌合片段碱基识别错误测序错误率替换1%~3%插入删除：1‰~3‰ACCGT--ACCGT--CGTGC----CGTGCTTACTTAC-----TGCCGT-TGCCGT--替换TTACCGTGCACCGT--ACC-GT--CAGTGC----CAGTGCTTACTTAC------TACCGT-TACC-GT--插入TTACCGTGCACCGT--ACCGT--CGTGC----CGTGCTTACTTAC-----TACGT-TAC-GT--删除TTACCGTGC未知朝向序列片段可能来自DNA的任一单链CACGT→CACGT--------ACGT→-ACGT--------ACTACG←--CGTAGT-----GTACT←-----AGTAC---ACTGA→--------ACTGACTGA→---------CTGACACGTAGTACTGA重复序列人类基因组中包含许多自身重复的序列人类T细胞受体基因座包含胰蛋白酶原基因（4kb）的五个相邻定位的重复，每个拷贝间仅有3%~5%的不同人类基因组包含不少于一百万个Alu重复体(300bp）和200,000个LINE重复体25%的基因有其完全相同的拷贝重复区域X1和X2近乎相同顺向重复段逆向重复段覆盖缺乏位置i的覆盖指在目标序列位置i的片段数量对每一个连续的覆盖区有一个排列，成为连叠（contig）contig覆盖缺乏一个或多个位置覆盖为0，则缺乏足够的信息来组装完全的目标序列交叠很少覆盖不足通常由更多的采样解决Target:嵌合片段和DNA污染来自目标分子不同部分的两个正常片段相连，产生一个不连续的片段，称为嵌合片段由于纯化不完全，测序片段中出现宿主或载体分子的DNAACCGT--ACCGT--CGTGC----CGTGCTTACTTAC-----TACCGT-TACCGT--TTATGCTTACCGTGCTTA---TGC片段组装评估熵计分：列一致性的程度，熵越低越好max(E）=-5*0.2*log(0.2)=log5Min(E)=0覆盖：一个片段f([l,k])覆盖一列i，则l≤i≤k最大覆盖：5最小覆盖：1平均覆盖：43/11log(,,,,)cccEppcATCG片段组装评估连锁：片段在排列中的连接方式片段间应有交叠段，以显示连锁的证据片段组装背景理想情形复杂问题评估参数测序补充方法DNA测序补充方法有向测序：填补鸟枪法测序的剩余小空隙，价格昂贵从连叠的终端导出一个特殊引物测序新片段，得到连叠的相邻序列扩展这个序列不断重复，直到能够覆盖当前连叠与下个连叠的空隙DNA测序补充方法双端测序插入片段通常大于读出部分测序长度是单端测序的两倍随着反应轮数增加，序列长度和质量均有所下降，为基因组进一步拼接提供定位信息填补空隙时非常有效杂交测序法给定一个短探针（8~30bp的单链合成DNA片段）和一条单链靶DNA片段，如果探针是靶片段互补链的子序列，靶片段和探针杂交，检测未知的靶DNA并确定它的l-元组组成1988年，杂交测序（sequencingbyhybridization，SBH）出现，将数千个短DNA片段附着在芯片表面杂交测序法通用DNA整列包含长度为l的全部4l个探针用组合算法根据l-元组重构靶DNA序列片段组装模型最短公共超串无错且序列方向已知NP-难题重构容许错误和未知序列方向不能处理重复序列，覆盖缺乏多连叠增加了连锁概念可以处理错误和未知序列方向最短公共超串给定一个字符串集合F，求出一个最短的字符串S，使得对于所有属于F的字符串f，S是f的超串（或者f是S的子串）设F={ACT，CTA，AGT}，则S=ACTAGT是F的最短公共超串最短公共超串最短公共超串未必是真实生物分子重复区域重构考虑到片段的误差和未知方向的问题设是一个介于0和1之间的数，称串f是在误差下S的近似子串，如果ds(f,S)fds为子串编辑距离重构重建模型：给定一个字符串集合F，求一个最短的字符串S，使得对于所有属于F的字符串f，下式成立：min(ds(f,S),ds(f’,S))f其中f’是f的反向互补串。LCS与编辑距离LCS：计分系统及转移公式-ATCG-00000A01-2-2-2T0-21-2-2C0-2-21-2G0-2-2-210TGCATA00000000A0000101T0111122C0112222T0112233G0122233A0122334T01222441,,,11,1max1ijijijijijSSSSifvw编辑距离编辑距离：d(v,w)=n+m-2*s(v,w)-ATCG-01111A10111T11011C11101G111101,,,11,11min1ijijijijijddddifvw0TGCATA00123456A1234345T2123434C3232345T4343434G5434545A6545454T7656545子串编辑距离子串编辑距离dsS(b)表示b的所有子串集合d是经典编辑距离ds(a,b)≠ds(b,a)a=GCGATAG,b=CAGTCGCTGATCGTACGds(a,b)=2=0.29()(,)min(,)ssSbdabdas多连叠模型如果其最弱连接的交叠长度至少为t，称一个多重序列比对是t-contig（t-连叠）如果能够根据序列片段集合F构造一个t-contig，称F允许一个t-contig多连叠模型：给定一个片段集合F和一个整数t（0），将F分割为最小数目的子集Ci，1ik，每个Ci允许一个t-contig目标序列序列碎片不连续区域多连叠模型设F={GTAC，TAATG，TGTAA}内容多序列比对片段组装背景模型算法启发式方法片段组装算法贪婪算法无环子图方法适用范围无错且序列方向已知集合内无子串交叠多重图序列片段覆盖图（交叠多重图）OM（F）是一个有向图，其中图中的各个顶点代表F的一个字符串如果序列f、gF，并且f的t个字符的后缀与g的t个字符的前缀相同，则图中存在一条权值为t的有向边。一条通路（不包含重复顶点的路径）构成一个超串序列片段覆盖图通路P为OM(F)中的通路，A表示P中所包含的片段集合，由P导出的公共超串成为S(P)A的全长、通路的权及超串的长之间的关系遍历所有顶点的通路即哈密顿通路，最小化|S(P)|即最大化ω(P)()()aAaPSP贪婪算法简化交叠图，对每一对顶点仅考虑权值最大的边，而去掉其它的边，称经过处理后的新图为F的覆盖图，记为OG(F)核心思想：逐步加入满足哈密顿路径条件的最大权值的边无回路节点出度为1节点入度为1贪婪算法ATCACAGTGCAT22TGCATATCACAGTGCATCAG3CATGAG不一定能得到最优解TGCATATCACATCAGTGCATCAGATCA期望结果TGCATATCACATGAGTGCATCATCAG无环子图方法当一个无环图有一个哈密顿通路时，这个通路是唯一的无环图包含一个哈密顿通路，只能至多有一个源（入度为0的节点）拓扑排序算法：不断地从图中移出源无环子图方法利用无环子图求解哈密顿路径，生成节点的拓扑排序:w→z→u→x→ywzuxy43439无环子图方法表决序列长度37，最弱连接为3wzuxy43439贪婪算法表决序列长度36，最弱连接为0wzuxy43439片段组装总结对于给定的片段集合F，首先去掉那些是子串的序列，形成新的片段集合F’根据F’生成交叠多重图求权值最高的哈密顿路径，由此得到最短的公共超串形成组装结果启发式方法发现交叠构造排列计算表决序列发现交叠检查所有片段及其逆补片段是是否与某一片段的前缀或后一个片段的后缀匹配动态规划方法的半全局匹配发现前缀-后缀相似性：第一个序列（列序列）的后部及第二个序列（行序列）的前部空格没有罚分发现交叠排序片段构造通路每个通路有一个对应的补通路环通常表示出现了重复片段不均衡的覆盖与重复片段有关比对与表决由带错误的通路构造一个好排列f和g之间的半全局优化比对最优比对比对与表决表决序列与大多数片段吻合对已建立的排列进行局部比对Thanksforyourattention!Question?习题第四章习题2、4、6、12