生物序列联配中的算法省公共课一等奖全国赛课获奖课件.pptx

《生物序列联配中的算法省公共课一等奖全国赛课获奖课件.pptx》由会员分享，可在线阅读，更多相关《生物序列联配中的算法省公共课一等奖全国赛课获奖课件.pptx（71页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、生物序列联配中算法 张 法第1页提 纲n n背景知识n n序列相同性比较t t两条序列联配问题t t多序列联配问题t t一些启发式算法n n生物序列联配中并行算法第2页DNA(1)脱氧核糖核酸nDNA分子组成uu核甘(nucleotides)t t磷酸盐(phosphate)t t糖(sugar)t t一个碱基腺嘌呤腺嘌呤(A Adenine)denine)鸟嘌呤鸟嘌呤(GGuanine)uanine)胞嘧啶胞嘧啶(C Cytosine)ytosine)胸腺嘧啶胸腺嘧啶(T Thymine)hymine)第3页DNA(2)n n碱基配对标准uuA(腺嘌呤)T(胸腺嘧啶)uuC(鸟嘌呤)G(胞嘧

2、啶)n n一个嘌呤基与一个嘧啶基通 过氢键联结成一个碱基对。n nDNA分子方向性uu53第4页DNA(3)n nDNA双螺旋结构 碱基对之间互补能力碱基对之间互补能力第5页DNA(4)n nDNA复制uu在DNA解旋酶作用 下两条链分离开，分 别作为一个模板，在 聚合酶作用下合成 一条新链。第6页RNA、转录和翻译n nRNA(核糖核酸)：单链结构、尿嘧啶U代替胸腺嘧啶T、位于细胞核和细胞质中。n n转录：DNA链 RNA链 信使RNA(mRNA)，开启子。n n翻译：mRNA上携带遗传信息在核糖体中合成蛋白质过程。第7页变异n n进化过程中因为不正确复制，使DNA内容发生局部改变。n n变

3、异种类主要有以下三种：uu替换(substitution)uu插入或删除(insertion or deletion)indeluu重排(rearrangement)第8页蛋白质n n由氨基酸依次链接形成在生物体中总共有20种氨基酸。n n蛋白有十分复杂三维结构。其三维机构决定了蛋白质功效。第9页基 因n n什么是基因？uuDNA上含有特定功效一个片断，负责一个特定性状表示。普通来讲，一个基因只编码一个蛋白质。第10页基因组n n任何一条染色体上都带有许多基因，一条高等生物染色体上可能带有成千上万个基因，一个细胞中全部基因序列及其间隔序列统称为genomes（基因组）。第11页DNA上基因 基

4、因第12页基因编码n n基因编码是一个逻辑映射，表明存放在DNA和mRNA中基因信息决定什么样蛋白质序列。n n每个碱基三元组称为一个密码子(codon)n n碱基组成三元组排列共有4364种，而氨基酸共有20种类型，所以不一样密码子可能表示同一个氨基酸。第13页带来问题n n序列排列问题 n n基因组重排问题 n n蛋白质结构和功效预测 n n基因(外显子、内含子)查找问题 n n序列装配(Sequence Assembly)问题第14页生物序列相同性比较第15页动机n n在生物学研究中，将未知序列同已知序列进行比较分析已经成为一个强有力研究伎俩，生物学领域中绝大部分问题在计算机科学领域中主

5、要表达为序列或字符串问题。第16页序列联配问题分类 假如两个序列含有足够相同性，则假如两个序列含有足够相同性，则认为二者含有同源性。认为二者含有同源性。n n序列相同性比较(两条序列联配)n n序列分类n n序列排列n n多序列联配第17页两条序列联配问题分类n n全局联配(Global Alignment)n n局部联配(Local Alignment)n n空位处罚(Gap Penalty)第18页全局联配(1)定义n n定义1：两个任意字符 x和y，(x,y)表示表x和y比较时分值。(x,x)=2,(x,y)=(x,-)=(-,y)=-1n n定义2：S=s1sn和T=t1tm，其全局联

