前趋节点的个数等于2k - 1
假设以k维数组A存放超晶格，则计算过程如下： a[ 0, 0, … ,0 ] = 0
a[ i ] = max {a[ i - b ] + SP-score(Column(s, i, b))}
Colum n ( s , i , b ) (c j ) j k s j [i j ] cj
（2）特征统计图（Profile） 令P=(P1,P2,…,PL)，P表示在的每一列上 各种字符出现的概率分布
Pj=(pj0,pj1,…,pj|A|)
A代表字母表，Pjk代表字母表A中第k个字符在第 j 列出现的概率。 第0个字符是特殊的空位符号“-”。
ATTAT AACTT CTTAT ACTTT AGAAT
if bj = 1 if bj = 0
(3-37) (3-38)
问题：
计算量巨大
时间复杂度为O(2ki=1,...,k si) ↓ O(2kNk)
图3.17 三维晶格节点计算依赖关系
2、 优化计算方法
标准动态规划算法存在的问题： 搜索空间大 剪枝技术：将搜索空间限定在一个较小的区域 范围内。 若问题是搜索一条得分最高（或代价最小）的 路径，则在搜索时如果当前路径的得分低于某 个下限（或累积代价已经超过某个上限），则 对当前路径进行剪枝，即不再搜索当前路径的 后续空间。
六、统计特征分析
• 对于所得到的多重序列比对，我们往往需要进行归纳分析， 总结这些序列的特征，或者给出这些序列共性的表示
—H—LVV G—VLVG GN—LVV LHCLVVHCL--
（1）保守序列 表示序列每个位置上最可能出现的字符（或者所有可能出 现的字符） ATNTSC (N - A,T,C,G ; S - G,C)
两两比对 多重比对
(sc, s1) (sc, s2) … (sc, sk)
sc
s1 s2 … sk
如何选择核心序列？
– 尝试将每一个序列分别作为核心序列，进行星形 多重序列比对，取比对结果最好的一个。 – 另一种方法是计算所有的两两比对，取下式值最 大的一个：
sim( si, sc )
例如，有5个序列： s1 = ATTGCCATT s2 = ATGGCCATT s3 = ATCCAATTTT s4 = ATCTTCTT
A T C G （碱基）
1 0.8 0.0 0.2 0.0
2 0.2 0.4 0.2 0.2
3 0.2 0.6 0.2 0.0
4 0.6 0.4 0.0 0.0
5 (位置) 0.0 1.0 0.0 0.0
• 利用保守序列或者特征统计图可以判断一个序列 是否满足一定的特征 一条序列与特征统计图相对照，如果代价值小， 说明该序列具有相应的特征，否则该序列不具备 相应的特征。 • 利用特征统计矩阵搜索数据库时，可以考察家族 的成员关系。
— 用一个k维数组来表示该显式函数（类似于打分矩阵）
期望： 函数在形式上应该简单 具有统一的形式 不随序列的个数而发生形式变化
逐对加和SP（sum-of-pairs）函数
SP score(c1 , c2 ,...,ck ) p(ci , c j )
i 1 j i 1
k 1
k
第四章 多序列比对
多序列比对
Made by GENEDOC
一、多序列比对：简介
• 1. 不同物种中，许多基因的功能保守，序列 相似性较高，通过多条序列的比较，发现保守 与变异的部分； • 2. 可构建统计学模型（如HMM） ，搜索更多 的同源序列； • 3. 构建进化树的必须步骤； • 4. 比较基因组学研究；
l: 双序列比对
Gap Gap V 0 -11
4
V -11 4
2
D -22 -7
S -33 -18
C -44 -29 -1 9 8 -3
Y -55 -40 -12 -3 7 15
时间复杂度：O(n2)
-5
10 -1 -12 -23
E
S L C Y
-22
-33 -44 -55 -66
-7
-18 -29 -40 -51
二、多序列比对的方法
• 手工比对方法（包括对结果进行修饰） • 同步法 • 步进法 动态规划算法 优化计算方法 • 星形比对 • 其它多序列比对算法
二、步进法
• 动态规划算法 • 优化计算方法
1、多重比对的动态规划算法
多重序列比对的最终目标是通过处理得 到一个得分最高（或代价最小）的序列 对比排列，从而分析各序列之间的相似 性和差异。
6
-5 -16 -27 -38
-16
-27
多序列比对：最优算法
多项式时间复杂度：≤O(n3) 三条序列：时间复杂度：O(lmn) = O(n3)
四条序列：时间复杂度：O(n4)，非多项式时间！ … m条序列：时间复杂度：O(nm)，指数时间！
动态规划算法：全空间
/CBBresearch/Schaffer/msa.html
其中，c1,c2,…,ck是一列中的k个字符，p是关于一对字符相似性的打分函数。
L L A P SP score 26 G S G
逐对计算p(1,2)，p (1,3)，...， p(1,8)，p (2,3)，p(2,4)，...， p (2,8)，...，p (7,8) 的所有得 分 -6-6-5-4-2-2-1 = -26
（3-44）
多序列比对的方法
• 手工比对方法（包括对结果进行修饰） • 同步法 • 步进法 动态规划算法 优化计算方法 • 星形比对 • 其它多序列比对算法
五、MSA: 多序列比对的打分和评价
1、SP（Sum-of-Pairs）模型
评价多重序列比对的结果
按照每个对比的列进行打分，然后加和 处理每一列： — k个变量的打分函数
动态规划算法：优化算法
Sequence B
搜索有限空 间，类似于 BLAST算法
/CBBresearch/Schaffer/msa.html
多序列比对的方法
• 手工比对方法（包括对结果进行修饰） • 同步法 • 步进法 动态规划算法 优化计算方法 • 星形比对 • 其它多序列比对算法
• 星形比对是一种近似的方法，可以证明，用该方法 所得到多重序列比对的代价不会大于最优多重序列 比对代价的两倍
引理3.1： 对于所有的1≤i，j≤k，,ij, 有 dc(si, sj) ≤ D(si, sc) + D(sc, sj) （3-43）
定理3.2
V ( c ) 2(k 1) 2 V ( ) k
星形比对
• 星形比对的基本思想是：在给定的若干序列中， 选择一个核心序列，通过该序列与其它序列的 两两比对形成所有序列的多重比对，从而使 得在核心序列和任何一个其它序列方向的投 影是最优的两两比对。 • 利用标准的动态规划方法求出所有si和sc的最 优两两比对 –时间为O（kn2） –将这些两两比对聚集起来 –并采用“只要是空白， 则永远是空白”的原则。
s5 = ACTGACC
sc=s1
ATTGCCATT ATGGCCATT ATTGCCATT-ATC-CAATTTT ATTGCCATT ATCTTC-TT ATTGCCATT ACTGACC--
ATTGCCATT-ATGGCCATT-ATC-CAATTTT ATCTTC-TT-ACTGACC----