生物计算技术多重序列比对分析省公共课一等奖全国赛课获奖课件.pptx

Biocomputing technology Multiple sequence alignment第第4章章 多重序列比对分析多重序列比对分析目要求：1 掌握多重序列比对基本概念及意义。2 掌握多重序列比对星形比对、树形比对及隐马尔可夫模型。3 了解多重序列比对动态规划算法、CLUSTAL W 算法。教学内容：4.1 多重序列比对意义 4.2 多重序列比对算法原理Multiple sequence alignment第1页4.1 多重序列比对意义目标：目标：发觉多个序列共性发觉多个序列共性 发觉与结构和功效相关保守序列片段发觉与结构和功效相关保守序列片段定义：定义：设：有设：有k个序列个序列s1,s2,.,sk，每个序列由同一，每个序列由同一个字母表中字符组成，个字母表中字符组成，k大于大于2，经过插入，经过插入“空位空位”操作，使得各序列到达操作，使得各序列到达一样长度一样长度，从而形成这，从而形成这些序列多重比对。些序列多重比对。Biocomputing technology Multiple sequence alignment第2页8条免疫球蛋白序列片段多重比对：条免疫球蛋白序列片段多重比对：半光氨酸半光氨酸色氨酸色氨酸疏水残基疏水残基保守区域保守区域SPSP得分得分Biocomputing technology Multiple sequence alignment第3页Biocomputing technology Multiple sequence alignment 经过序列多重比对，能够得到一个序列家族序列经过序列多重比对，能够得到一个序列家族序列特征。当给定一个新序列时，依据序列特征，能够判断这特征。当给定一个新序列时，依据序列特征，能够判断这个序列是否属于该家族。个序列是否属于该家族。对于多序列比对，现有大多数算法都基于渐进比对对于多序列比对，现有大多数算法都基于渐进比对思想，在序列两两比正确基础上逐步优化多序列比正确思想，在序列两两比正确基础上逐步优化多序列比正确结果。结果。进行多序列比对后，能够对比对结果进行深入处理，进行多序列比对后，能够对比对结果进行深入处理，比如构建序列特征模式，将序列聚类、构建分子进化树等。比如构建序列特征模式，将序列聚类、构建分子进化树等。第4页4.2 多重序列比对算法原理多重序列比对算法原理4.2.1 SP模型4.2.2 多重比对动态规划算法4.2.3 优化算法4.2.4 星型比对4.2.5 树形比对4.2.6 CLUSTALW算法4.2.7隐马尔可夫模型Biocomputing technology Multiple sequence alignment第5页4.2.1 SP 模型模型 (Sum-of-Pairs)逐对加和函数逐对加和函数作用：评价多重序列比对结果SPSP计算两种方法：计算两种方法：Biocomputing technology Multiple sequence alignment第6页方法方法1 1：先计算多重比对结果每一列字符得分，：先计算多重比对结果每一列字符得分，然后求整体多重比对得分然后求整体多重比对得分Biocomputing technology Multiple sequence alignment假设假设:得分函数得分函数(代价函数代价函数)含有加和性，即多重比正确得分含有加和性，即多重比正确得分 是各列得分总和。是各列得分总和。思绪思绪:怎样给比正确每一列打分，然后将各列和加起来，怎样给比正确每一列打分，然后将各列和加起来，成为一个总得分。成为一个总得分。每一列处理方式每一列处理方式:寻找一个含有寻找一个含有k 个变量打分函数个变量打分函数，每一个变量或者是，每一个变量或者是 一个来自特定字母表中字符，或者是一个空位。一个来自特定字母表中字符，或者是一个空位。k 是参加多重比正确序列个数。是参加多重比正确序列个数。第7页Biocomputing technology Multiple sequence alignment显式函数应满足以下条件：显式函数应满足以下条件：1.函数形式简单，含有统一形式，不随序列个数函数形式简单，含有统一形式，不随序列个数2.而发生形式改变。而发生形式改变。2.依据得分函数意义，函数值应独立于各参数次序，依据得分函数意义，函数值应独立于各参数次序，即与待比较序列先后次序无关。即与待比较序列先后次序无关。3.对相同或相同字符比对，奖励得分值高，而对对相同或相同字符比对，奖励得分值高，而对 于不相关字符比对或空白，则进行处罚（得分为负值）。于不相关字符比对或空白，则进行处罚（得分为负值）。满足上述条件一个函数就是惯用逐对加和函数，满足上述条件一个函数就是惯用逐对加和函数，SP函数函数。第8页方法方法1 1：先计算多重比对结果每一列字符得分，：先计算多重比对结果每一列字符得分，然后求整体多重比对得分然后求整体多重比对得分其中，其中，c1,c2,ck是一列中是一列中k个字符，个字符，p是关于一对字符相同性打分函数。是关于一对字符相同性打分函数。SP_score(c1,c2,ck)是多重序列比对中某一列是多重序列比对中某一列 得分得分.Biocomputing technology Multiple sequence alignment第9页例：图例：图4.1多重比正确倒数第多重比正确倒数第3列列SP得分：得分：打分函数：打分函数：P（a,a）=0 P（a,b）=-1 （ab）P（a,-）=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-5-4-3-2-1）+2=-26然后将一个多重比对全部列得分全部加起来，其和即为该多重比正确得分。然后将一个多重比对全部列得分全部加起来，其和即为该多重比正确得分。将全部多重比正确得分计算出来进行比较，得分最高，应该是最好。将全部多重比正确得分计算出来进行比较，得分最高，应该是最好。Biocomputing technology Multiple sequence alignment第10页多重比对在两条特定序列上投影多重比对在两条特定序列上投影Biocomputing technology Multiple sequence alignment第11页方法方法2：先计算多重序列结果序列两两比对得分，：先计算多重序列结果序列两两比对得分，然后计算整体多重比对得分。然后计算整体多重比对得分。是一个多重比对是一个多重比对 ijij是由是由 推演出来序列推演出来序列s si i和和s sj j两两比对两两比对 方法方法1和方法和方法2等价条件：等价条件：P(-,-)=0Biocomputing technology Multiple sequence alignment第12页4.2.2 多重比对动态规划算法 多重序列比正确最终目标是经过处理得到一个得分最高多重序列比正确最终目标是经过处理得到一个得分最高（或代价最小）序列对比排列，从而分析各序列之间相同（或代价最小）序列对比排列，从而分析各序列之间相同性和差异性和差异。Biocomputing technology Multiple sequence alignment第13页4.2.2 多重比对动态规划算法s1:VSN-Ss2:-SNA-s3:-ASBiocomputing technology Multiple sequence alignment第14页前趋节点个数等于前趋节点个数等于2 2k k-1 -1 问题：问题：计算量巨大计算量巨大时间复杂度为时间复杂度为O(2k i=1,.,k si)O(2kNk)Biocomputing technology Multiple sequence alignment第15页NP-完全问题定义完全问题定义Biocomputing technology Multiple sequence alignment P 类问题为多项式界问题；类问题为多项式界问题；NP 类问题是这么一类问题，假如有一个复杂度为多类问题是这么一类问题，假如有一个复杂度为多项式算法处理其中某个问题，则全部这些问题都在项式算法处理其中某个问题，则全部这些问题都在P类中；类中；而而NP-完全问题是这么一类问题，假如其中某个问题存在完全问题是这么一类问题，假如其中某个问题存在多项式界算法，则多项式界算法，则NP 类中每一个问题都存在一个多项类中每一个问题都存在一个多项式界算法。式界算法。NP 完全问题通常被认为是一些人们难以在有限时间、完全问题通常被认为是一些人们难以在有限时间、空间内对问题求出最正确解问题，几乎全部教授都认为不可空间内对问题求出最正确解问题，几乎全部教授都认为不可能在多项式时间内准确求解能在多项式时间内准确求解NP-完全问题。完全问题。第16页NP-完全问题近似求解方法完全问题近似求解方法Biocomputing technology Multiple sequence alignment1.舍去寻找最优解要求，寻找对普通问题比较靠近舍去寻找最优解要求，寻找对普通问题比较靠近2.最优解近似解；最优解近似解；3.2.利用非常规求解技术求解，比如，利用神经网络、利用非常规求解技术求解，比如，利用神经网络、4.遗传算法等方法进行问题求解。遗传算法等方法进行问题求解。第17页生物信息学中生物信息学中NP-完全问题近似求解方法完全问题近似求解方法Biocomputing technology Multiple sequence alignment1.只求解规模比较小问题；只求解规模比较小问题；2.利用动态规划、分支约束等技术减小搜索空间，提升利用动态规划、分支约束等技术减小搜索空间，提升 求解问题效率；求解问题效率；3.针对详细问题特点，依据实际输入情况，设计实用针对详细问题特点，依据实际输入情况，设计实用 求解算法，这么算法即使在最坏情况下其时间复求解算法，这么算法即使在最坏情况下其时间复 杂度是非多项式，不过算法执行平均效率和复杂杂度是非多项式，不过算法执行平均效率和复杂 度与多项式算法相当；度与多项式算法相当；4.采取近似算法或者启发式方法，如局部搜索、模拟退火、采取近似算法或者启发式方法，如局部搜索、模拟退火、遗传算法等。遗传算法等。对基于对基于SP 模型寻找最优多重序列比对这么一个问题，模型寻找最优多重序列比对这么一个问题，能够用近似方法求解，其算法时间复杂度可用多项式表示。能够用近似方法求解，其算法时间复杂度可用多项式表示。第18页4.2.3 优化计算方法优化计算方法标准动态规划算法存在问题：标准动态规划算法存在问题：搜索空间大搜索空间大剪枝技术：将搜索空间限定在一个较小区域范围内。剪枝技术：将搜索空间限定在一个较小区域范围内。若问题是搜索一条得分最高（或代价最小）路径，则在搜若问题是搜索一条得分最高（或代价最小）路径，则在搜索时假如当前路径得分低于某个下限（或累积代价已经超索时假如当前路径得分低于某个下限（或累积代价已经超出某个上限），则对当前路径进行剪枝，即不再搜索当前出某个上限），则对当前路径进行剪枝，即不再搜索当前路径后续空间。路径后续空间。Biocomputing technology Multiple sequence alignment第19页Biocomputing technology Multiple sequence alignment 在序列两两比对中在序列两两比对中,Fickett 和和Ukkonen 设计了一个设计了一个称为称为定界约束过程定界约束过程(bounding procedure)方法来缩小搜方法来缩小搜索空间索空间,降低计算量降低计算量,其中距离矩阵上界和下界能够预先其中距离矩阵上界和下界能够预先确定或动态改变。确定或动态改变。为了在多维空间上使用动态规划算法，为了在多维空间上使用动态规划算法，Carrillo 和和Lipman 将这种思想引入到多重序列比对，即先进行初步将这种思想引入到多重序列比对，即先进行初步序列双重比对，以限制深入做多重序列全方面比对所需序列双重比对，以限制深入做多重序列全方面比对所需要多维空间大小和计算量，从而克服了多序列维数、要多维空间大小和计算量，从而克服了多序列维数、空间和运算量之间矛盾空间和运算量之间矛盾 第20页Carrillo-Lipman优化计算方法优化计算方法Biocomputing technology Multiple sequence alignment 设设k 条序列长度分别为条序列长度分别为n1n2nk，按照，按照SP 得分模得分模型计算这些序列最优比对。依然采取动态规划方法，但型计算这些序列最优比对。依然采取动态规划方法，但并不计算超晶格空间中全部节点，而是仅处理并不计算超晶格空间中全部节点，而是仅处理与最优路与最优路径径“相关相关”节点节点。不过，哪些节点是相关呢？这需要观。不过，哪些节点是相关呢？这需要观察节点在两条序列上投影。察节点在两条序列上投影。确定相关节点方法：确定相关节点方法：假设假设是关于是关于k 条序列条序列s1s2sk 最优多重比对。最优多重比对。从某个节点向任何两条序列所在平面投影，假如该投影从某个节点向任何两条序列所在平面投影，假如该投影是这两条序列两两最优比正确一部分（前面一部分），则是这两条序列两两最优比正确一部分（前面一部分），则该节点是与最优比对相关节点。该节点是与最优比对相关节点。问题提出问题提出:第21页一个计算两条序列经过特定断点最优比正确算法一个计算两条序列经过特定断点最优比正确算法Biocomputing technology Multiple sequence alignment设有两条序列设有两条序列s、t,|s|=m,|t|=n;位点位点i 将序列将序列s一分为二一分为二,位点位点j将序列将序列t一分为二一分为二,则则:序列序列s、t 对于经过特定断点（对于经过特定断点（i、j）最优比对可分为两个部分）最优比对可分为两个部分:对应于两条序列前缀对应于两条序列前缀0:s:i 与与0:t:j 最优比对最优比对;对应于两条序列后缀对应于两条序列后缀 i:s:m与与j:t:n 最优比对最优比对;第22页例例:Biocomputing technology Multiple sequence alignment比对两条序列比对两条序列:s=ATTCGG,t=GATTC打分函数打分函数:p(a,a)=1,p(a,b)=-1,p(a,-)=p(-,b)=-1第23页Biocomputing technology Multiple sequence alignment 假如超晶格空间中一个节点想假如超晶格空间中一个节点想任意任意两条序列所在两条序列所在平面投影平面投影,投影在这些投影在这些”断点断点”中中,则超晶格空间中这则超晶格空间中这个节点就是与最优路径相关节点个节点就是与最优路径相关节点,不然不是相关节点不然不是相关节点.小结小结:在进行多重序列比对时在进行多重序列比对时,首先要进行序列两两比对首先要进行序列两两比对,其目标就是要找到任意两条序列经过特定断点最优比对其目标就是要找到任意两条序列经过特定断点最优比对,找到这些断点找到这些断点,然后然后,将多重比对中超晶格空间节点向将多重比对中超晶格空间节点向任意两条序列所在平面投影任意两条序列所在平面投影,看看投影是否在这些断点上看看投影是否在这些断点上,假如节点向各个平面投影均在对应断点上假如节点向各个平面投影均在对应断点上,则这个节点则这个节点是与多重序列比正确最优路径相关节点是与多重序列比正确最优路径相关节点,不然不然,就不是相就不是相关节点关节点,要进行要进行”剪枝剪枝”处理处理.第24页Biocomputing technology Multiple sequence alignment(1)设设 是关于是关于s1s2sk 最优比对，假如最优比对，假如 SP_score()L，则，则 score(i,j)Li,j (4-6)其中，其中，score(i,j)是是 在在si 和和sj 所在平面投影得分所在平面投影得分,这里这里,L实际上是最优多重序列比正确一个下限实际上是最优多重序列比正确一个下限,Lij是序列是序列si 和序列和序列sj 比对得分一个下限比对得分一个下限 虽然最优多重比对投影不一定是两两最优比对，不过我们可认为投影得分设立一个下限。判断超晶格空间中一个节点是否是相关节点方法：判断超晶格空间中一个节点是否是相关节点方法：第25页Biocomputing technology Multiple sequence alignment(2)现在问题现在问题:需要判断超晶格中一个节点需要判断超晶格中一个节点 i=(i1,i2,ik)是是否在否在L 限制下与最优比对相关。限制下与最优比对相关。(3)简单地说简单地说,假如一个节点全部投影满足假如一个节点全部投影满足(4-6)式式 条件，则该节点是相关。若条件不满足，条件，则该节点是相关。若条件不满足，即即score(i,j)小，则该节点不可能是相关，小，则该节点不可能是相关，所以，所以，i 必定不会处于最优路径上。必定不会处于最优路径上。(4)公式公式(4-6)条件只是一个必要条件，但不是充分条件。条件只是一个必要条件，但不是充分条件。满足条件只是说明满足条件只是说明i 可能可能处于最优路径，但处于最优路径，但不一定不一定处于处于 最优路径。公式最优路径。公式(4-6)条件作用是限制搜索空间，提升条件作用是限制搜索空间，提升 算法实施效率。算法实施效率。第26页Biocomputing technology Multiple sequence alignment(5)将判断条件公式将判断条件公式(4-6)深入详细化，深入详细化，则对于全部则对于全部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 比对得分下限比对得分下限 注意注意:尽管不是全部相关节点均参加最优比对尽管不是全部相关节点均参加最优比对,但只有与最优路径相关节点才参加最优比对但只有与最优路径相关节点才参加最优比对.第27页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),因而因而,该超该超晶格节点是晶格节点是非相关节点非相关节点.第28页Biocomputing technology Multiple sequence alignment 为了得到一个合理下限为了得到一个合理下限 L，我们能够任选一个包含，我们能够任选一个包含全部序列多重比对，计算其得分，以此作为全部序列多重比对，计算其得分，以此作为 L。若选取。若选取 L 靠近于最优值，算法速度将大大提升。靠近于最优值，算法速度将大大提升。注意：注意：L 值不能超出最优值，不然算法犯错。值不能超出最优值，不然算法犯错。在实现上述优化计算方法时，必须非常仔细。不可能在实现上述优化计算方法时，必须非常仔细。不可能对超晶格中每一个节点都进行上述判断，不然，计算时对超晶格中每一个节点都进行上述判断，不然，计算时间不会有多大降低。我们需要一个完全消除无关单元间不会有多大降低。我们需要一个完全消除无关单元方法方法,方便不需再处理它们。方便不需再处理它们。下面介绍一个可能策略下面介绍一个可能策略:第29页Biocomputing technology Multiple sequence alignment 在计算机中实现在计算机中实现“剪枝剪枝”技术办法技术办法-1:(1)从超晶格零点从超晶格零点0=(0,0,0)出发出发,此节点总此节点总(2)是相关是相关,并影响依赖于它节点并影响依赖于它节点.每个这么节点每个这么节点(3)又有它自己受影响节点又有它自己受影响节点,如此展开如此展开,直至到达在直至到达在(4)最终角落节点最终角落节点(n1n2nk).(5)(2)以数组以数组a 保留各节点计算结果保留各节点计算结果.(6)假如在计算假如在计算a j 时用到时用到i,称节点称节点i 影响另一个节点影响另一个节点j,(7)又称又称,节点节点j 依赖于节点依赖于节点i。(8)每个节点依赖于至多每个节点依赖于至多2k-1个其它节点个其它节点,也至多影响也至多影响(9)2k-1个其它节点个其它节点.(10)(3)节点节点i 和节点和节点j 关系另一特征是：关系另一特征是：b=j-i(11)b是一个非零二进向量是一个非零二进向量.第30页Biocomputing technology Multiple sequence alignment在计算机中实现在计算机中实现“剪枝剪枝”技术办法技术办法-2:(4)为了便于处理，设置一个缓冲区，该缓冲区内仅存放为了便于处理，设置一个缓冲区，该缓冲区内仅存放 相关节点后续节点相关节点后续节点。(5)首先将首先将0 放入其中。放入其中。(6)当节点当节点i 进入缓冲区时，其对应值进入缓冲区时，其对应值a i 被初始化，被初始化，然后然后a i 值在随即阶段中被更新。值在随即阶段中被更新。当节点当节点i 离开缓冲区时，其值即为该点真正值，并用离开缓冲区时，其值即为该点真正值，并用 于其它节点于其它节点(依赖于此节点依赖于此节点)计算。计算。(7)节点节点i 后续节点是否要计算，还取决于后续节点是否要计算，还取决于i 是否为相关是否为相关 节点，若不是，则不再计算其后续其它节点。节点，若不是，则不再计算其后续其它节点。第31页详细实现过程详细实现过程:Biocomputing technology Multiple sequence alignment(1)设节点设节点j 是一个依赖于节点是一个依赖于节点i 相关节点，相关节点，(2)假如假如j 不在缓冲区内，则将其放入缓冲区，并计算不在缓冲区内，则将其放入缓冲区，并计算(3)a j a i+SP_Score(Colum(s,i,b)(3)假如假如j 早已在缓冲区中，则按下式更新早已在缓冲区中，则按下式更新 a j max(a j,a i+SP_Score(Colum(s,i,b)注意注意:Carrilo-Lipman 算法要求待比较多个序列含有较大算法要求待比较多个序列含有较大 相同性，而且序列数不能太多。相同性，而且序列数不能太多。第32页4.2.4 星形比对星形比对Biocomputing technology Multiple sequence alignment*启发式方法启发式方法作为首选。作为首选。*启发式方法启发式方法不一定确保最终能得到最优解，但在大多数不一定确保最终能得到最优解，但在大多数 情况下，其计算结果靠近于最优结果。情况下，其计算结果靠近于最优结果。*启发式启发式这类方法能够大大降低所需计算时间，加紧计这类方法能够大大降低所需计算时间，加紧计 算速度。算速度。*渐进法渐进法是多重序列比对中惯用到启发式方法。其基本是多重序列比对中惯用到启发式方法。其基本 思想是将序列多重比对转化为序列两两比对，逐步将两思想是将序列多重比对转化为序列两两比对，逐步将两 两比对组合起来，最终形成完整多序列比对。两比对组合起来，最终形成完整多序列比对。*组合两两序列比对方法有：星形结构或者树形结构。第33页1.星形比对基本思想：星形比对是一个启发式方法，首先由星形比对是一个启发式方法，首先由Gusfield 提出。提出。在给定若干序列中，选择一个在给定若干序列中，选择一个关键序列关键序列，经过该序列与，经过该序列与其它序列两两比对形成全部序列多重比对其它序列两两比对形成全部序列多重比对 ，从而使得，从而使得 在在关键序列和任何一个其它序列方向投影是最优两两比对关键序列和任何一个其它序列方向投影是最优两两比对。Biocomputing technology Multiple sequence alignment第34页2.星形比对算法概述星形比对算法概述-1Biocomputing technology Multiple sequence alignment*设设s1,s2,sk是是k 条待比正确序列。条待比正确序列。*假设已知关键序列是假设已知关键序列是sc，1c k，则能够利用标准，则能够利用标准 动态规划算法求出全部动态规划算法求出全部sc 和和si 最优两两比对。最优两两比对。这个工作时间复杂度为这个工作时间复杂度为O(kn2),假设全部序列长度约为假设全部序列长度约为n。*将这些序列两两比对聚集起来，并采取将这些序列两两比对聚集起来，并采取“只要是空位，则只要是空位，则 永远是空位永远是空位”标准。标准。*聚集过程从某一个两两比对开始，然后逐步加上其它两聚集过程从某一个两两比对开始，然后逐步加上其它两 两比对。在这个过程中，逐步增加两比对。在这个过程中，逐步增加sc中空位字符，以适应中空位字符，以适应 其它比对，但其它比对，但决不删除决不删除sc中已存在空位字符中已存在空位字符。第35页2.星形比对算法概述星形比对算法概述-2Biocomputing technology Multiple sequence alignment*随着后续比对不停加入,一方面我们有一个由sc指导、已经建立好部分序列多重比对，其次我们有sc与 一个新序列之间比对。在两种比对中我们插入尽可能少 而必要空位,以保持与扩展sc序列相匹配。然后,将新 扩展序列加入序列群中,且它和其它扩展序列具有相 同长度。*这个过程一直进行到全部两两比对都加入以后结束，这 一步所需计算量为O(k2n)。*算法总时间复杂度为O(kn2+k2n)。第36页scs1s2sk(sc,s1)(sc,s2)(sc,sk)两两比对两两比对 多重比对多重比对Biocomputing technology Multiple sequence alignment第37页方法方法1：尝试将每一个序列分别作为关键序列，：尝试将每一个序列分别作为关键序列，进行星形多重序列比对，取比对结果最进行星形多重序列比对，取比对结果最 好一个。即好一个。即SP得分最高为最好。得分最高为最好。方法方法2：是计算全部两两比对，取下式值最大：是计算全部两两比对，取下式值最大 一个：一个：3.怎样选择关键序列？怎样选择关键序列？Biocomputing technology Multiple sequence alignment第38页4.举例举例 有有5 5个序列：个序列：s1=ATTGCCATT s2=ATGGCCATT s3=ATCCAATTTT s4=ATCTTCTT s5=ACTGACCsc=s1ATTGCCATT ATTGCCATT-ATTGCCATT ATTGCCATTATGGCCATT ATC-CAATTTT ATCTTC-TT ACTGACC-(s1,s2)(s1,s3)(s1,s4)(s1,s5)ATTGCCATT-ATGGCCATT-ATC-CAATTTT ATCTTC-TT-ACTGACC-Biocomputing technology Multiple sequence alignment第39页 星形比对是一个多重序列比对近似方法，然而是星形比对是一个多重序列比对近似方法，然而是一个比很好近似方法。假如用代价来评判多重序列比一个比很好近似方法。假如用代价来评判多重序列比对结果，则能够证实，用该方法所得到多重序列比正对结果，则能够证实，用该方法所得到多重序列比正确代价不会大于最优多重序列比对代价两倍。确代价不会大于最优多重序列比对代价两倍。Biocomputing technology Multiple sequence alignment第40页4.2.5 树形比对树形比对k k个待比正确序列个待比正确序列 含有含有k k个叶节点树个叶节点树每个叶节点对应一条序列每个叶节点对应一条序列将序列赋予树内部节点，能够计算树中每个分支权值。将序列赋予树内部节点，能够计算树中每个分支权值。权值代表对应分支连接两个序列之间相同性。权值代表对应分支连接两个序列之间相同性。全部权值和就是这棵树得分全部权值和就是这棵树得分树形比正确问题树形比正确问题：寻找一个树：寻找一个树内部节点序列赋予方式内部节点序列赋予方式，使得树得分最大。使得树得分最大。星型比对能够看作是树形比正确一个特例。星型比对能够看作是树形比正确一个特例。Biocomputing technology Multiple sequence alignment第41页将将CT、CG、CT分别赋予节点分别赋予节点 x、y、z，则树得分为，则树得分为8。CTCGCT多重序列比对 两两序列比对 合并两个比对（比对比对）Aligment of AlignmentAA算法打分函数：打分函数：P（a,a）=1 P（a,b）=0 （ab）P（a,-）=P（-,b）=-1111122G-TG-TC A TC A TC-GC-GC T GC T G比对结果：比对结果：Biocomputing technology Multiple sequence alignment第42页AA算法概述算法概述-1Biocomputing technology Multiple sequence alignment假设有两个多重比对假设有两个多重比对1和和2 1代表序列代表序列s1,s2,si多重比对多重比对 2代表序列代表序列t1,t2,tj多重比对多重比对而且而且,(s1,s2,si)(t1,t2,tj)=代表代表s1和和t1两两比对两两比对,则则计算与计算与相一致相一致1 和和2比正确算法以下比正确算法以下:第43页AA算法概述算法概述-2Biocomputing technology Multiple sequence alignment标定标定1各列各列,假如假如s1在比对中对应位置编辑操作不是插入或在比对中对应位置编辑操作不是插入或删除删除,则这些列分别标识为则这些列分别标识为s1对应位置上字符对应位置上字符:a1,a2,al1 s1=l1 标定标定2各列各列,假如假如t1在比对中对应位置编辑操作不是在比对中对应位置编辑操作不是 插入或删除插入或删除,则这些列分别标识为则这些列分别标识为t1对应位置上字符对应位置上字符:b1,b2,bl2 t1=l2 对对a1,a2,al1 和和b1,b2,bl2 进行比对进行比对,在所得到比对中在所得到比对中,对于对于1、2和和中原来有插入或删除操中原来有插入或删除操 作位置作位置,恢复其原有实际字符或空位字符恢复其原有实际字符或空位字符”-”.第44页Biocomputing technology Multiple sequence alignmenta1 a2a3a4b1 b2b3b4b5第45页对于对于n n个序列树形比正确基本算法过程以下：个序列树形比正确基本算法过程以下：（1 1）初始化，对于每个序列，生成一个叶节点）初始化，对于每个序列，生成一个叶节点（2 2）利用）利用AAAA算法合并两个节点，形成一个新节点，算法合并两个节点，形成一个新节点，合并结果放在新节点中，原来两个节点作为合并结果放在新节点中，原来两个节点作为 新节点子节点新节点子节点（3 3）重复执行（）重复执行（2 2），直到形成），直到形成n n个叶节点树根为止，个叶节点树根为止，根节点中序列即为最终多重比对结果。根节点中序列即为最终多重比对结果。s1 s2 s3 s41 12 2Biocomputing technology Multiple sequence alignment第46页4.2.6 CLUSTAL 算法算法Biocomputing technology Multiple sequence alignment CLUSTAL 算法是一个算法是一个渐进比对方法渐进比对方法，它是由，它是由D.G.Higgins和和 P.M.Sharp 于于1988年首次提出。年首次提出。目标：目标：对来自不一样物种功效相同或相同蛋白进行比对对来自不一样物种功效相同或相同蛋白进行比对和聚类分析，可对这些物种亲缘关系进行判断，而且和聚类分析，可对这些物种亲缘关系进行判断，而且对这些蛋白在生物进化过程中保守性作出预计。对这些蛋白在生物进化过程中保守性作出预计。第47页Clustal算法包含三个阶段：算法包含三个阶段：1.1.先将多重序列进行两两比对。基于这些比对，计算得到先将多重序列进行两两比对。基于这些比对，计算得到 一个距离矩阵，该矩阵反应每对序列之间关系。一个距离矩阵，该矩阵反应每对序列之间关系。2.2.依据距离矩阵计算产生依据距离矩阵计算产生系统发育树系统发育树，以此来确定被比较，以此来确定被比较 序列间相同程度序列间相同程度3.3.有了这棵系统发育树指导，从关系最紧密两条序列有了这棵系统发育树指导，从关系最紧密两条序列 开始，逐步引入邻近序列或序列组，并不停重新构建开始，逐步引入邻近序列或序列组，并不停重新构建 比对，直到全部序列都被加入为止。比对，直到全部序列都被加入为止。Biocomputing technology Multiple sequence alignment第48页举例：举例：Biocomputing technology Multiple sequence alignment已知三级结构七个球蛋白序列，分别为：已知三级结构七个球蛋白序列，分别为：Hbb_Human:人人-球蛋白球蛋白Hbb_Horse :马马-球蛋白球蛋白 Hba_Human:人人-球蛋白球蛋白Hba_Horse :马马-球蛋白球蛋白 Myg_phyca :抹香鲸血红蛋白抹香鲸血红蛋白 Glb5_petma:七鳃鳗蓝血红蛋白七鳃鳗蓝血红蛋白Lgb2_Luplu :羽扇豆豆血红蛋白羽扇豆豆血红蛋白第49页第一阶段：两两比对产生距离矩阵第一阶段：两两比对产生距离矩阵Biocomputing technology Multiple sequence alignment 用完全动态规划法计算用完全动态规划法计算7个球蛋白序列之间个球蛋白序列之间77距离矩阵距离矩阵 第50页第二阶段：产生指导树第二阶段：产生指导树Biocomputing technology Multiple sequence alignment 依据第一阶段结果中距离矩阵，用邻近归并法来依据第一阶段结果中距离矩阵，用邻近归并法来计算产生一棵有分枝长度和序列计算产生一棵有分枝长度和序列权重权重有根树。有根树。第51页第三阶段：渐进比对第三阶段：渐进比对Biocomputing technology Multiple sequence alignment 这一阶段基本步骤是经过一系列两两比对来构建更这一阶段基本步骤是经过一系列两两比对来构建更大比对序列组。按照指导树中分支次序，从有根树大比对序列组。按照指导树中分支次序，从有根树末梢到树根逐步进行。依据图末梢到树根逐步进行。依据图4.22有根树，经过下面有根树，经过下面次序对序列进行比对：次序对序列进行比对：(1)对对(2)(3)对对(4)(8)对对(9)(5)对对(10)(6)对对(11)(7)对对(12)。*每一阶段使用了有残基权重矩阵