6、配A能够用序列S和T来表示，其中：(1)|S|=|T|；(2)将S和T中空字符除去后所得到序列分别为S和T;联配A分值Score为：第19页全局联配(2)原始算法n n输入：序列S和T，其中|S|=|T|=n n n输出：S和T最优联配 n nfor i=0 to n dofor i=0 to n do for (S for (S全部子序列全部子序列A A，其中其中|A|=i)doA|=i)do for(T for(T全部子序列全部子序列B B，其中其中|B|=i)do B|=i)do 第20页全局联配(3)n n动态规划DP(Dynamic Programming)n nSmith-Wate

7、rman 算法uu计算出两个序列相同分值，存于一个矩阵中。(相同度矩阵、DP矩阵)uu依据此矩阵，按照动态规划方法寻找最优联配序列。第21页全局联配(4)n n前提条件n n递归关系第22页全局联配(5)n n在得到相同度矩阵后，经过动态规划回溯（Traceback）方法可取得序列最优联配序列。例：S=“a c g c t g”和T=“c a t g t”(x,x)=2,(x,y)=(x,-)=(-,y)=-1第23页 j ji i0 01 1c c2 2a a3 3t t4 4g g5 5t t 0 00 0-1-1-2-2-3-3-4-4-5-5 1 1 a a-1-1-1-11 10 0

8、-1-1-2-2 2 2 c c-2-21 10 00 0-1-1-2-2 3 3 g g-3-30 00 0-1-12 21 1 4 4 c c-4-4-1-1-1-1-1-11 11 1 5 5 t t-5-5-2-2-2-21 10 03 3 6 6 g g-6-6-3-3-3-30 03 32 2第24页n n三种可能最优联配序列：1.S:a c g c t g -T:-c a t g t 2.S:a c g c t g -T:-c a t g t 3.S:-a c g c t g T:c a t g -t -第25页局部联配(1)n n两条序列在一些局部区域内含有很高相同度。n n在

9、生物学中局部联配比全局联配更含有实际意义。uu两条DNA长序列，可能只在很小区域内(密码区)存在关系。uu不一样家族蛋白质往往含有功效和结构上相同一些区域。第26页局部联配(2)n n前提条件前提条件：V(i,0)=0;V(0,j)=0;n n递归关系递归关系：找出i*和j*，使得：第27页局部联配(3)n n对全局联配策略稍作修改可得到局部最优联配算法。n n联配路径不需要抵达搜索图尽头,假如某种联配分值不会因为增加联配数量而增加时，这种联配就是最正确。n n依赖于记分系统性质：因为某种路径记分会在不匹配序列段降低,当分值降为零时，路径延展将会终止，一个新路径就会产生。第28页局部联配(4)

10、S=“a b c x d e x”，T=“x x x c d e”记分函数(x,y)：(x,x)=2,(x,y)=(x,-)=(-,y)=-1第29页 j j i i0 01 1x x2 2x x3 3x x4 4c c5 5d d6 6e e 0 0 0 00 00 00 00 00 00 0 1 1 a a0 00 00 00 00 00 00 0 2 2 b b0 00 00 00 00 00 00 0 3 3 c c0 00 00 00 02 21 10 0 4 4 x x0 02 22 22 21 11 10 0 5 5 d d0 01 11 11 11 13 32 2 6 6 e

11、e0 00 00 00 00 02 25 5 7 7 x x0 02 22 22 21 11 14 4第30页n nS=“a b c x d e x”，T=“x x x c d e”局部最优联配是：c x d e c-d e或 x-d e x c d e 第31页空位处罚(1)n n空位:序列中任意连续尽可能长空格。n n空位引入是为了赔偿那些插入或缺失，不过在序列联配中引入空位不能太多，不然会使序列排列变得面目全非。n n每引入一个空位，联配分值都会有所扣除，常见罚分规则主要有两种：uu空位权值恒定模型uu仿射空位处罚模型 第32页空位处罚(2)n n空位权值恒定模型：在每个空位中空格分值为

