生物序列联配中的算法幻灯片.ppt

《生物序列联配中的算法幻灯片.ppt》由会员分享，可在线阅读，更多相关《生物序列联配中的算法幻灯片.ppt（71页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、生物序列联配中的算法第1页，共71页，编辑于2022年，星期一提 纲n n背景知识n n序列相似性的比较t t两条序列的联配问题t t多序列的联配问题t t一些启发式的算法n n生物序列联配中的并行算法第2页，共71页，编辑于2022年，星期一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页，共

2、71页，编辑于2022年，星期一DNA(2)n n碱基的配对原则uuA(腺嘌呤)T(胸腺嘧啶)uuC(鸟嘌呤)G(胞嘧啶)n n一个嘌呤基与一个嘧啶基通 过氢键联结成一个碱基对。n nDNA分子的方向性uu53第4页，共71页，编辑于2022年，星期一DNA(3)n nDNA的双螺旋结构 碱基对之间的互补能力碱基对之间的互补能力第5页，共71页，编辑于2022年，星期一DNA(4)n nDNA的复制uu在DNA解旋酶的作用 下两条链分离开，分 别作为一个模板，在 聚合酶的作用下合成 一条新链。第6页，共71页，编辑于2022年，星期一RNA、转录和翻译n nRNA(核糖核酸)：单链结构、尿嘧啶

3、U代替胸腺嘧啶T、位于细胞核和细胞质中。n n转录：DNA链 RNA链 信使RNA(mRNA)，启动子。n n翻译：mRNA上携带遗传信息在核糖体中合成蛋白质的过程。第7页，共71页，编辑于2022年，星期一变异n n进化过程中由于不正确的复制，使DNA内容发生局部的改变。n n变异的种类主要有以下三种：uu替代(substitution)uu插入或删除(insertion or deletion)indeluu重排(rearrangement)第8页，共71页，编辑于2022年，星期一蛋白质n n由氨基酸依次链接形成在生物体中总共有20种氨基酸。n n蛋白有十分复杂的三维结构。其三维机构决定

4、了蛋白质的功能。第9页，共71页，编辑于2022年，星期一基 因n n什么是基因？uuDNA上具有特定功能的一个片断，负责一种特定性状的表达。一般来讲，一个基因只编码一个蛋白质。第10页，共71页，编辑于2022年，星期一基因组n n任何一条染色体上都带有许多基因，一条高等生物的染色体上可能带有成千上万个基因，一个细胞中的全部基因序列及其间隔序列统称为genomes（基因组）。第11页，共71页，编辑于2022年，星期一DNA上的基因 基因第12页，共71页，编辑于2022年，星期一基因的编码n n基因编码是一个逻辑的映射，表明存储在DNA和mRNA中的基因信息决定什么样的蛋白质序列。n n每

5、个碱基三元组称为一个密码子(codon)n n碱基组成的三元组的排列共有4364种，而氨基酸共有20种类型，所以不同的密码子可能表示同一种氨基酸。第13页，共71页，编辑于2022年，星期一带来的问题n n序列排列问题 n n基因组的重排问题 n n蛋白质结构和功能的预测 n n基因(外显子、内含子)查找问题 n n序列装配(Sequence Assembly)问题第14页，共71页，编辑于2022年，星期一生物序列相似性的比较第15页，共71页，编辑于2022年，星期一动机n n在生物学的研究中，将未知序列同已知序列进行比较分析已经成为一种强有力的研究手段，生物学领域中绝大部分的问题在计算机

6、科学领域中主要体现为序列或字符串的问题。第16页，共71页，编辑于2022年，星期一序列联配问题的分类 如果两个序列具有足够的相似性，则认如果两个序列具有足够的相似性，则认为两者具有同源性。为两者具有同源性。n n序列相似性的比较(两条序列的联配)n n序列的分类n n序列的排列n n多序列的联配第17页，共71页，编辑于2022年，星期一两条序列联配问题的分类n n全局联配(Global Alignment)n n局部联配(Local Alignment)n n空位处罚(Gap Penalty)第18页，共71页，编辑于2022年，星期一全局联配(1)定义n n定义定义1 1：两个任意的字符

