生物计算技术-第章多重序列比对分析ppt课件

1、Biocomputing technology Multiple sequence alignment第第4章章 多重序列比对分析多重序列比对分析目的要求：目的要求： 1 1 掌握多重序列比对的基本概念及意义。掌握多重序列比对的基本概念及意义。 2 2 掌握多重序列比对的星形比对、树形比对及隐马尔可夫模型。掌握多重序列比对的星形比对、树形比对及隐马尔可夫模型。 3 3 了解多重序列比对的动态规划算法、了解多重序列比对的动态规划算法、CLUSTAL W CLUSTAL W 算法。算法。教学内容：教学内容： 4.1 4.1 多重序列比对的意义多重序列比对的意义 4.2 4.2 多重序列比对算法原理

2、多重序列比对算法原理Multiple sequence alignment4.1 多重序列比对的意义多重序列比对的意义目的：目的： 发现多个序列的共性发现多个序列的共性 发现与结构和功能相关的保守序列片段发现与结构和功能相关的保守序列片段定义：定义：设：有设：有k个序列个序列s1, s2, . ,sk，每个序列由同一，每个序列由同一个字母表中的字符组成，个字母表中的字符组成，k大于大于2，通过插入，通过插入“空空位位操作，使得各序列达到一样的长度，从而形操作，使得各序列达到一样的长度，从而形成这些序列的多重比对。成这些序列的多重比对。Biocomputing technology Multip

3、le sequence alignment8条免疫球蛋白序列片段的多重比对：条免疫球蛋白序列片段的多重比对：半光氨酸半光氨酸色氨酸色氨酸疏水残基疏水残基保守区域保守区域SPSP得分得分Biocomputing technology Multiple sequence alignmentBiocomputing technology Multiple sequence alignment 通过序列的多重比对，可以得到一个序列家族的序列通过序列的多重比对，可以得到一个序列家族的序列特征。当给定一个新序列时，根据序列特征，可以判断这特征。当给定一个新序列时，根据序列特征，可以判断这个序列是否属于该家

4、族。个序列是否属于该家族。 对于多序列比对，现有的大多数算法都基于渐进比对对于多序列比对，现有的大多数算法都基于渐进比对的思想，在序列两两比对的基础上逐步优化多序列比对的的思想，在序列两两比对的基础上逐步优化多序列比对的结果。结果。 进行多序列比对后，可以对比对结果进行进一步处理，进行多序列比对后，可以对比对结果进行进一步处理，例如构建序列的特征模式，将序列聚类、构建分子进化树等。例如构建序列的特征模式，将序列聚类、构建分子进化树等。 4.2 多重序列比对算法原理多重序列比对算法原理4.2.1 SP模型模型4.2.2 多重比对的动态规划算法多重比对的动态规划算法4.2.3 优化算法优化算法4.

5、2.4 星型比对星型比对4.2.5 树形比对树形比对4.2.6 CLUSTALW算法算法4.2.7隐马尔可夫模型隐马尔可夫模型Biocomputing technology Multiple sequence alignment4.2.1 SP 模型模型 (Sum-of-Pairs) 逐对加和函数逐对加和函数作用：评价多重序列比对的结果作用：评价多重序列比对的结果SPSP计算的两种方法：计算的两种方法：Biocomputing technology Multiple sequence alignment方法方法1 1：先计算多重比对结果的每一列字符的得分，：先计算多重比对结果的每一列字符的得分

6、， 然后求整体多重比对得分然后求整体多重比对得分Biocomputing technology Multiple sequence alignment假设假设: 得分函数得分函数(代价函数代价函数) 具有加和性，即多重比对的得分具有加和性，即多重比对的得分 是各列得分总和。是各列得分总和。思路思路: 如何给比对的每一列打分，然后将各列的和加起来，如何给比对的每一列打分，然后将各列的和加起来， 成为一个总得分。成为一个总得分。每一列的处理方式每一列的处理方式: 寻找一个具有寻找一个具有k 个变量的打分函数，每一个变量或者是个变量的打分函数，每一个变量或者是 一个来自特定字母表中的字符，或者是一个

7、空位。一个来自特定字母表中的字符，或者是一个空位。 k 是参与多重比对的序列的个数。是参与多重比对的序列的个数。Biocomputing technology Multiple sequence alignment显式函数应满足如下条件：显式函数应满足如下条件：函数形式简单，具有统一的形式，不随序列的个数函数形式简单，具有统一的形式，不随序列的个数 而发生形式的变化。而发生形式的变化。2. 根据得分函数的意义，函数值应独立于各参数的顺序，根据得分函数的意义，函数值应独立于各参数的顺序， 即与待比较的序列先后次序无关。即与待比较的序列先后次序无关。3. 对相同的或相似字符的比对，奖励的得分值高，

