生物分子序列比较（二）生物分子序列比较（孙啸生物电子学国家重点实验室东南大学序列多重比对目的：目的：?发现多个序列的共性?发现与结构和功能相关的保守序列片段个序列s设：有k个序列1,s2,...,sk，每个序列由同一个个序列字母表中的字符组成，大于大于2。字母表中的字符组成，k大于。通过插入操作，使得各序列达到一样的长度。通过插入操作，使得各序列达到一样的长度。1、SP（Sum-of-Pairs）模型SP（Sum-of-Pairs）评价多重序列比对的结果按照每个对比的列进行打分，按照每个对比的列进行打分，然后加和处理每一列：处理每一列：—k个变量的打分函数个变量的打分函数—用一个维数组来表示该显式函数（类似于打分矩阵）用一个k维数组来表示该显式函数类似于打分矩阵）维数组来表示该显式函数（期望：期望：函数在形式上应该简单具有统一的形式不随序列的个数而发生形式变化逐对加和SP（逐对加和（sum-of-pairs）函数）SP?score(c1,c2,...,ck)=∑k?1i=1j=i+1∑p(c,c)ijk其中，c1,c2,…,ck是一列中的k个字符，p是关于一对字符相似性的打分函数。?L??L????A????P?=26SP?score?G????S???????G???逐对计算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）另一种计算方式：另一种计算方式：先处理每一个序列对在处理序列对时，逐个计算字符对，在处理序列对时，逐个计算字符对，最后加和得分模型的计算公式如下：则SP得分模型的计算公式如下：得分模型的计算公式如下SP?score(α)=∑αiji<jα是一个多重比对αij是由α推演出来的序列i和sj的两两比对是由α推演出来的序列s多重序列比对投影2、多重比对的动态规划算法?多重序列比对的最终目标是通过处理得到一个得分最高（或代价最小）的序列对比排列，从而分析各序列或代价最小）的序列对比排列，之间的相似性和差异。之间的相似性和差异前趋节点的个数等于2前趋节点的个数等于k-1假设以k维数组存放超晶格则计算过程如下：假设以维数组A存放超晶格，则计算过程如下：维数组存放超晶格，a[0,0,…,0]=0a[i]=max{a[i-b]+SP-score(Column(s,i,b))}Column(s,i,b)=(cj)j≤k?sj[ij]cj=???ifbj=1ifbj=0问题：问题：计算量巨大时间复杂度为O(2kΠi=1,...,k?si?)时间复杂度为↓O(2kNk)3、优化计算方法标准动态规划算法存在的问题：标准动态规划算法存在的问题：搜索空间大剪枝技术：剪枝技术：将搜索空间限定在一个较小的区域范围内。围内。若问题是搜索一条得分最高（或代价最小）若问题是搜索一条得分最高（或代价最小）的路径，则在搜索时如果当前路径的得分低于某个下或累积代价已经超过某个上限），），则对当前限（或累积代价已经超过某个上限），则对当前路径进行剪枝，即不再搜索当前路径的后续空间。路径进行剪枝，即不再搜索当前路径的后续空间。经过特定断点的最优比对算法：经过特定断点的最优比对算法：设有两条序列s、，已知它们的两个断点分别是i、设有两条序列、t，已知它们的两个断点分别是、j经过特定断点（、）的最优比对可分为两个部分：经过特定断点（i、j）的最优比对可分为两个部分：——0:s:i与0:t:j的最优比对——i:s:m与j:t:n的最优比对i序列S:序列t:j为了得到特定断点的最优比对，用两个矩阵和为了得到特定断点的最优比对，用两个矩阵A和Ba[i,j]=sim(0:s:i,0:t:j)b[i,j]=sim(i:s:m,j:t:n)?矩阵的计算和标准算法一样矩阵A的计算和标准算法一样?矩阵的计算则是反方向的，即先对的最后一行和最后一列矩阵B的计算则是反方向的即先对B的最后一行和最后一列的计算则是反方向的，进行初始化，然后反向推进到（，）。进行初始化，然后反向推进到（0，0）。?矩阵与B的和矩阵A与的和的和C=A+B包含了在特定断点（i、j）的最优比对包含了在特定断点（包含了在特定断点、）得分。矩阵为总得分矩阵，得分。称C矩阵为总得分矩阵，而A、B分别是前缀和后缀的得矩阵为总得分矩阵、分别是前缀和后缀的得分矩阵。分矩阵。?根据的最大值，可非常容易地找出最优比对所对应的路径。根据C的最大值可非常容易地找出最优比对所对应的路径。的最大值，（a）-ATTCGGGATTC-（c