12、零，即：(x,-)=(-,y)=0 n n联配分值为：其中，Wg为开放一个空位罚分 第33页空位处罚(3)n n仿射空位处罚模型(Affine Gap Model)用一个附加罚分百分比去乘空位长度 Wg+qWs n n联配分值为：第34页空位处罚(4)初始条件初始条件：V V(0,0)=0(0,0)=0;V V(i i,0)=,0)=E E(i,i,0)=0)=WWg g+iWiWs s;V V(0,(0,j j)=)=F F(0(0,j,j)=)=WWg g+jWjWs s;递归条件递归条件：V V(i,ji,j)=)=maxmax G G(i,ji,j),),E E(i,ji,j),),F

13、 F(i,ji,j);G G(i,ji,j)=)=V V(i i-1-1,j,j-1)+(-1)+(S S i i,T T j j);E E(i,ji,j)=)=maxmax E E(i,ji,j-1)+-1)+WWs s,V V(i,ji,j-1)+-1)+WWg g+WWs s F F(i,ji,j)=)=maxmax F F(i i-1-1,j,j)+)+WWs s,V V(i i-1-1,j,j)+)+WWg g+WWs s.第35页n n利用动态规划计算序列最优联配算法复杂度分析：t t时间复杂度；O(nm)t t空间复杂度：O(n+m)第36页最新相关研究n n在动态规划算法基础上

14、提出了一个新方法，处理在序列局部联配最优排列中经常出现马赛克问题(在最优排列中间经常出现相同度很低保守区域)n n把hash表方法引入到基因组序列局部联配问题中，同时提升了原有算法效率和质量 第37页多序列联配(1)n n两条序列联配问题普通化推广n n动机：携带更多消息、生物学家一个主要伎俩。n nDNA或蛋白质数据库容量指数级增加，即使使用很简单记分函数也极难找到一个在有效时间内处理方法，而几乎全部近似算法和许多启发式算法，实际上都是在算法计算速度和取得最正确联配结果敏感性之间寻找一个权衡（tradeoff）策略。第38页多序列联配(2)n nrigorous算法uu两条序列 多条序列，N

15、P hardn ntree_based算法和 iterative算法uu首先从序列中找出两条相同度最大联配，然后按摄影同度递减次序连续添加一些序列到最优联配序列中。uu序列非常靠近或属于一个同源家族 uu原始算法基础上近似算法，不过它们也是非常耗时。第39页多序列联配(3)n n记分方法：用函数(x,y)来计算字符x和y之间距离，两个序列联配距离分值我们用V来表示：n nk条序列联配分值：为k条序列中任意两条序列(共有Ck2条)分值(距离)V之和，用SP (Sum_of_Pairs)来表示:第40页多序列联配(4)n n中心星算法中心星算法输入：一组含有输入：一组含有k k条序列集合条序列集合

16、 uu找出序列找出序列S St t，S St t，使得使得 ititD D(S Si i,S,St t)值最小，令值最小，令A A=S St t uu逐次地添加逐次地添加S Si i-S St t 到到A A中，并使中，并使S Si i与与S St t联配值最小；联配值最小；假设假设S S1 1，S S2 2，S Si i-1-1已添加到已添加到A A中，因为在分别和中，因为在分别和S St t进进行联配过程中需要加入一些空格，故此时行联配过程中需要加入一些空格，故此时A A为：为：A A=S S1 1，S S2 2，S Si i-1-1，S S t t。添加添加S Si i到到A A中，按照