8、而对对相同的或相似字符的比对，奖励的得分值高，而对 于不相关的字符比对或空白，则进行惩罚得分为负值）。于不相关的字符比对或空白，则进行惩罚得分为负值）。满足上述条件的一个函数就是常用的逐对加和函数，满足上述条件的一个函数就是常用的逐对加和函数，SP函数函数 。 方法方法1 1：先计算多重比对结果的每一列字符的得分，：先计算多重比对结果的每一列字符的得分， 然后求整体多重比对得分然后求整体多重比对得分 1k1ik1ijjik21)c,p(c)c,.,c,SP_score(c其中，其中，c1,c2,ck是一列中的是一列中的k个字符，个字符， p是关于一对字符相似性的打分函数。是关于一对字符相似性的

9、打分函数。 SP_score(c1,c2,ck)是多重序列比对中某一列是多重序列比对中某一列 的得分的得分.Biocomputing technology Multiple sequence alignment例：图例：图4.1多重比对的倒数第多重比对的倒数第3列的列的SP得分：得分：26GSGPALLscoreSP打分函数：打分函数： Pa,a）=0 Pa,b）= -1 （ab） Pa,-）=P（-,b）= -1 P（-,-）=0逐对计算逐对计算p(1,2)，p (1,3)，.，p(1,8)，p (2,3)，p(2,4)，.p(2,8) .，p(7,8) 的所有得分：的所有得分：（-7-6-

10、5-4-3-2-1）+2 = -26然后将一个多重比对所有列的得分全部加起来，其和即为该多重比对的得分。然后将一个多重比对所有列的得分全部加起来，其和即为该多重比对的得分。将所有多重比对的得分计算出来进行比较，得分最高的，应该是最好的。将所有多重比对的得分计算出来进行比较，得分最高的，应该是最好的。 Biocomputing technology Multiple sequence alignment多重比对在两条特定序列上的投影多重比对在两条特定序列上的投影Biocomputing technology Multiple sequence alignment方法方法2：先计算多重序列结果的序

11、列两两比对得分，：先计算多重序列结果的序列两两比对得分， 然后计算整体多重比对得分。然后计算整体多重比对得分。 是一个多重比对是一个多重比对 ijij是由是由 推演出来的序列推演出来的序列sisi和和sjsj的两两比对的两两比对 方法方法1和方法和方法2等价的条件：等价的条件：P(-,-)=0Biocomputing technology Multiple sequence alignmentj ji ii ij js sc co or re e( () )S SP P4.2.2 多重比对的动态规划算法多重比对的动态规划算法 多重序列比对的最终目标是通过处理得到一个得分最高多重序列比对的最终目

12、标是通过处理得到一个得分最高或代价最小的序列对比排列，从而分析各序列之间的或代价最小的序列对比排列，从而分析各序列之间的相似性和差异。相似性和差异。Biocomputing technology Multiple sequence alignment4.2.2 多重比对的动态规划算法多重比对的动态规划算法s1:VSN-Ss2:-SNA-s3:-ASBiocomputing technology Multiple sequence alignment前趋节点的个数等于前趋节点的个数等于2k - 1 2k - 1 问题：问题：计算量巨大计算量巨大时间复杂度为时间复杂度为O(2kO(2ki=1,.,

13、k i=1,.,k sisi) ) O(2kNk) O(2kNk) Biocomputing technology Multiple sequence alignmentNP-完全问题的定义完全问题的定义Biocomputing technology Multiple sequence alignment P 类问题为多项式界的问题；类问题为多项式界的问题； NP 类问题是这样一类问题，如果有一个复杂度为多类问题是这样一类问题，如果有一个复杂度为多项式的算法解决其中的某个问题，则所有这些问题都在项式的算法解决其中的某个问题，则所有这些问题都在P类中；类中；而而NP-完全问题是这样一类问题，如果

14、其中的某个问题存在完全问题是这样一类问题，如果其中的某个问题存在多项式界的算法，则多项式界的算法，则NP 类中的每一个问题都存在一个多项类中的每一个问题都存在一个多项式界算法。式界算法。 NP 完全问题通常被认为是一些人们难以在有限的时间、完全问题通常被认为是一些人们难以在有限的时间、空间内对问题求出最佳解的问题，几乎所有专家都认为不可空间内对问题求出最佳解的问题，几乎所有专家都认为不可能在多项式时间内准确求解能在多项式时间内准确求解NP-完全问题。完全问题。 NP-完全问题的近似求解方法完全问题的近似求解方法Biocomputing technology Multiple sequence

15、alignment舍去寻找最优解的要求，寻找对一般问题比较接近舍去寻找最优解的要求，寻找对一般问题比较接近 最优解的近似解；最优解的近似解；2. 利用非常规的求解技术求解，例如，利用神经网络、利用非常规的求解技术求解，例如，利用神经网络、 遗传算法等方法进行问题求解。遗传算法等方法进行问题求解。 生物信息学中生物信息学中NP-完全问题的近似求解方法完全问题的近似求解方法Biocomputing technology Multiple sequence alignment1. 只求解规模比较小的问题；只求解规模比较小的问题；2. 利用动态规划、分支约束等技术减小搜索空间，进步利用动态规划、分支约

16、束等技术减小搜索空间，进步 求解问题的效率；求解问题的效率；3. 针对具体问题的特点，根据实际输入情况，设计实用针对具体问题的特点，根据实际输入情况，设计实用 求解算法，这样的算法虽然在最坏的情况下其时间复求解算法，这样的算法虽然在最坏的情况下其时间复 杂度是非多项式的，但是算法执行的平均效率和复杂杂度是非多项式的，但是算法执行的平均效率和复杂 度与多项式的算法相当；度与多项式的算法相当；4. 采用近似算法或者启发式方法，如局部搜索、模拟退火、采用近似算法或者启发式方法，如局部搜索、模拟退火、 遗传算法等。遗传算法等。 对基于对基于SP 模型寻找最优多重序列比对这样一个问题，模型寻找最优多重序

17、列比对这样一个问题，可以用近似的方法求解，其算法的时间复杂度可用多项式表示。可以用近似的方法求解，其算法的时间复杂度可用多项式表示。4.2.3 优化计算方法优化计算方法标准动态规划算法存在的问题：标准动态规划算法存在的问题： 搜索空间大搜索空间大剪枝技术：将搜索空间限定在一个较小的区域范围内。剪枝技术：将搜索空间限定在一个较小的区域范围内。若问题是搜索一条得分最高或代价最小的路径，则在若问题是搜索一条得分最高或代价最小的路径，则在搜索时如果当前路径的得分低于某个下限或累积代价已搜索时如果当前路径的得分低于某个下限或累积代价已经超过某个上限），则对当前路径进行剪枝，即不再搜索经超过某个上限），则

18、对当前路径进行剪枝，即不再搜索当前路径的后续空间。当前路径的后续空间。Biocomputing technology Multiple sequence alignmentBiocomputing technology Multiple sequence alignment 在序列两两比对中在序列两两比对中, Fickett 和和Ukkonen 设计了一种设计了一种称为定界约束过程称为定界约束过程 (bounding procedure)的方法来缩小搜的方法来缩小搜索空间索空间,减少计算量减少计算量, 其中距离矩阵的上界和下界可以预先其中距离矩阵的上界和下界可以预先确定或动态变化。确定或动态变

19、化。 为了在多维空间上使用动态规划算法，为了在多维空间上使用动态规划算法，Carrillo 和和Lipman 将这种思想引入到多重序列比对，即先进行初步将这种思想引入到多重序列比对，即先进行初步的序列双重比对，以限制进一步做多重序列全面比对所需的序列双重比对，以限制进一步做多重序列全面比对所需要的多维空间的大小和计算量，从而克服了多序列的维数、要的多维空间的大小和计算量，从而克服了多序列的维数、空间和运算量之间的矛盾空间和运算量之间的矛盾 Carrillo-Lipman的优化计算方法的优化计算方法Biocomputing technology Multiple sequence alignme

20、nt 设设k 条序列的长度分别为条序列的长度分别为n1n2nk，按照，按照SP 得分模得分模型计算这些序列的最优比对。依然采用动态规划方法，但型计算这些序列的最优比对。依然采用动态规划方法，但并不计算超晶格空间中所有的节点，而是仅处理与最优路并不计算超晶格空间中所有的节点，而是仅处理与最优路径径“相关相关的节点。但是，哪些节点是相关的呢？这需要观的节点。但是，哪些节点是相关的呢？这需要观察节点在两条序列上的投影。察节点在两条序列上的投影。确定相关节点的方法：确定相关节点的方法： 假设假设是关于是关于k 条序列条序列s1s2sk 的最优多重比对。的最优多重比对。从某个节点向任何两条序列所在的平面

21、投影，如果该投影从某个节点向任何两条序列所在的平面投影，如果该投影是这两条序列两两最优比对的一部分前面一部分），那么是这两条序列两两最优比对的一部分前面一部分），那么该节点是与最优比对相关的节点。该节点是与最优比对相关的节点。 问题的提出问题的提出: 一种计算两条序列经过特定断点的最优比对的算法一种计算两条序列经过特定断点的最优比对的算法Biocomputing technology Multiple sequence alignment设有两条序列设有两条序列s、t, |s|=m, |t|=n;位点位点i 将序列将序列s一分为二一分为二, 位点位点j将序列将序列t一分为二一分为二, 那么那么

22、:序列序列s、t 对于经过特定断点对于经过特定断点i、j的最优比对可分为两个部分的最优比对可分为两个部分: 对应于两条序列前缀对应于两条序列前缀0:s:i 与与0:t:j 的最优比对的最优比对; 对应于两条序列后缀对应于两条序列后缀 i:s:m与与j:t:n 的最优比对的最优比对; 例例: :Biocomputing technology Multiple sequence alignment比对两条序列比对两条序列: s=ATTCGG, t=GATTC打分函数打分函数: p(a,a)=1, p(a,b)=-1, p(a,-)=p(-,b)=-1Biocomputing technology

23、Multiple sequence alignment 如果超晶格空间中的一个节点想任意两条序列所在如果超晶格空间中的一个节点想任意两条序列所在的平面投影的平面投影,投影在这些投影在这些” 断点断点中中,则超晶格空间中的这则超晶格空间中的这个节点就是与最优路径相关的节点个节点就是与最优路径相关的节点,否则不是相关节点否则不是相关节点.小结小结: 在进行多重序列比对时在进行多重序列比对时, 首先要进行序列的两两比对首先要进行序列的两两比对,其目的就是要找到任意两条序列通过特定断点的最优比对其目的就是要找到任意两条序列通过特定断点的最优比对,找到这些断点找到这些断点,然后然后,将多重比对中的超晶格

24、空间的节点向将多重比对中的超晶格空间的节点向任意两条序列所在的平面投影任意两条序列所在的平面投影,看看投影是否在这些断点上看看投影是否在这些断点上,如果节点向各个平面的投影均在相应的断点上如果节点向各个平面的投影均在相应的断点上,则这个节点则这个节点是与多重序列比对的最优路径相关的节点是与多重序列比对的最优路径相关的节点,否则否则,就不是相就不是相关节点关节点,要进行要进行剪枝剪枝处置处置.Biocomputing technology Multiple sequence alignment(1) 设设 是关于是关于s1s2sk 的最优比对，假如的最优比对，假如 SP_score( ) L，那

25、么，那么 score( i,j ) Li,j (4-6 )其中，其中， score( i,j ) 是是 在在si 和和sj 所在平面投影的得分所在平面投影的得分, 这里这里,L实际上是最优多重序列比对的一个下限实际上是最优多重序列比对的一个下限, Lij是序列是序列si 和序列和序列sj 比对得分的一个下限比对得分的一个下限 虽然最优多重比对的投影不一定是两两最优比对，虽然最优多重比对的投影不一定是两两最优比对，但是我们可以为投影的得分设立一个下限。但是我们可以为投影的得分设立一个下限。 ) )s,(sim(sLLj)(i,y)(x,y,xyxij判断超晶格空间中一个节点是否是相关节点的方法：

26、判断超晶格空间中一个节点是否是相关节点的方法：Biocomputing technology Multiple sequence alignment(2) 现在的问题现在的问题: 需要判断超晶格中的一个节点需要判断超晶格中的一个节点 i = (i1,i2,ik ) 是是否在否在L 的限制下与最优比对相关。的限制下与最优比对相关。 (3) 简单地说简单地说, 如果一个节点的所有投影满足如果一个节点的所有投影满足(4-6 )式的式的 条件，则该节点是相关的。若条件不满足，条件，则该节点是相关的。若条件不满足， 即即score( i,j )小，则该节点不可能是相关的，小，则该节点不可能是相关的， 因

27、而，因而，i 肯定不会处于最优路径上。肯定不会处于最优路径上。 (4) 公式公式(4-6)的条件只是一个必要条件，但不是充分条件。的条件只是一个必要条件，但不是充分条件。 满足条件只是说明满足条件只是说明i 可能处于最优路径，但不一定处于可能处于最优路径，但不一定处于 最优路径。公式最优路径。公式(4-6)条件的作用是限制搜索空间，进步条件的作用是限制搜索空间，进步 算法的实施效率。算法的实施效率。 Biocomputing technology Multiple sequence alignment(5) 将判断条件公式将判断条件公式(4-6)进一步具体化，进一步具体化， 则对于所有的则对于

28、所有的1xyk，如果，如果i 满足满足 Cx,y ix,iy Lx,y （4-7 ） 则则i 是相关的。是相关的。 这里，这里， Cx,y是序列是序列sx 和和sy 的总得分矩阵的总得分矩阵; Cx,y ix,iy 表示在点表示在点 ix,iy 处的值处的值,即即 经过经过ix,iy断点的断点的sx和和sy的最优比对得分的最优比对得分 ; ix,iy是断点是断点; Lx,y是是sx 和和sy 的比对得分的下限的比对得分的下限 注意注意: 尽管不是所有的相关节点均参与最优比对尽管不是所有的相关节点均参与最优比对, 但只有与最优路径相关的节点才参与最优比对但只有与最优路径相关的节点才参与最优比对.

29、Biocomputing technology Multiple sequence alignment(6) 判断非相关节点的方法判断非相关节点的方法: 假设假设是关于是关于s1s2sk 的最优比对，其所对应的的最优比对，其所对应的路径通过节点路径通过节点 i= ( i1,i2,ix,iy,ik ),那么那么: Cx,y ix,iy Score(i,j) Lx,y反之反之, 假如假如 Cx,y ix,iy Lx,y ,则多重序列最优比对则多重序列最优比对路径不会经过节点路径不会经过节点 i= ( i1,i2,ix,iy,ik ), 因而因而,该超该超晶格节点是非相关节点晶格节点是非相关节点.

30、Biocomputing technology Multiple sequence alignment 为了得到一个合理的下限为了得到一个合理的下限 L，我们可以任选一个包含，我们可以任选一个包含所有序列的多重比对，计算其得分，以此作为所有序列的多重比对，计算其得分，以此作为 L。若选取。若选取的的 L 接近于最优值，算法速度将大大提高。接近于最优值，算法速度将大大提高。注意：注意：L 的值不能超过最优值，否则算法出错。的值不能超过最优值，否则算法出错。 在实现上述优化计算方法时，必须非常仔细。不可能在实现上述优化计算方法时，必须非常仔细。不可能对超晶格中的每一个节点都进行上述判断，否则，计算

31、时对超晶格中的每一个节点都进行上述判断，否则，计算时间不会有多大的减少。我们需要一种完全消除无关单元的间不会有多大的减少。我们需要一种完全消除无关单元的方法方法, 以便不需再处理它们。以便不需再处理它们。下面介绍一种可能的策略下面介绍一种可能的策略:Biocomputing technology Multiple sequence alignment 在计算机中实现在计算机中实现“剪枝剪枝技术的措施技术的措施-1: 从超晶格的零点从超晶格的零点0 = (0, 0, , 0) 动身动身, 此节点总此节点总 是相关的是相关的, 并影响依赖于它的节点并影响依赖于它的节点. 每个这样的节点每个这样的节

32、点 又有它自己的受影响的节点又有它自己的受影响的节点, 如此展开如此展开, 直至达到在直至达到在 最终角落的节点最终角落的节点( n1n2nk ).(2) 以数组以数组a 保存各节点的计算结果保存各节点的计算结果. 如果在计算如果在计算a j 时用到时用到i, 称节点称节点i 影响另一个节点影响另一个节点j, 又称又称,节点节点j 依赖于节点依赖于节点i。 每个节点依赖于至多每个节点依赖于至多2k-1个其它节点个其它节点,也至多影响也至多影响 2k-1个其它节点个其它节点.(3) 节点节点i 和节点和节点j 关系的另一特征是：关系的另一特征是：b=j- i b是一个非零的二进向量是一个非零的二

33、进向量.Biocomputing technology Multiple sequence alignment在计算机中实现在计算机中实现“剪枝剪枝技术的措施技术的措施-2:(4) 为了便于处理，设置一个缓冲区，该缓冲区内仅存放为了便于处理，设置一个缓冲区，该缓冲区内仅存放 相关节点的后续节点。相关节点的后续节点。(5) 首先将首先将0 放入其中。放入其中。(6) 当节点当节点i 进入缓冲区时，其对应的值进入缓冲区时，其对应的值a i 被初始化，被初始化， 然后然后a i 的值在随后的阶段中被更新。的值在随后的阶段中被更新。 当节点当节点i 离开缓冲区时，其值即为该点真正的值，并用离开缓冲区时

34、，其值即为该点真正的值，并用 于其他节点于其他节点(依赖于此节点依赖于此节点)的计算。的计算。(7) 节点节点i 的后续节点是否要计算，还取决于的后续节点是否要计算，还取决于i 是否为相关是否为相关 节点，若不是，则不再计算其后续的其他节点。节点，若不是，则不再计算其后续的其他节点。具体实现过程具体实现过程:Biocomputing technology Multiple sequence alignment设节点设节点j 是一个依赖于节点是一个依赖于节点i 的相关节点，的相关节点，如果如果j 不在缓冲区内，则将其放入缓冲区，并计算不在缓冲区内，则将其放入缓冲区，并计算 a j a i +SP

35、_Score( Colum(s, i, b) )(3) 如果如果j 早已在缓冲区中，则按下式更新早已在缓冲区中，则按下式更新 a j max( a j , a i +SP_Score( Colum(s,i, b) ) )注意注意: Carrilo-Lipman 算法要求待比较的多个序列具有较大算法要求待比较的多个序列具有较大 的相似性，并且序列数不能太多。的相似性，并且序列数不能太多。4.2.4 星形比对星形比对Biocomputing technology Multiple sequence alignment* 启发式方法作为首选。启发式方法作为首选。* 启发式方法不一定保证最终能得到最优

36、解，但在大多数启发式方法不一定保证最终能得到最优解，但在大多数 情况下，其计算结果接近于最优结果。情况下，其计算结果接近于最优结果。* 启发式这类方法能够大大减少所需的计算时间，加快计启发式这类方法能够大大减少所需的计算时间，加快计 算速度。算速度。 * 渐进法是多重序列比对中常用到的启发式方法。其基本渐进法是多重序列比对中常用到的启发式方法。其基本 思想是将序列多重比对转化为序列两两比对，逐渐将两思想是将序列多重比对转化为序列两两比对，逐渐将两 两比对组合起来，最终形成完整的多序列比对。两比对组合起来，最终形成完整的多序列比对。 * 组合两两序列比对的方法有：组合两两序列比对的方法有： 星形

37、结构或者树形结构。星形结构或者树形结构。 1. 星形比对的基本思想：星形比对的基本思想： 星形比对是一种启发式方法，首先由星形比对是一种启发式方法，首先由Gusfield 提出。提出。 在给定的若干序列中，选择一个核心序列，通过该序在给定的若干序列中，选择一个核心序列，通过该序列与其它序列的两两比对形成所有序列的多重比对列与其它序列的两两比对形成所有序列的多重比对 ，从，从而使得而使得 在核心序列和任何一个其它序列方向的投影是最在核心序列和任何一个其它序列方向的投影是最优的两两比对。优的两两比对。Biocomputing technology Multiple sequence alignme

38、nt2. 星形比对算法概述星形比对算法概述-1Biocomputing technology Multiple sequence alignment* 设设s1,s2,sk是是k 条待比对的序列。条待比对的序列。* 假设已知核心序列是假设已知核心序列是sc，1c k，则可以利用标准的，则可以利用标准的 动态规划算法求出所有动态规划算法求出所有sc 和和si 的最优两两比对。的最优两两比对。 这个工作的时间复杂度为这个工作的时间复杂度为O(kn2), 假设所有序列的长度约为假设所有序列的长度约为n。* 将这些序列的两两比对聚集起来，并采用将这些序列的两两比对聚集起来，并采用“只要是空位，那么只要

39、是空位，那么 永远是空位永远是空位的原则。的原则。* 聚集过程从某一个两两比对开始，然后逐步加上其他的两聚集过程从某一个两两比对开始，然后逐步加上其他的两 两比对。在这个过程中，逐步增加两比对。在这个过程中，逐步增加sc中的空位字符，以适应中的空位字符，以适应 其他的比对，但决不删除其他的比对，但决不删除sc中已存在的空位字符。中已存在的空位字符。2. 星形比对算法概述星形比对算法概述-2Biocomputing technology Multiple sequence alignment* 随着后续比对的不断加入随着后续比对的不断加入, 一方面我们有一个由一方面我们有一个由sc指导的、指导的

40、、 已经建立好的部分序列的多重比对，另一方面我们有已经建立好的部分序列的多重比对，另一方面我们有sc与与 一个新序列之间的比对。在两种比对中我们插入尽可能少一个新序列之间的比对。在两种比对中我们插入尽可能少 而必要的空位而必要的空位, 以保持与扩展的以保持与扩展的sc序列相匹配。然后序列相匹配。然后,将新将新 扩展的序列加入序列群中扩展的序列加入序列群中, 且它和其它扩展的序列具有相且它和其它扩展的序列具有相 同的长度。同的长度。 * 这个过程一直进行到所有的两两比对都加入以后结束，这这个过程一直进行到所有的两两比对都加入以后结束，这 一步所需的计算量为一步所需的计算量为O(k2n)。* 算法

41、总的时间复杂度为算法总的时间复杂度为O(kn2+k2n)。scs1s2sk(sc, s1) (sc, s2) (sc, sk)两两比对两两比对 多重比对多重比对Biocomputing technology Multiple sequence alignment方法方法1：尝试将每一个序列分别作为核心序列，：尝试将每一个序列分别作为核心序列， 进行星形多重序列比对，取比对结果最进行星形多重序列比对，取比对结果最 好的一个。即好的一个。即SP得分最高的为最好。得分最高的为最好。方法方法2：是计算所有的两两比对，取下式值最大：是计算所有的两两比对，取下式值最大 的一个：的一个：3. 如何选择核心序

42、列？如何选择核心序列？Biocomputing technology Multiple sequence alignmentcici)s,ssim( 4.举例举例 有有5 5个序列：个序列： s1 = ATTGCCATTs1 = ATTGCCATT s2 = ATGGCCATT s2 = ATGGCCATT s3 = ATCCAATTTT s3 = ATCCAATTTT s4 = ATCTTCTT s4 = ATCTTCTT s5 =ACTGACC s5 =ACTGACCsc=s1ATTGCCATT ATTGCCATT- ATTGCCATT ATTGCCATTATGGCCATT ATC-CAA

43、TTTT ATCTTC-TT ACTGACC- (s1,s2) (s1,s3) (s1,s4) (s1,s5)ATTGCCATT-ATGGCCATT- ATC-CAATTTT ATCTTC-TT- ACTGACC- Biocomputing technology Multiple sequence alignment 星形比对是一种多重序列比对近似的方法，然星形比对是一种多重序列比对近似的方法，然而是一种比较好的近似方法。如果用代价来评判多而是一种比较好的近似方法。如果用代价来评判多重序列的比对结果，则可以证明，用该方法所得到重序列的比对结果，则可以证明，用该方法所得到多重序列比对的代价不会大

44、于最优多重序列比对代多重序列比对的代价不会大于最优多重序列比对代价的两倍。价的两倍。 Biocomputing technology Multiple sequence alignment4.2.5 树形比对树形比对k k个待比对的序列个待比对的序列 具有具有k k个叶节点的树个叶节点的树每个叶节点对应一条序列每个叶节点对应一条序列将序列赋予树的内部节点，可以计算树中每个分支的权值。将序列赋予树的内部节点，可以计算树中每个分支的权值。权值代表对应分支连接的两个序列之间的相似性。权值代表对应分支连接的两个序列之间的相似性。所有权值的和就是这棵树的得分所有权值的和就是这棵树的得分树形比对的问题：寻

45、找一种树的内部节点序列赋予方式，树形比对的问题：寻找一种树的内部节点序列赋予方式， 使得树的得分最大。使得树的得分最大。星型比对可以看作是树形比对的一种特例。星型比对可以看作是树形比对的一种特例。Biocomputing technology Multiple sequence alignment将将CT、CG、CT分别赋予节点分别赋予节点 x、y、z，则树的得分为，则树的得分为8。CTCGCT多重序列比对多重序列比对 两两序列比对两两序列比对 合并两个比对比对的比对）合并两个比对比对的比对） Aligment of AlignmentAA算法算法打分函数：打分函数： Pa,a）=1 Pa,b

46、）= 0 （ab） Pa,-）=P（-,b）= -1111122G - TG - TC A TC A TC - GC - GC T GC T G比对结果：比对结果：Biocomputing technology Multiple sequence alignmentAA算法概述算法概述-1Biocomputing technology Multiple sequence alignment假设有两个多重比对假设有两个多重比对1和和2 1代表序列代表序列s1,s2,si的多重比对的多重比对 2代表序列代表序列t1,t2,tj的多重比对的多重比对并且并且,( s1,s2,si ) ( t1,t2,

47、tj )= 代表代表s1和和t1的两两比对的两两比对, 那么那么计算与计算与相一致的相一致的1 和和2比对的算法如下比对的算法如下:AA算法概述算法概述-2Biocomputing technology Multiple sequence alignment标定标定1的各列的各列, 如果如果s1在比对中对应位置的编辑操作不是在比对中对应位置的编辑操作不是插入或删除插入或删除,则这些列分别标记为则这些列分别标记为s1对应位置上的字符对应位置上的字符: a1,a2,al1 s1=l1 标定标定2的各列的各列, 如果如果t1在比对中对应位置的编辑操作不在比对中对应位置的编辑操作不是是 插入或删除插入

48、或删除,则这些列分别标记为则这些列分别标记为t1对应位置上的字符对应位置上的字符: b1,b2,bl2 t1=l2 对对a1,a2,al1 和和b1,b2,bl2 进行比对进行比对, 在所得到的比对中在所得到的比对中,对于对于1、2和和中原来有插入或删除中原来有插入或删除操操 作的位置作的位置, 恢复其原有的实际字符或空位字符恢复其原有的实际字符或空位字符”-”.Biocomputing technology Multiple sequence alignmenta1 a2a3a4b1 b2b3b4b5对于对于n n个序列的树形比对的基本算法过程如下：个序列的树形比对的基本算法过程如下：（1

49、1初始化，对于每个序列，生成一个叶节点初始化，对于每个序列，生成一个叶节点（2 2利用利用AAAA算法合并两个节点，形成一个新节点，算法合并两个节点，形成一个新节点， 合并的结果放在新节点中，原来的两个节点作为合并的结果放在新节点中，原来的两个节点作为 新节点的子节点新节点的子节点（3 3反复执行反复执行2 2），直到形成），直到形成n n个叶节点的树根为止，个叶节点的树根为止， 根节点中的序列即为最终的多重比对结果。根节点中的序列即为最终的多重比对结果。 s1 s2 s3 s41122Biocomputing technology Multiple sequence alignment4.2

50、.6 CLUSTAL 算法算法Biocomputing technology Multiple sequence alignment CLUSTAL 算法是一种渐进的比对方法，它是由算法是一种渐进的比对方法，它是由D.G.Higgins和和 P.M.Sharp 于于1988年首次提出的。年首次提出的。目的：目的： 对来自不同物种的功能相同或相似的蛋白进行比对对来自不同物种的功能相同或相似的蛋白进行比对和聚类分析，可对这些物种的亲缘关系进行判断，并且和聚类分析，可对这些物种的亲缘关系进行判断，并且对这些蛋白在生物进化过程中的保守性作出估计。对这些蛋白在生物进化过程中的保守性作出估计。 Clust

51、al算法包括三个阶段：算法包括三个阶段：1. 1. 先将多重序列进行两两比对。基于这些比对，计算得到先将多重序列进行两两比对。基于这些比对，计算得到 一个距离矩阵，该矩阵反映每对序列之间的关系。一个距离矩阵，该矩阵反映每对序列之间的关系。2. 2. 根据距离矩阵计算产生系统发育树，以此来确定被比较根据距离矩阵计算产生系统发育树，以此来确定被比较 序列间相似的程度序列间相似的程度3. 3. 有了这棵系统发育树的指导，从关系最紧密的两条序列有了这棵系统发育树的指导，从关系最紧密的两条序列 开场，逐步引入邻近的序列或序列组，并不断重新构建开场，逐步引入邻近的序列或序列组，并不断重新构建 比对，直到所

52、有序列都被加入为止。比对，直到所有序列都被加入为止。Biocomputing technology Multiple sequence alignment举例：举例：Biocomputing technology Multiple sequence alignment已知三级结构的七个球蛋白序列，分别为：已知三级结构的七个球蛋白序列，分别为： Hbb_Human : 人的人的-球蛋白球蛋白Hbb_Horse : 马的马的-球蛋白球蛋白 Hba_Human : 人的人的-球蛋白球蛋白Hba_Horse : 马的马的-球蛋白球蛋白 Myg_phyca : 抹香鲸的血红蛋白抹香鲸的血红蛋白 Glb5

53、_petma : 七鳃鳗蓝血红蛋白七鳃鳗蓝血红蛋白Lgb2_Luplu : 羽扇豆的豆血红蛋白羽扇豆的豆血红蛋白第一阶段：两两比对产生距离矩阵第一阶段：两两比对产生距离矩阵Biocomputing technology Multiple sequence alignment 用完全动态规划法计算的用完全动态规划法计算的7个球蛋白序列之间的个球蛋白序列之间的77的距离矩阵的距离矩阵 第二阶段：产生指导树第二阶段：产生指导树Biocomputing technology Multiple sequence alignment 根据第一阶段结果中的距离矩阵，用邻近归并法来根据第一阶段结果中的距离矩阵

54、，用邻近归并法来计算产生一棵有分枝长度和序列权重的有根树。计算产生一棵有分枝长度和序列权重的有根树。 第三阶段：渐进的比对第三阶段：渐进的比对Biocomputing technology Multiple sequence alignment 这一阶段基本的步骤是通过一系列两两比对来构建更这一阶段基本的步骤是通过一系列两两比对来构建更大的比对序列组。按照指导树中的分支顺序，从有根树的大的比对序列组。按照指导树中的分支顺序，从有根树的末梢到树根逐渐进行。根据图末梢到树根逐渐进行。根据图4.22的有根树，通过下面的的有根树，通过下面的顺序对序列进行比对：顺序对序列进行比对：(1)对对(2)(3)

55、对对(4)(8)对对(9) (5)对对(10)(6)对对(11)(7)对对(12)。* 每一阶段使用了有残基权重矩阵和空位开放及空位扩展罚每一阶段使用了有残基权重矩阵和空位开放及空位扩展罚 分的完全动态规划算法。分的完全动态规划算法。* 每一阶段都由对两个已经存在的排列或序列进行比对组成。每一阶段都由对两个已经存在的排列或序列进行比对组成。* 在先前比对中出现的空位仍然是固定的在先前比对中出现的空位仍然是固定的 图4.23Biocomputing technology Multiple sequence alignment序列权重的作用序列权重的作用: 计算多重序列比对得分计算多重序列比对得分

56、Biocomputing technology Multiple sequence alignment peeksavtalpeeksavtal geekaavlalgeekaavlal padktnvkaapadktnvkaa aadktnvkaaaadktnvkaa egewqlvlhvegewqlvlhv aaektkirsaaaektkirsa多重序列比对的统计特征分析多重序列比对的统计特征分析 对于所得到的多重序列比对，我们往往需要进行归纳分对于所得到的多重序列比对，我们往往需要进行归纳分析，总结这些序列的特征，或者给出这些序列共性的表示。析，总结这些序列的特征，或者给出这些序列共性

57、的表示。表示方式表示方式1 1：保守序列表示方式：保守序列表示方式 表示出序列每个位置上最可能出现的字符表示出序列每个位置上最可能出现的字符 或所有可能出现的字符或所有可能出现的字符表示方式表示方式2 2；特征统计图谱；特征统计图谱profileprofile表示方式表示方式 （或特征统计矩阵表示方法）（或特征统计矩阵表示方法）Biocomputing technology Multiple sequence alignment令令P=(P1,P2,Pj,PL )；P表示在多重比对表示在多重比对的每一列上各种的每一列上各种 字符出现的概率分布字符出现的概率分布Pj=(pj0,pj1,pj|A|

58、)；A代表字母表，代表字母表， Pjk代表字母表代表字母表A中第中第k个字符在第个字符在第j列列 出现的概率。出现的概率。 pj0：第：第0个字符是特殊的空位符号个字符是特殊的空位符号“-”。称称P为多重序列比对为多重序列比对的特征统计图谱或特征统计矩阵。的特征统计图谱或特征统计矩阵。 P反映了多重序列比对反映了多重序列比对各个列的特征。各个列的特征。表示方法表示方法2 2：特征统计图谱：特征统计图谱Biocomputing technology Multiple sequence alignment 1 2 3 4 5 (位置位置) A 0.8 0.2 0.2 0.6 0.0 T 0.0 0

59、.4 0.6 0.4 1.0 C 0.2 0.2 0.2 0.0 0.0 G 0.0 0.2 0.0 0.0 0.0 （碱基）（碱基）Biocomputing technology Multiple sequence alignment A T T A T A A C T T C T T A T A C T T T A G A A T 利用保守序列或者特征统计图可以判断一个序列是否满足利用保守序列或者特征统计图可以判断一个序列是否满足一定的特征一定的特征 给定一个序列给定一个序列s=a1a2ams=a1a2am，定义字符，定义字符a a在第在第j j位的代价为位的代价为 其中，其中，|A|A|

60、代表字母表代表字母表A A的长度，的长度， AkAk代表代表A A的第的第k k个字符，个字符， A0A0代表空缺字符代表空缺字符“-”-”。整个序列。整个序列s s的代价为的代价为|0),(),( AkjkkPAawjawjjawsw),( ),(*一条序列与特征统计图相对照，如果代价值小，说明该序一条序列与特征统计图相对照，如果代价值小，说明该序列具有相应的特征，否则该序列不具备相应的特征。列具有相应的特征，否则该序列不具备相应的特征。 Biocomputing technology Multiple sequence alignment4.2.7 隐马尔可夫模型隐马尔可夫模型 HMMBi