全局序列比对
动态规划算法
Algorithm) Methods)
(Dynamic Programming
(Divide and Conquer
分而治之方法
SP方法 (Sum of Pairs Methods) 累进方法 (Progressive Methods) 迭代方法 (Iterative Methods) 遗传算法 (Genetic Algorithms)
SP方法通过对一个随机数据矩阵 中氨基酸对的所有可能组合的记 分求和来获得矩阵记分
SP 方法例子
S S I I S K K E
-8 - 8 + 4 = -12
使用 BLOSUM62 矩阵, 空位罚分为 -8 在第一列, 有三种两两 比对组合方式： -, S -, S S,S 每一列有k(k-1)/2 个双 序列比对
d
1 3
1 3 2
1 3 2 5 4 1 3 2 5 4
累进算法的一些问题
比对的准确性高度依赖于开始选择的 双序列比对 序列关系越远发生的错误可能越高 选择合适的打分矩阵和罚分准则较困 难
Clபைடு நூலகம்USTALW/X简介
ClLUSTAL最初初由Higgins等于1988年创 立并不断完善
用来多序列比对、概形(Profile)分析和创 建进化树 ClLUSTAL分为ClLUSTALW和 CLUSTALX两种类型 ClLUSTAL有用于WINDOWS和 UNIX/LINUX的各种版本
一个多序列比对例子
VTISCTGSSSNIGAG-NHVKWYQQLPG VTISCTGTSSNIGS--ITVNWYQQLPG LRLSCSSSGFIFSS--YAMYWVRQAPG LSLTCTVSGTSFDD--YYSTWVRQPPG PEVTCVVVDVSHEDPQVKFNWYVDG-ATLVCLISDFYPGA--VTVAWKADS-AALGCLVKDYFPEP--VTVSWNSG--VSLTCLVKGFYPSD--IAVEWWSNG--
多序列比对方法
全局序列比对
动态规划算法 (Dynamic Programming Algorithm) 分而治之方法 (Divide and Conquer Methods) SP方法 (Sum of Pairs Methods) 累进方法 (Progressive Methods) 迭代方法 (Iterative Methods)
动态规划算法(Dynamic Programming)
序列长度为 n 的双序列比对 n2 比对 比对数目成指数增长 例如：序列长度为n，序列数为N 的 多序列比对数目是nN
对于数目较少且较短的序列来说都不 切实际
多维的动态规划算法
Sequence 1
Sequence 2
分而治之方法
分而治之 (Divide and Conquer, DCA)方法 将MSA的空间复 杂度减小 DCA在线MSA
局部序列比对
概形分析 (Profile Analysis) 区块分析 (Block Analysis) 统计学方法 (Statistical Methods）
多序列比对总体思路
在多序列比对前要考虑的问题
比对的优劣与序列条数正相关 避免在比对中包括相似度 >80%的序 列 每个亚群应分别先比对，然后再整体 比对
累进算法原理
Scerevisiae Celegans Drosophia Human Mouse [1] [2] [3] [4] [5] 0.640 0.634 0.327 0.630 0.408 0.420 0.619 0.405 0.469 0.289
1 对所有序列做双序列比 对，构建距离矩阵计算相 似性分数值 2 基于双序列距离矩阵， 构建一个进化树 3 依据进化树进行渐进比对
CLUSTAL方法
进行所有序列间的双序列比对
基于双序列比对分数产生一个相邻连 接进化树(neighbor-join tree) 根据进化树提供的序列间关系按顺序 对序列进行比对 比对可以用以下两种方法： - slow/accurate - fast/approximate
我们为什么做多序列比对?
分析多个序列的一致序列
用于进化分析，是用系统发育方法构建进 化树的初使步骤 寻找个体之间单核苷酸多态性(SNPs)
通过序列比对发现直系同源(Orthologs)与 旁系同源(Paralogs)基因 寻找同源基因(相似的序列往往具有同源 性)
多序列比对与进化研究例子
图中NYLS为树根
累进算法(Progressive Methods)
针对基于动态规划算法的MSA程序比对序 列数目有限， Feng & Doolittle(1987)发明 了累进算法
CLUSTAL 和 PILEUP 是目前常用的基于 累进算法的比对软件 CLUSTAL 是免费软件,目前应用非常广泛
trasbg.fr/BioInfo/ClustalX/Top.html
多序列比对
(Multiple Alignments)
郭志云
Email:bioinf@
我们为什么做多序列比对?
寻找蛋白质家族，识别多个序列的保守区 域
相似的蛋白质序列往往具有相似的结构与 功能 辅助预测新序列的二级或三级结构
可以直观地看到基因的哪些区域对突变敏 感 PCR引物设计
http://bioweb.pasteur.fr/seqana l/interfaces/dca-simple.html
So in effect …
Sequence 1
Sequence 2
SP(Sum of Pairs)方法
为了找到最佳比对，并解决动态 规则算法的计算复杂问题， Carrillo & Lipman (1988)发明了 SP(Sum of Pairs)方法
• 依据进化树，开始对关系较 近的序列进行两两比对 • 逐渐加入关系较远的序列进 行比对 • 构建多序列比对
Human Mouse Dmel Cele Scer
Multiple alignment
一般累进比对方法
d
1 3
1 3 2 5
1 3 2 5
root
1 3 2 5 4
果仁糖累进方法
(Praline progressive strategy)