17、两条序列中，按照两条序列联配动态规划算法比较联配动态规划算法比较S S t t和和S Si i，分别产生新序列分别产生新序列S St t 和和S Si i，再按照再按照S St t 中添加空格位置调整序列中添加空格位置调整序列S S1 1，S S2 2，S Si+i+1 1 为为S S1 1，S S2 2，S Si i-1-1，并用并用S St t 替换替换S St t。第41页n n借助硬件来完成动态规划算法 n n采取并行固件，把问题有效地分配到多个处理器上运行，最终再把各处理器运算结果搜集起来 n n借助于一些比最初动态规划算法更加快启发式算法。以降低运算结果质量为代价来提升计算速度。第

18、42页启发式算法-FASTAn n基本思想是：一个能够揭示出真实序列关系联配最少包含一个两个序列都拥有字(片断)，把查询序列中所用字编成索引，然后在数据库搜索时查询这些索引，以检索出可能匹配，这么那些命中字很快被判定出来。第43页1.1.确定参数ktup，在两个序列中查找长度为ktup、相匹配片段(增强点)。连续增强点在动态规划矩阵中主对角线附近。为了提升速度，能够经过查询表格或hash表来完成，然后在表格中搜索与另一条序列相匹配、长度为ktup片段。2.2.在同一条对角线中临近增强点成为一个增强段。每一个增强点都赋予一个正分值，一个增强段中相邻两个增强点之间不匹配区域赋予一定负值。一个增强段

19、对应于一段相匹配子序列，分值最高段被标识为init1。第44页3.引 入 indel。把 那 些 没 有 重 合(non-overlap)增强段拼接起来(增强段分值之和减去空位处罚)。分值最高区域记为initn。4.对最有可能匹配序列深入评分：以增强段init1所在对角线为中心，划分出一个较狭窄对角线带，利用S-W算法，来取得分值最高局部联配，记作opt。5.按照initn和opt分值，对分值最高序列再进行一次S-W联配。FASTA对每一个检索到联配都提供一个统计学显著性评定，以判断该联配意义。第45页n nFASTA对DNA序列搜索结果要比对蛋白质序列搜索结果更敏感，因为它对数据库每一次搜索

20、都只有一个最正确联配，这么对于蛋白质序列而言，一些有意义联配可能被错过。第46页启发式算法-BLASTn n基本思想是：经过产生数量更少但质量更加好增强点来提升速度。n nBALST算法是建立在严格统计学基础之上。它集中于发觉含有较高相同性局部联配，且局部联配中不能含有空位。n n因为局部联配限制条件，在大多数情况下联配会被分解为若干个显著HSP(High-score Sequence Pairs)。第47页1.首先确定一个终止值S、步长参数w和一个阀值t，S值通常是基于统计学原理指明一个预期终止E值，然后软件会在考虑搜索背景性质基础上计算出适当S值。使要联配序列中包含一个分值大于SHSP。2

21、.引入邻近字串思想：不需要字串确切地匹配，当有一个字串分值高于t时，BALST就宣称找到了一个选中字串。为了提升速度，允许较长字串长度W。W值极少改变，这么，t值就成为权衡速度和敏感度参数。第48页3.一个字串选中后，程序会进行没有空位局部寻优，联配最低分值是S，当联配延伸时会碰到一些负分值，使得联配分值下降，当下降分值小于S时，命中延伸就会终止。这么系统会降低消耗于毫无指望选中延伸时间，使系统性能得以改进。第49页PSI-BLASTn nPosition Specific Iterated BLASTn n在1997年提出了对BLAST程序改进算法，在序列联配中允许出现空位，提升了搜索速度、

22、敏感度和实用性。uu对一个选中字串长度标准延伸 uu利用profile(表头文件)数据结构来进行搜索 第50页n n在利用动态规划矩阵进行联配时，以步长为2w来搜索每一条对角线，这么能够找到一些长度为2w选中字。n n改进算法中允许位于不一样对角线两个片段拼接在一起。在拼接过程中要包括到indel操作，与FASTA算法只产生一个最正确联配不一样，位于不一样对角线两个片段拼接在一起前提条件是：拼接后片段分值大于某一个终止值。第51页n n执行通常BLAST算法，使用一个不一样记分方式，依据高度显著联配(HSPs)最高分值建立一个最初profile。n n依据该profile重复利用BLAST算法

