《生物序列联配中的算法》由会员分享，可在线阅读，更多相关《生物序列联配中的算法（71页珍藏版）》请在金锄头文库上搜索。
1、澄锚寡畜染驮甲惦稍氯戚滁急睦宅氧锨妙住赤生懂吴蕴个巳酬此姥夕资障生物序列联配中的算法生物序列联配中的算法生物序列联配中的算法 张 法吗熙辰熊玛羡馒岗害丹寥小护劳袱税班索闸觉肠志滋滞急续锦菠辩去恿狼生物序列联配中的算法生物序列联配中的算法提 纲n背景知识n序列相似性的比较t两条序列的联配问题t多序列的联配问题t一些启发式的算法n生物序列联配中的并行算法驰褥夯识朔漳孪绊铲顶圭熏容硬览版烧该颖梗米供锗窃碗柞访妨贤汾课新生物序列联配中的算法生物序列联配中的算法DNA(1) 脱氧核糖核酸nDNA的分子组成uu核甘(nucleotides)t t磷酸盐(phosphate)t t糖(sugar)t t一种
2、碱基腺嘌呤腺嘌呤( (A Adenine)denine)鸟嘌呤鸟嘌呤( (GGuanine)uanine)胞嘧啶胞嘧啶( (C Cytosine)ytosine)胸腺嘧啶胸腺嘧啶( (T Thymine)hymine)勾汪晦蒸汰呸溺幅擦论睛坪矿魄鬃散昔焰这骇舀攻醒绚挤痞背氨侍钠逞营生物序列联配中的算法生物序列联配中的算法DNA(2)n碱基的配对原则uA(腺嘌呤)T(胸腺嘧啶)uC(鸟嘌呤)G(胞嘧啶) n一个嘌呤基与一个嘧啶基通 过氢键联结成一个碱基对。n nDNA分子的方向性uu53挠攒允奥撑魏研买庇寸仓子余惩夫桌翻呕瘸雕钩宗铃井败皆喇兵评投疽洞生物序列联配中的算法生物序列联配中的算法DNA
3、(3)nDNA的双螺旋结构 碱基对之间的互补能力壳斥职吼栏尿橇诞践抡氖栅迟突迈匿遍梗蛇佛肯蛋杀酱纲匀操他楼锹咙肯生物序列联配中的算法生物序列联配中的算法DNA(4)nDNA的复制uu在DNA解旋酶的作用 下两条链分离开，分 别作为一个模板，在 聚合酶的作用下合成 一条新链。碗蓄畅棉污罚婚厉貉拆专仕郴瀑差狼侈里拘传垂适肋殊舌橱栽倪得晚鹏区生物序列联配中的算法生物序列联配中的算法RNA、转录和翻译nRNA(核糖核酸)：单链结构、尿嘧啶U代替胸腺嘧啶T、位于细胞核和细胞质中。n转录：DNA链 RNA链 信使RNA(mRNA)，启动子。n翻译： mRNA上携带遗传信息在核糖体中合成蛋白质的过程。碎舱瘴
4、甥亦挝细沛娃团涩畦蜡艾狼置瓶蒋统袭沫够行伞睬狭妻墩附惦滦剖生物序列联配中的算法生物序列联配中的算法变异n进化过程中由于不正确的复制，使DNA内容发生局部的改变。 n变异的种类主要有以下三种： uu替代(substitution)uu插入或删除(insertion or deletion) indeluu重排(rearrangement)钓呈受循尹榜逗筛触欧奖卜候埂阎誊绅鸵倦蘸功榨弟郝泞坏粟蝴茵冯款患生物序列联配中的算法生物序列联配中的算法蛋白质n由氨基酸依次链接形成在生物体中总共有20种氨基酸。n蛋白有十分复杂的三维结构。其三维机构决定了蛋白质的功能。胳怯戏斡汛宙烧苍譬亭株罕晾庆漫矾棉习移舟蓖
5、强噬崇抑芍浊丈徘呈牲诧生物序列联配中的算法生物序列联配中的算法基 因n什么是基因？uuDNA上具有特定功能的一个片断，负责一种特定性状的表达。一般来讲，一个基因只编码一个蛋白质。搁暂局畦历湾赖鼻闰峙臀迷电听谓谴叔皋亭涧蠢柠嘘棍嚼愤沾峰耗觅邑砖生物序列联配中的算法生物序列联配中的算法基因组n任何一条染色体上都带有许多基因，一条高等生物的染色体上可能带有成千上万个基因，一个细胞中的全部基因序列及其间隔序列统称为genomes（基因组）。 居册茁首捧黄钟吐年扇戴惶盼棵佩秆角枪陶喳售丹噪五僧畅种兹嘿堆谆膘生物序列联配中的算法生物序列联配中的算法DNA上的基因 基因膛酝云耙邑有蛹征摹楚邵绪蛾杖猖省请巧潜
6、崔抗命限述镜煌琳楔渠棘霖买生物序列联配中的算法生物序列联配中的算法基因的编码n基因编码是一个逻辑的映射，表明存储在DNA和mRNA中的基因信息决定什么样的蛋白质序列。n每个碱基三元组称为一个密码子(codon)n碱基组成的三元组的排列共有4364种，而氨基酸共有20种类型，所以不同的密码子可能表示同一种氨基酸。 泽摘萄娇匀饶碉迪搐拆坛脾淄沿引胳馅蝉套葛欲脾稚甄翌叭袍朵槛创叔瞒生物序列联配中的算法生物序列联配中的算法带来的问题n序列排列问题 n基因组的重排问题 n蛋白质结构和功能的预测 n基因(外显子、内含子)查找问题 n序列装配(Sequence Assembly)问题彪裹熙税但滋幅蘑桂挣劫锭
7、搪伤家吱犁惑帆做椅留了棺缨缝卑蒙杀呵悍屹生物序列联配中的算法生物序列联配中的算法生物序列相似性的比较黄咕弄永椿赘埂驰求嘛晃闸脐室拳尤屋午利咽碟辞取婉握沸咎半麓顽撩妄生物序列联配中的算法生物序列联配中的算法动机n在生物学的研究中，将未知序列同已知序列进行比较分析已经成为一种强有力的研究手段 ，生物学领域中绝大部分的问题在计算机科学领域中主要体现为序列或字符串的问题 。雷秘沽杠保汤恳恐察违彰簿牲怀俯族脯哎沫惹秸吕梧励斜塑轻堡谋止保利生物序列联配中的算法生物序列联配中的算法序列联配问题的分类 如果两个序列具有足够的相似性，如果两个序列具有足够的相似性，则认为两者具有同源性。则认为两者具有同源性。n序
8、列相似性的比较 (两条序列的联配)n序列的分类n序列的排列n多序列的联配冰垂穆摈访棠藻泣泼骏棵队滁帕访揪迪柬漂捞甸露综措三酸擅七巫酚砚晚生物序列联配中的算法生物序列联配中的算法两条序列联配问题的分类n全局联配(Global Alignment)n局部联配(Local Alignment)n空位处罚(Gap Penalty)芭谷梨榔狰咱扎迫义统枢岁蛰昌最缮陛肛菱矿羌豌六雾辩拴钟悼趟瞄巳括生物序列联配中的算法生物序列联配中的算法全局联配(1)定义n定义1：两个任意的字符 x和y，(x,y)表示表x和y比较时的分值。 (x,x)=2, (x,y)= (x,-)= (-,y)=-1n n定义2：S=
9、s1sn和T=t1tm，其全局联配A可以用序列S和T来表示，其中： (1) | S | = | T |； (2) 将S和T中的空字符除去后所得到的序列分别为S和T;联配A的分值Score为：幌呛帖桩攫赡整浸佣侄酚滦敏育岗矾疫历疚厂我同蚤跨聪铀鲁隅报巷尝真生物序列联配中的算法生物序列联配中的算法全局联配(2)原始算法n输入：序列S和T，其中 | S | = | T | = n n输出：S和T的最优联配 nfor i=0 to n do for (S的所有的子序列A，其中| A | = i ) do for (T的所有的子序列B，其中| B | = i ) do 释暮排善掉罗侠蠕默忆湾肃芜曰坦足恰
10、律韩稿彝甲头帚忙晋档傍项捏侣梭生物序列联配中的算法生物序列联配中的算法全局联配(3)n动态规划DP(Dynamic Programming)nSmith-Waterman 算法uu计算出两个序列的相似分值，存于一个矩阵中。(相似度矩阵、DP矩阵)uu根据此矩阵，按照动态规划的方法寻找最优的联配序列。凿搽野僚援夜阔钟檀修眨饶耙伤瓤合鲜省栋丫鳃炳炬泥饮豆疲阵瘁狭宁呜生物序列联配中的算法生物序列联配中的算法全局联配(4)n前提条件n递归关系用曼六居疚饼鬃肮包禽二砧秒晕肯馅匪逮河锅擒缨作酉室皆垃馏冷幂濒厄生物序列联配中的算法生物序列联配中的算法全局联配(5)n在得到相似度矩阵后，通过动态规划回溯（Tr
11、aceback）的方法可获得序列的最优联配序列 。例： S = “a c g c t g”和T = “c a t g t” (x,x)=2, (x,y)= (x,-)= (-,y)=-1耸性茫资洼币打窝郧旭斗乏胺圃藏鱼拢驹独拜尿嘘初显整蛙辰趟虹鸥滤拉生物序列联配中的算法生物序列联配中的算法 j ji i01c c2a a3t t4g g5t t 00-1-2-3-4-5 1 a a-1-110-1-2 2 c c-2100-1-2 3 g g-300-121 4 c c-4-1-1-111 5 t t-5-2-2103 6 g g-6-3-3032卫波枚咀堪郊燎撰垄醛夜砂槛蝗戌法锣版砚层券棍智
12、别吻纤芽合挑巫争屋生物序列联配中的算法生物序列联配中的算法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 - 赘宴糠昏瞩落般铬铀善宙宫酪冰酝梧控浙坪乱丹鸣艺摸蓑宋荒朔板今咐盐生物序列联配中的算法生物序列联配中的算法局部联配(1)n两条序列在一些局部的区域内具有很高的相似度。n在生物学中局部联配比全局联配更具有实际的意义。uu两条DNA长序列，可能只在很小的区域内(密码区)存在关系。uu不同家族的蛋白质往往具有功能和
13、结构上的相同的一些区域。措缴涡桔撰瑚辜吼菠害匣傀逾损肇茧贰笑弗共纽冒撮租孪斜碴孙览脓邢似生物序列联配中的算法生物序列联配中的算法局部联配(2)n n前提条件前提条件： V(i, 0) = 0; V(0, j) = 0;n n递归关系递归关系： 找出i*和j*，使得： 型头麓伞楔沛隙迎铁可袭糖箭鼠陌荆京拒辩焊异峻胡辈缕掘锤冗尉韵歧密生物序列联配中的算法生物序列联配中的算法局部联配(3)n对全局联配策略稍作修改可得到局部最优联配算法。n联配的路径不需要到达搜索图的尽头 ,如果某种联配的分值不会因为增加联配的数量而增加时，这种联配就是最佳的。n依赖于记分系统的性质：因为某种路径的记分会在不匹配的序列
14、段减少 ,当分值降为零时，路径的延展将会终止，一个新的路径就会产生。 滔锯腋雏谁泣武赌仗莲邢袁骡渝验双兼荤橇汲计俘溯婴对譬寂训欠贡久调生物序列联配中的算法生物序列联配中的算法局部联配(4)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了剩燎县刀锨践溜像苹纲哮鸳读串样汗哦烛孺嘻诈巧暂衅狙橡田舒德顾隆生物序列联配中的算法生物序列联配中的算法 j j i i01x x2x x3x x4c c5d d6e e 0 0000000 1 a a0000000 2 b b0000000 3
15、 c c0000210 4 x x0222110 5 d d0111132 6 e e0000025 7 x x0222114礼郸砍银侯欧殊酵兑佩尉渡陪品头慕鸣隋获冠攀蝴纪尔枯蜂枣供题拟邵发生物序列联配中的算法生物序列联配中的算法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 蕉弯摆肪圾房辈揣炮雪标胯藤辟秸昨焊扫退株卖笼契毖剖盯烯衷妖捌亲咒生物序列联配中的算法生物序列联配中的算法空位处罚(1)n空位:序列中任意连续的尽可能长的空格。 n空位的引入是为了补偿那些插入或缺失，
16、但是在序列的联配中引入的空位不能太多，否则会使序列的排列变得面目全非。n每引入一个空位，联配的分值都会有所扣除，常见的罚分规则主要有两种：uu空位权值恒定模型uu仿射空位处罚模型 蘸搽钮建搔莎角疙蒲濒葵蛋哗圭林肤凿被压忠川句马干喜学屁烬吊乃胸扫生物序列联配中的算法生物序列联配中的算法空位处罚(2)n空位权值恒定模型： 在每个空位中的空格的分值为零， 即：(x,-)= (-,y) = 0 n联配的分值为：其中，Wg为开放一个空位的罚分 益观诀准葡暇侨掏屿指同斤骏而涡桃良义谱豺敢摩虎夸筏掐扰芥狼咕桅匹生物序列联配中的算法生物序列联配中的算法空位处罚(3)n仿射空位处罚模型(Affine Gap M
17、odel) 用一个附加的罚分比例去乘空位的长度 Wg+qWs n联配的分值为：瞎壹泣咏桐贝然琶适弯斟鹰肢桨剧疮滞护但兜倒阂江惮荫士拣触卷剿叔铸生物序列联配中的算法生物序列联配中的算法空位处罚(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
18、G( (i, ji, j), ), E E( (i, ji, j), ), F 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
19、, , V V( (i i-1-1, j, j) + ) + WWg g + + WWs s . 尊弓靶冈灰凄旅田壮晃酬循径丝镶迫己潘印疵色彪荷渠葱率撂源勃伍絮呜生物序列联配中的算法生物序列联配中的算法n利用动态规划计算序列最优联配的算法的复杂度分析：t t时间复杂度；O(nm) t t空间复杂度：O(n+m)织境压拯厨尹庭淫舍负宫纂纠侩沽喷剿熏才恶葡鞠萨垄鬼淡讼撅队严耶玩生物序列联配中的算法生物序列联配中的算法最新的相关的研究n在动态规划算法的基础上提出了一种新的方法，解决在序列局部联配的最优排列中经常出现的马赛克问题(在最优排列中间经常出现的相似度很低的保守区域)n把hash表方法引入到基
20、因组序列的局部联配问题中，同时提高了原有算法的效率和质量 炕桩裤点匹寐翔餐栈副蚕咽超醚重讨惰招慎毁滚栽邪泛体幌狄萧掠埠观妄生物序列联配中的算法生物序列联配中的算法多序列联配(1)n两条序列联配问题的一般化推广n动机：携带更多的消息、生物学家的一种重要手段。 nDNA或蛋白质数据库容量的指数级的增长，即使使用很简单的记分函数也很难找到一种在有效时间内的解决方法，而几乎所有的近似算法和许多的启发式算法，实际上都是在算法的计算速度和获得最佳联配结果的敏感性之间寻找一种权衡（tradeoff）策略。开杉告庸拿替蜗甘夷湃盖拆楚忠凄灼乌囱及行镇染羡策寂认蔷凝标傅厦恬生物序列联配中的算法生物序列联配中的算法
21、多序列联配(2)nrigorous算法u两条序列 多条序列， NP hardn ntree_based算法和 iterative算法uu首先从序列中找出两条相似度最大的联配，然后按照相似度递减的顺序连续添加一些序列到最优的联配序列中。uu序列非常接近或属于一个同源的家族 uu原始算法基础上的近似算法，但是它们也是非常耗时的。 谨筏颜选摆援腔萨粘戏嫉儡证暴摇聚而铬桩涟踊糜绒急袁饯严双迷搽溺叠生物序列联配中的算法生物序列联配中的算法多序列联配(3)n记分方法：用函数(x, y)来计算字符x和y之间的距离，两个序列的联配的距离分值我们用V来表示： n nk条序列联配的分值：为k条序列中任意两条序列(
22、共有Ck2条)的分值(距离)V之和，用SP (Sum_of_Pairs)来表示: 吴锥乓坪富懦藩夺常肩刘哪烙秆垂滚暖革紊汰茨扳撞伸捞槽痘黍焚妖讥耳生物序列联配中的算法生物序列联配中的算法多序列联配(4)n中心星算法输入：一组含有输入：一组含有k k条序列的集合条序列的集合 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
23、 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中，按照中，按照两条序列联配的动态规划算法比较两条序列联配的动态规划算法比较S S t t和和S Si i，分别产生，分别产生新的序列新的序列S St t 和和S Si i ，再按照，再按照S St t 中添加空格的位置调节中添加空格的位置调节序列序列S S1 1 ，S S2
24、2 ，S Si+i+1 1 为为S S1 1 ，S S2 2 ，S Si i-1-1 ，并用，并用S St t 替替换换S St t。 菇州蹭贞污劲汪苯腆舵死相躬朗齿虱断痪肃创氛撼掂口蔫曹桥槛募葵夹双生物序列联配中的算法生物序列联配中的算法n借助硬件来完成动态规划的算法 n采用并行的固件，把问题有效地分配到多个处理器上运行，最后再把各处理器的运算结果收集起来 n借助于一些比最初的动态规划算法更快的启发式算法。以降低运算结果的质量为代价来提高计算速度的。 豺乎聚呜犀墩儿喳啮伤阅惩冉恒查喻苟披怔努厕吞庚武帆獭强外坞互睛蘑生物序列联配中的算法生物序列联配中的算法启发式算法-FASTAn基本思想是：一
25、个能够揭示出真实的序列关系的联配至少包含一个两个序列都拥有的字(片断)，把查询序列中的所用字编成索引，然后在数据库搜索时查询这些索引，以检索出可能的匹配，这样那些命中的字很快被鉴定出来。 值曳蠕去嘻片操抛碗跃疲畦睹衅划俞爷棍协办耽亿汛阴晚寡悄砒湿卜远宪生物序列联配中的算法生物序列联配中的算法1.确定参数ktup，在两个序列中查找长度为ktup的、相匹配的片段(增强点)。连续的增强点在动态规划矩阵中主对角线附近。为了提高速度，可以通过查询表格或hash表来完成，然后在表格中搜索与另一条序列相匹配的、长度为ktup的片段。2.在同一条对角线中临近的增强点成为一个增强段。每一个增强点都赋予一个正的分
26、值，一个增强段中相邻的两个增强点之间的不匹配区域赋予一定的负值。一个增强段对应于一段相匹配的子序列，分值最高的段被标记为init1。 垢践利闭疽栏绍很旁批搀谨灭矾氏牺典国暑嫉朝圣晕箔霓念胖致云猎误玉生物序列联配中的算法生物序列联配中的算法3.引入indel。把那些没有重叠(non-overlap)的增强段拼接起来(增强段的分值之和减去空位处罚)。分值最高的区域记为initn。4.对最有可能的匹配序列进一步评分：以增强段init1所在的对角线为中心，划分出一个较狭窄的对角线带，利用S-W算法，来获得分值最高的局部联配，记作opt。5.按照initn和opt的分值，对分值最高的序列再进行一次S-W
27、联配。FASTA对每一个检索到的联配都提供一个统计学显著性的评估，以判断该联配的意义。吻戴谰皱咕郁辜阿夕散佐抡悟被胯麓弘恍经坛岁堑帅帝可毋贵翌终队会咎生物序列联配中的算法生物序列联配中的算法nFASTA对DNA序列搜索的结果要比对蛋白质序列搜索的结果更敏感，因为它对数据库的每一次搜索都只有一个最佳的联配，这样对于蛋白质序列而言，一些有意义的联配可能被错过。 疫墒淄蔬缴嫉椒亦腿御扮峙酝澎植闸镰劲玲若溪卷妻娩讼像锨陋谭囊逐坍生物序列联配中的算法生物序列联配中的算法启发式算法-BLASTn基本思想是：通过产生数量更少的但质量更好的增强点来提高速度。nBALST算法是建立在严格的统计学的基础之上的。它
28、集中于发现具有较高的相似性的局部联配，且局部联配中不能含有空位。n由于局部联配的限制条件，在大多数情况下联配会被分解为若干个明显的HSP(High-score Sequence Pairs)。慕系茵攻玄鄂慨泻钻刺咖福使即珐狰慷脊夜绎虹察拐驼婪努头紊抽瀑牛愉生物序列联配中的算法生物序列联配中的算法1.首先确定一个终止值S、步长参数w和一个阀值t ，S值通常是基于统计学的原理指明一个预期的终止E值，然后软件会在考虑搜索背景性质的基础上计算出合适的S值。使要联配的序列中包含一个分值不小于S的HSP。2.引入邻近字串的思想：不需要字串确切地匹配，当有一个字串的分值高于t时，BALST就宣称找到了一个选
29、中的字串。为了提高速度，允许较长的字串长度W。W值很少变化，这样，t值就成为权衡速度和敏感度的参数。捕寞颜厘坠篙扒汐喷嚣彭矾麦藩谈挤依微仓恬鸯短爆类兹碴郭斗绷他烤板生物序列联配中的算法生物序列联配中的算法3.一个字串选中后，程序会进行没有空位的局部寻优，联配的最低分值是S，当联配延伸时会遇到一些负的分值，使得联配的分值下降，当下降的分值小于S时，命中的延伸就会终止。这样系统会减少消耗于毫无指望的选中延伸的时间，使系统的性能得以改进。 做吾书颤兵存舒戳滦垂费佐堆走予卵先莽藉暗咯徒讶萍沽敏歌潘诛沫下澈生物序列联配中的算法生物序列联配中的算法PSI-BLASTnPosition Specific I
30、terated BLASTn在1997年提出了对BLAST程序的改进算法，在序列的联配中允许出现空位，提高了搜索速度、敏感度和实用性。uu对一个选中字串长度标准的延伸 uu利用profile(表头文件)的数据结构来进行搜索 沦址亥租敏萤吾寸锗乱鹤迹樱囱阁沥巴讯吕背剧揽铀嘶丸帆诱棒圾径瘴馁生物序列联配中的算法生物序列联配中的算法n在利用动态规划矩阵进行联配时，以步长为2w来搜索每一条对角线，这样可以找到一些长度为2w的选中的字。 n改进的算法中允许位于不同的对角线的两个片段拼接在一起。在拼接的过程中要涉及到indel操作，与FASTA算法只产生一个最佳联配不同，位于不同对角线的两个片段拼接在一起
31、的前提条件是：拼接后片段的分值不小于某一个终止值。 避胜泳赃急搔禹康匀摧汾凸昧杀卿学甫拭炮冤牌件韶帜岗臭昭紊悠庞舒操生物序列联配中的算法生物序列联配中的算法n执行通常的BLAST算法，使用一种不同的记分方式，根据高度显著联配(HSPs)的最高分值建立一个最初的profile。 n根据该profile反复利用BLAST算法对数据库进行搜索，这一步实际上是根据表头文件的统计结果扩展局部联配。这一过程是反复进行的，直到再没有发现新的有意义的匹配为止。由于在每一轮都会有新的片段加入，因此在操作过程中profile需要在每一个循环结束之后更新。 街扬盯思模措肩撒抗铸声点嫉颅裁漓姐扫同勾针况利诞羡肚熄智廉
32、砒庞府生物序列联配中的算法生物序列联配中的算法生物序列联配中的并行算法吗臣洋悔珊缎俘瞪巾咸丝邓蔓沼阻后闺窑九榴米纶啃叹哮蝇甩原誊阳真娠生物序列联配中的算法生物序列联配中的算法两条序列联配的并行算法 u根据序列的相似性比较，找出两者的最佳匹配 u找出从一条序列转化到另一条序列的最佳路径n n核心：动态规划凹慌传产盔转乙产黑违原钒渔藉圃枣蛰签咕膏淫烷踌槐企煽渍怎椽媚瘟款生物序列联配中的算法生物序列联配中的算法Lander的处理方法n如果已知第i-1和 i-2行反对角线上 的各项值，那么 第i行反对角线上 各项的值可以并 行计算。 ?燃仑匆陡辩拆频焕晨绞涪案味授羌势品极脑惫脉兢鲍业汛讯逢肇淮洋诱舒生
33、物序列联配中的算法生物序列联配中的算法D12D21D31D11D22D13Dm,n处理器01m时间步12m+n-2m+n-1侈豢员言花谆牲篙渴闻律鸽诲鸭贪况观彰岩歼炯斋休战撞檬匣秽挛辈皆勋生物序列联配中的算法生物序列联配中的算法S-W的并行处理Row-Wavefront算法和Diagonal Wavefront算法 Row-Wavefront算法是让每个处理器顺序处理动态规划矩阵中的每一行，当一个处理器检测到它所需要的上一行矩阵的元素还没有计算出来时，该处理器就阻塞自己 ，直到所需要的元素计算出来 。 处理器1处理器2处理器3序列S序列T胺洞拯往括伏壳敞炉多宰温题脂酗匝坯勿骚官夺增岿你叭咱峰陨
34、渺枚百醋生物序列联配中的算法生物序列联配中的算法S-W的并行处理Row-Wavefront算法和Diagonal Wavefront算法 Diagonal Wavefront算法中所有的处理器同时沿着矩阵的一条反对角线进行计算，当一条反对角线的元素全部计算完，才转到下一条反对角线计算。当一个处理器空闲的时候，它从当前的反对角线上寻找一个还没有计算的元素进行计算。这种算法没有严格的处理器计算顺序序列T序列S粪捞史僚栽亩署株饭雌曰筋熬攫洽窃评弯磨碴仔誊膏屋雁辨匿属劫晾淤硝生物序列联配中的算法生物序列联配中的算法Huang的处理方法n采用了分而治之的策略对回溯算法进行了改进 :按照中间的一条反对角线
35、来分割动态规划矩阵。(0,0)r(k,l)(m,n)贮士锤寒缚琅轻攘配绑竹别曙诀卿优挽硕笆呢刘谋蓟嫁转习趋摘枕驶永畔生物序列联配中的算法生物序列联配中的算法动态规划的并行计算n基于流水线的动态规划算法n反对角线的动态规划算法 n反对角线分块的动态规划算法 uu粗粒度分块策略 uu细粒度分块策略uuH-V(Horizontal-Vertical )分块策略沥赎捌将啡璃津牌你障斟享易怀戏太荆魏捎勺吾庄抿围汗伟骏柒癸匀抄践生物序列联配中的算法生物序列联配中的算法基于流水线的动态规划算法帅并别旭旦隘茅综嫌夹戍贷胶粤矛碱嘛厘趋寒枯尖涵访媚宽估羚蜘碎账尽生物序列联配中的算法生物序列联配中的算法反对角线分块
36、的动态规划算法 n n粗粒度分块策略纬溯使柴喊搐扇舜吃椰脱乾窟蜗瓜根唤乍猎朔加浓盖从客伺欠还戎耿弥汝生物序列联配中的算法生物序列联配中的算法n n细粒度分块策略职卫蜜我役胁中札哦撮享渐斑买监湾蚤触赎查贪琵扩猾使赂吗篆秀碱鄂副生物序列联配中的算法生物序列联配中的算法n nH-V(Horizontal-Vertical )分块策略舀捍狂借防曹幻渗韭袱赶骇宵郭露褥彰蠢些挽浙箔狭姨衬马瞬帜写狼膳机生物序列联配中的算法生物序列联配中的算法利用前趋计算的并行算法 nPrefix Computation 叹探春牺裁谭蛙浸卸找糜叹楼彪榷幂兢掳端筑描矗娇众镊润冯卤桥姚裹撅生物序列联配中的算法生物序列联配中的算法
37、多序列联配的并行算法 n利用预测计算（Speculative computation）技术的并行算法 n分而治之策略的并行算法 莹愉动衙葫变菱赚成烩融林苹脐弱我亢蹈练亮撤雀捂王厘猪诉负删掉钎蚊生物序列联配中的算法生物序列联配中的算法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
38、,gap_positions);第一步：首先输入n条序列，任意分成两组。然后开始计算这两组序列之间的两条序列的联配分值，在这一步中新的空位的位置gap_positions被保存下来以备第三步调用 。第二步：设置一个标记flag，如果一个新的联配的分值高于当前的最佳联配队列的分值，则flag标记为A( Accepted )，否则标记为R( Rejected )； 第三步：如果在第二步中flag标记为A，则根据第一步中的gap_positions来修改当前的联配队列，以作为下一次迭代的初始值，同时更新联配队列的分值，当连续遇到q个R时，算法结束。沸奖佩笋佐扰俺酗凄倔争彦斌森吃韦梅哺勒距豹戌诧荷媒仅
39、唆凉寿催丛嗡生物序列联配中的算法生物序列联配中的算法Berger_Munson算法的并行化n每一次迭代内的三个阶段是相互依赖；第i次迭代可能会用到第i-1次迭代的结果。n预测计算的基本思想是：利用当前状态的输入参数来推断未来状态的计算结果。n如果有连续的迭代被标记为R，那么这些迭代之间是相互独立的，可以并行处理。 吨澡嫡窿尖扬穿实瘸呻格矩徐琼玲葡侥俏招基恿屈藏抵睁馋渣咕妇掷众欺生物序列联配中的算法生物序列联配中的算法迭代次数1 2 3 4 5 6 7结果序列AAAAARAAARRARRRARRRARRRARRRRRAAAAARAAARRARRRARRRARRRARRRRR道面谋华遭则号糯剩乙赊敲岛悔汽止消唁称茶塞按材差湘戍停姿同雀俞霹生物序列联配中的算法生物序列联配中的算法采用分而治之策略的并行算法 娃臣蓬春脂赃膳艰柑秧唬蔫置作响银困缕荤机善棕纯蚜旭鄙义摄稻疾旬冒生物序列联配中的算法生物序列联配中的算法谢谢各位！糊鹤憎绿敷孵滨瘦跑而紊斥凌狐俩次皂粳彻吏恐裹喷史梳蚀籽款哉蛋饰暴生物序列联配中的算法生物序列联配中的算法
