东南大学吴健雄实验室

《东南大学吴健雄实验室》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第三章（2）序列多重比对主讲人：孙啸制作人：刘志华东南大学吴健雄实验室第三节序列多重比对目的：发现多个序列的共性发现与结构和功能相关的保守序列片段设：有k个序列s1,s2,...,sk，每个序列由同一个字母表中的字符组成，k大于2。通过插入操作，使得各序列达到一样的长度。1、SP（Sum-of-Pairs）模型评价多重序列比对的结果按照每个对比的列进行打分，然后加和处理每一列：—k个变量的打分函数—用一个k维数组来表示该显式函数（类似于打分矩阵）期望：函数在形式上应该简单具有统一的形式不随序列的个数而

2、发生形式变化其中，c1,c2,…,ck是一列中的k个字符，p是关于一对字符相似性的打分函数。逐对加和SP（sum-of-pairs）函数逐对计算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得分模型的计算公式如下：是一个多重比对ij是由推演出来的序列si和sj的两两比对2、多重比对的动态规划

3、算法多重序列比对的最终目标是通过处理得到一个得分最高（或代价最小）的序列对比排列，从而分析各序列之间的相似性和差异。前趋节点的个数等于2k-1假设以k维数组A存放超晶格，则计算过程如下：a[0,0,…,0]=0a[i]=max{a[i-b]+SP-score(Column(s,i,b))}(3-37)(3-38)ifbj=1ifbj=0图3.17三维晶格节点计算依赖关系问题：计算量巨大时间复杂度为O(2ki=1,...,ksi)↓O(2kNk)3、优化计算方法标准动态规划算法存在的问题：搜索空间

4、大剪枝技术：将搜索空间限定在一个较小的区域范围内。若问题是搜索一条得分最高（或代价最小）的路径，则在搜索时如果当前路径的得分低于某个下限（或累积代价已经超过某个上限），则对当前路径进行剪枝，即不再搜索当前路径的后续空间。经过特定断点的最优比对算法：设有两条序列s、t，已知它们的两个断点分别是i、j经过特定断点（i、j）的最优比对可分为两个部分：——0:s:i与0:t:j的最优比对——i:s:m与j:t:n的最优比对序列S:序列t:ji为了得到特定断点的最优比对，用两个矩阵A和Ba[i,j]=sim(0

5、:s:i,0:t:j)b[i,j]=sim(i:s:m,j:t:n)矩阵A的计算和标准算法一样矩阵B的计算则是反方向的，即先对B的最后一行和最后一列进行初始化，然后反向推进到（0，0）。矩阵A与B的和C=A+B包含了在特定断点（i、j）的最优比对得分。称C矩阵为总得分矩阵，而A、B分别是前缀和后缀的得分矩阵。根据C的最大值，可非常容易地找出最优比对所对应的路径。-ATTCGGGATTC--（c）图（a）前缀矩阵；（b）总得分矩阵；（c）最优比对（a）（b）定理3-1：设是关于s1,s2,...,sk

6、的最优比对，如果SP-score()L，则score(ij)Lij其中Lij=L-(sim(sx,sy))x

7、任何一个其它序列方向的投影是最优的两两比对。利用标准的动态规划方法求出所有si和sc的最优两两比对时间为O（kn2）将这些两两比对聚集起来并采用“只要是空白，则永远是空白”的原则。scs1s2…sk(sc,s1)(sc,s2)…(sc,sk)两两比对多重比对如何选择核心序列？尝试将每一个序列分别作为核心序列，进行星形多重序列比对，取比对结果最好的一个。另一种方法是计算所有的两两比对，取下式值最大的一个：sim(si,sc)例如，有5个序列：s1=ATTGCCATTs2=ATGGCCATTs3=AT

8、CCAATTTTs4=ATCTTCTTs5=ACTGACCsc=s1ATTGCCATTATTGCCATT--ATTGCCATTATTGCCATTATGGCCATTATC-CAATTTTATCTTC-TTACTGACC--ATTGCCATT--ATGGCCATT--ATC-CAATTTTATCTTC-TT--ACTGACC----引理3.1：对于所有的1≤i，j≤k，,ij,有dc(si,sj)≤D(si,sc)+D(sc,sj)（3-43）定理3.2（