7、：两个任意的字符 x和和y，(x,y)表示表表示表x x和y比较时的分值。(x,x)=2,)=2,(x,yx,y)=(x,-x,-)=)=(-(-,y)=-1n n定义定义2 2：S=s1 1s sn和T T=t1 1t tm m，其全局联配A可以用序列S 和和T 来表示，其中：来表示，其中：(1)|S|=|=|T T|；(2)将S S和和T T 中的空字符除去后所得到的序列分中的空字符除去后所得到的序列分别为别为S S和T;联配联配A A的分值的分值ScoreScore为：第19页，共71页，编辑于2022年，星期一全局联配(2)原始算法n n输入：序列S和T，其中|S|=|T|=n n n

8、输出：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页，共71页，编辑于2022年，星期一全局联配(3)n n动态规划DP(Dynamic Programming)n nSmith-Waterman 算法uu计算出两个序列的相似分值，存于一个矩阵中。(相似度矩阵、DP矩阵)uu根据此矩阵，按照动态规划的方法寻找最优的联配序列。第21页，共71页，编辑

9、于2022年，星期一全局联配(4)n n前提条件n n递归关系第22页，共71页，编辑于2022年，星期一全局联配(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页，共71页，编辑于2022年，星期一 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-1-1-2-2 2 2 c c-2-21

10、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页，共71页，编辑于2022年，星期一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页，共71页，编辑于2022年，星期一局部联配(1)n n两条序列在一些局部

11、的区域内具有很高的相似度。n n在生物学中局部联配比全局联配更具有实际的意义。uu两条DNA长序列，可能只在很小的区域内(密码区)存在关系。uu不同家族的蛋白质往往具有功能和结构上的相同的一些区域。第26页，共71页，编辑于2022年，星期一局部联配(2)n n前提条件前提条件：V(i,0)=0;V(0,j)=0;n n递归关系递归关系：找出i*和j*，使得：第27页，共71页，编辑于2022年，星期一局部联配(3)n n对全局联配策略稍作修改可得到局部最优联配算法。n n联配的路径不需要到达搜索图的尽头,如果某种联配的分值不会因为增加联配的数量而增加时，这种联配就是最佳的。n n依赖于记分系

12、统的性质：因为某种路径的记分会在不匹配的序列段减少,当分值降为零时，路径的延展将会终止，一个新的路径就会产生。第28页，共71页，编辑于2022年，星期一局部联配(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第29页，共71页，编辑于2022年，星期一 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

13、 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 e0 00 00 00 00 02 25 5 7 7 x x0 02 22 22 21 11 14 4第30页，共71页，编辑于2022年，星期一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页，共71页，编辑于2022年，星期一空位处罚(1)n n空位:序列中任意连续的尽可能长的空格。n

14、 n空位的引入是为了补偿那些插入或缺失，但是在序列的联配中引入的空位不能太多，否则会使序列的排列变得面目全非。n n每引入一个空位，联配的分值都会有所扣除，常见的罚分规则主要有两种：uu空位权值恒定模型uu仿射空位处罚模型 第32页，共71页，编辑于2022年，星期一空位处罚(2)n n空位权值恒定模型：在每个空位中的空格的分值为零，即：(x,-)=(-,y)=0 n n联配的分值为：其中，Wg为开放一个空位的罚分 第33页，共71页，编辑于2022年，星期一空位处罚(3)n n仿射空位处罚模型(Affine Gap Model)用一个附加的罚分比例去乘空位的长度 Wg+qWs n n联配的分

15、值为：第34页，共71页，编辑于2022年，星期一空位处罚(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 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,

16、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页，共71页，编辑于2022年，星期一n n利用动态规划计算序列最优联配的算法的复杂度分析：t t时间复杂度；O(nm)t t空间复杂度：O(n+m)第36页，共71页，编辑于2022年，星期一最新的相关的研究n n在动态规划算法的基础上提出了一种新的方法，解决在序列局部联配的最优排列中经常出现的马赛克问题(在最优排列中间经常出现的相似度很低

17、的保守区域)n n把hash表方法引入到基因组序列的局部联配问题中，同时提高了原有算法的效率和质量 第37页，共71页，编辑于2022年，星期一多序列联配(1)n n两条序列联配问题的一般化推广两条序列联配问题的一般化推广n n动机：携带更多的消息、生物学家的一种重要手段。动机：携带更多的消息、生物学家的一种重要手段。n nDNA或蛋白质数据库容量的指数级的增长，即使或蛋白质数据库容量的指数级的增长，即使使用很简单的记分函数也很难找到一种在有效时使用很简单的记分函数也很难找到一种在有效时间内的解决方法，而几乎所有的近似算法和许多间内的解决方法，而几乎所有的近似算法和许多的启发式算法，实际上都是

18、在算法的计算速度和的启发式算法，实际上都是在算法的计算速度和获得最佳联配结果的敏感性之间寻找一种权衡获得最佳联配结果的敏感性之间寻找一种权衡（tradeoff）策略。第38页，共71页，编辑于2022年，星期一多序列联配(2)n nrigorous算法uu两条序列 多条序列，NP hardn ntree_based算法和 iterative算法uu首先从序列中找出两条相似度最大的联配，然后按照相似度递减的顺序连续添加一些序列到最优的联配序列中。uu序列非常接近或属于一个同源的家族 uu原始算法基础上的近似算法，但是它们也是非常耗时的。第39页，共71页，编辑于2022年，星期一多序列联配(3)

19、n n记分方法：用函数记分方法：用函数(x x,y y)来计算字符x和和y y之间的距离，两个序列的联配的距离分值我们用两个序列的联配的距离分值我们用V来表示：n nk k条序列联配的分值：为k k条序列中任意两条序列(共有Ck k2条)的分值(距离)V V之和，用SP (Sum_of_Pairs)来表示:第40页，共71页，编辑于2022年，星期一多序列联配(4)n n中心星算法中心星算法输入：一组含有输入：一组含有k k条序列的集合条序列的集合 uu找出序列找出序列S St t，S St t，使得使得 ititD D(S Si i,S,St t)的值最小，令的值最小，令A A=S St t

20、 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中，按照两条序列联配的动态规中，按照两条序列联配的动态规划算法比较划算法比较S S t t和和S Si i，分别产生新的序列分别产生新的序列

21、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页，共71页，编辑于2022年，星期一n n借助硬件来完成动态规划的算法 n n采用并行的固件，把问题有效地分配到多个处理器上运行，最后再把各处理器的运算结果收集起来 n n借助于一些比最初的动态规划算法更快的启发式算法。以降低运算结果的质量为代价来提高计算速度的。第42页，共71页，编辑于2022年，星期一启发式算法-FASTAn n基

22、本思想是：一个能够揭示出真实的序列关系的联配至少包含一个两个序列都拥有的字(片断)，把查询序列中的所用字编成索引，然后在数据库搜索时查询这些索引，以检索出可能的匹配，这样那些命中的字很快被鉴定出来。第43页，共71页，编辑于2022年，星期一1.1.确定参数ktup，在在两两个个序序列列中中查查找找长长度度为为ktup的、相匹配的片段(增强点)。连续的增强点在动态规划矩阵中主对角线附近。为了提高速度，可以通过查询表格或hash表来完成，然后在表格中搜索与另一条序列相匹配的、长度为ktupktup的片段。2.2.在同一条对角线中临近的增强点成为一个增强段。每一个增强点都赋予一个正的分值，一个增强

23、段中相邻的两个增强点之间的不匹配区域赋予一定的负值。一个增强段对应于一段相匹配的子序列，分值最高的段被标记为initinit1 1。第44页，共71页，编辑于2022年，星期一3.引 入 indel。把 那 些 没 有 重 叠(non-overlap)的增强段拼接起来(增强段的分值之和减去空位处罚)。分值最高的区域记为initn。4.对最有可能的匹配序列进一步评分：以增强段init1所在的对角线为中心，划分出一个较狭窄的对角线带，利用S-W算法，来获得分值最高的局部联配，记作opt。5.按照initn和opt的分值，对分值最高的序列再进行一次S-W联配。FASTA对每一个检索到的联配都提供一个

24、统计学显著性的评估，以判断该联配的意义。第45页，共71页，编辑于2022年，星期一n nFASTA对DNA序列搜索的结果要比对蛋白质序列搜索的结果更敏感，因为它对数据库的每一次搜索都只有一个最佳的联配，这样对于蛋白质序列而言，一些有意义的联配可能被错过。第46页，共71页，编辑于2022年，星期一启发式算法-BLASTn n基本思想是：通过产生数量更少的但质量更好的增强点来提高速度。n nBALST算法是建立在严格的统计学的基础之上的。它集中于发现具有较高的相似性的局部联配，且局部联配中不能含有空位。n n由于局部联配的限制条件，在大多数情况下联配会被分解为若干个明显的HSP(High-sc

25、ore Sequence Pairs)。第47页，共71页，编辑于2022年，星期一1.首先确定一个终止值S、步长参数w和一个阀值t，S值通常是基于统计学的原理指明一个预期的终止E值，然后软件会在考虑搜索背景性质的基础上计算出合适的S值。使要联配的序列中包含一个分值不小于S的HSP。2.引入邻近字串的思想：不需要字串确切地匹配，当有一个字串的分值高于t时，BALST就宣称找到了一个选中的字串。为了提高速度，允许较长的字串长度W。W值很少变化，这样，t值就成为权衡速度和敏感度的参数。第48页，共71页，编辑于2022年，星期一3.一个字串选中后，程序会进行没有空位的局部寻优，联配的最低分值是S，

26、当联配延伸时会遇到一些负的分值，使得联配的分值下降，当下降的分值小于S时，命中的延伸就会终止。这样系统会减少消耗于毫无指望的选中延伸的时间，使系统的性能得以改进。第49页，共71页，编辑于2022年，星期一PSI-BLASTn nPosition Specific Iterated BLASTn n在1997年提出了对BLAST程序的改进算法，在序列的联配中允许出现空位，提高了搜索速度、敏感度和实用性。uu对一个选中字串长度标准的延伸 uu利用profile(表头文件)的数据结构来进行搜索 第50页，共71页，编辑于2022年，星期一n n在利用动态规划矩阵进行联配时，以步长为2w来搜索每一条

27、对角线，这样可以找到一些长度为2w的选中的字。n n改进的算法中允许位于不同的对角线的两个片段拼接在一起。在拼接的过程中要涉及到indel操作，与FASTA算法只产生一个最佳联配不同，位于不同对角线的两个片段拼接在一起的前提条件是：拼接后片段的分值不小于某一个终止值。第51页，共71页，编辑于2022年，星期一n n执行通常的BLAST算法，使用一种不同的记分方式，根据高度显著联配(HSPs)的最高分值建立一个最初的profile。n n根据该profile反复利用BLAST算法对数据库进行搜索，这一步实际上是根据表头文件的统计结果扩展局部联配。这一过程是反复进行的，直到再没有发现新的有意义的

28、匹配为止。由于在每一轮都会有新的片段加入，因此在操作过程中profile需要在每一个循环结束之后更新。第52页，共71页，编辑于2022年，星期一生物序列联配中的并行算法第53页，共71页，编辑于2022年，星期一两条序列联配的并行算法 uu根据序列的相似性比较，找出两者的最佳匹配 uu找出从一条序列转化到另一条序列的最佳路径n n核心：动态规划第54页，共71页，编辑于2022年，星期一Lander的处理方法n n如果已知第i-1和 i-2行反对角线上 的各项值，那么 第i行反对角线上 各项的值可以并 行计算。?第55页，共71页，编辑于2022年，星期一D12D21D31D11D22D13

29、Dm,n处理器01m时间步12m+n-2m+n-1第56页，共71页，编辑于2022年，星期一S-W的并行处理Row-Wavefront算法和Diagonal WavefrontDiagonal Wavefront算法 Row-Wavefront算法是让每个处理器顺序处理动态规划矩阵中的每一行，当一个处理器检测到它所需要的上一行矩阵的元素还没有计算出来时，该处理器就阻塞自己，直到所需要的元素计算出来。处理器1处理器2处理器3序列S序列T第57页，共71页，编辑于2022年，星期一S-W的并行处理Row-Wavefront算法和算法和Diagonal WavefrontDiagonal Wave

30、front算法算法 Diagonal Wavefront算法中所有的处理器同时沿着矩阵的一条反对角线进行计算，当一条反对角线的元素全部计算完，才转到下一条反对角线计算。当一个处理器空闲的时候，它从当前的反对角线上寻找一个还没有计算的元素进行计算。这种算法没有严格的处理器计算顺序序列T序列S第58页，共71页，编辑于2022年，星期一Huang的处理方法n n采用了分而治之的策略对回溯算法进行了改进:按照中间的一条反对角线来分割动态规划矩阵。(0,0)r(k,l)(m,n)第59页，共71页，编辑于2022年，星期一动态规划的并行计算n n基于流水线的动态规划算法n n反对角线的动态规划算法 n

31、 n反对角线分块的动态规划算法 uu粗粒度分块策略 uu细粒度分块策略uuH-V(Horizontal-Vertical)分块策略第60页，共71页，编辑于2022年，星期一基于流水线的动态规划算法第61页，共71页，编辑于2022年，星期一反对角线分块的动态规划算法 n n粗粒度分块策略第62页，共71页，编辑于2022年，星期一n n细粒度分块策略第63页，共71页，编辑于2022年，星期一n nH-V(Horizontal-Vertical)分块策略第64页，共71页，编辑于2022年，星期一利用前趋计算的并行算法 n nPrefix Computation 第65页，共71页，编辑于2

32、022年，星期一多序列联配的并行算法 n n利用预测计算（Speculative computation）技术的并行算法 n n分而治之策略的并行算法 第66页，共71页，编辑于2022年，星期一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_positions);第一步：首先

33、输入n条序列，任意分成两组。然后开始计算这两组序列之间的两条序列的联配分值，在这一步中新的空位的位置gap_positions被保存下来以备第三步调用。第二步：设置一个标记flag，如果一个新的联配的分值高于当前的最佳联配队列的分值，则flag标记为A(Accepted)，否则标记为R(Rejected)；第三步：如果在第二步中flag标记为A，则根据第一步中的gap_positions来修改当前的联配队列，以作为下一次迭代的初始值，同时更新联配队列的分值，当连续遇到q个R时，算法结束。第67页，共71页，编辑于2022年，星期一Berger_Munson算法的并行化n n每一次迭代内的三个阶

34、段是相互依赖；第i次迭代可能会用到第i-1次迭代的结果。n n预测计算的基本思想是：利用当前状态的输入参数来推断未来状态的计算结果。n n如果有连续的迭代被标记为R，那么这些迭代之间是相互独立的，可以并行处理。第68页，共71页，编辑于2022年，星期一迭代次数迭代次数1 2 3 4 5 6 71 2 3 4 5 6 7结果序列结果序列AAAAARAAARRARRRARRRARRRARRRRRAAAAARAAARRARRRARRRARRRARRRRR第69页，共71页，编辑于2022年，星期一采用分而治之策略的并行算法 第70页，共71页，编辑于2022年，星期一谢谢各位！第71页，共71页，编辑于2022年，星期一