23、对数据库进行搜索，这一步实际上是依据表头文件统计结果扩展局部联配。这一过程是重复进行，直到再没有发觉新有意义匹配为止。因为在每一轮都会有新片段加入，所以在操作过程中profile需要在每一个循环结束之后更新。第52页生物序列联配中并行算法第53页两条序列联配并行算法 uu依据序列相同性比较，找出二者最正确匹配 uu找出从一条序列转化到另一条序列最正确路径n n关键：动态规划第54页Lander处理方法n n假如已知第i-1和 i-2行反对角线上 各项值，那么 第i行反对角线上 各项值能够并 行计算。?第55页D12D21D31D11D22D13Dm,n处理器01m时间步12m+n-2m+n-1

24、第56页S-W并行处理Row-Wavefront算法和Diagonal Wavefront算法 Row-Wavefront算法是让每个处理器次序处理动态规划矩阵中每一行，当一个处理器检测到它所需要上一行矩阵元素还没有计算出来时，该处理器就阻塞自己，直到所需要元素计算出来。处理器1处理器2处理器3序列S序列T第57页S-W并行处理Row-Wavefront算法和Diagonal Wavefront算法 Diagonal Wavefront算法中全部处理器同时沿着矩阵一条反对角线进行计算，当一条反对角线元素全部计算完，才转到下一条反对角线计算。当一个处理器空闲时候，它从当前反对角线上寻找一个还没有

25、计算元素进行计算。这种算法没有严格处理器计算次序序列T序列S第58页Huang处理方法n n采取了分而治之策略对回溯算法进行了改进:按照中间一条反对角线来分割动态规划矩阵。(0,0)r(k,l)(m,n)第59页动态规划并行计算n n基于流水线动态规划算法n n反对角线动态规划算法 n n反对角线分块动态规划算法 uu粗粒度分块策略 uu细粒度分块策略uuH-V(Horizontal-Vertical)分块策略第60页基于流水线动态规划算法第61页反对角线分块动态规划算法 n n粗粒度分块策略第62页n n细粒度分块策略第63页n nH-V(Horizontal-Vertical)分块策略第6

26、4页利用前趋计算并行算法 n nPrefix Computation 第65页多序列联配并行算法 n n利用预测计算（Speculative computation）技术并行算法 n n分而治之策略并行算法 第66页Berger_Munson算法 best_score=initial_score();while(stop criteria is not met)1 current_score=calculate(seq,gap_positions);2 flag=decide(current_score,best_score);3 seq=modify(seq,flag,gap_positio

27、ns);第一步：首先输入n条序列，任意分成两组。然后开始计算这两组序列之间两条序列联配 分 值，在 这 一 步 中 新 空 位 位 置gap_positions被保留下来以备第三步调用。第二步：设置一个标识flag，假如一个新联配分值高于当前最正确联配队列分值，则flag标识为A(Accepted)，不然标识为R(Rejected)；第三步：假如在第二步中flag标识为A，则依据第一步中gap_positions来修改当前联配队列，以作为下一次迭代初始值，同时更新联配队列分值，当连续碰到q个R时，算法结束。第67页Berger_Munson算法并行化n n每一次迭代内三个阶段是相互依赖；第i次迭代可能会用到第i-1次迭代结果。n n预测计算基本思想是：利用当前状态输入参数来推断未来状态计算结果。n n假如有连续迭代被标识为R，那么这些迭代之间是相互独立，能够并行处理。第68页迭代次数迭代次数1 2 3 4 5 6 71 2 3 4 5 6 7结果序列结果序列AAAAARAAARRARRRARRRARRRARRRRRAAAAARAAARRARRRARRRARRRARRRRR第69页采取分而治之策略并行算法 第70页谢谢各位！第71页