第四章 双序列比对的动态规划算法.ppt

第四章双序列比对 2 概念 同源 homology 具有共同的祖先直向同源 Orthologous 共生同源 paralogous 相似 similarity 同源序列一般是相似的 相似序列不一定是同源的 3 4 通过点矩阵进行序列比较 5 编辑距离 EditDistance 6 相似性得分 7 第二节打分矩阵 1 核酸打分矩阵设DNA序列所用的字母表为 A C G T a 等价矩阵 unitarymatrix b BLAST矩阵c 转移矩阵 transition transversion 嘌呤 腺嘌呤A 鸟嘌呤G 嘧啶 胞嘧啶C 胸腺嘧啶T 表3 1等价矩阵表 表3 3转移矩阵 表3 2BLAST矩阵 8 2 蛋白质打分矩阵 i 等价矩阵 ii 氨基酸突变代价矩阵GCM iii 疏水矩阵 iv PAM矩阵 PointAcceptedMutation Dayhoff模型 可接受点突变 v BLOSUM矩阵 BlocksAminoAcidSubstitutionMatrices 其中Rij代表打分矩阵元素i j分别代表字母表第i和第j个字符 9 氨基酸突变代价矩阵GCM一个氨基酸残基转变到另一个氨基酸残基所需的密码子碱基变化数目1或2只有Met到Tyr为3 10 11 GCM矩阵 12 疏水矩阵 动态规划算法 动态规划算法整体比对算法Needleman Wunsch算法间隔罚分局部比对算法Simth Waterman算法 矩阵的基本形式是将两序列中匹配的残基所对应的单元设为1 不匹配的为0对矩阵中的每个单元进行连需求和 即把能够到达该位置的所有单元中的最大值与该位置的值相加 第I行第j列单元的值为Ij本身的值 i 1行第j个单元之后所有单元的最大值或j 1列第i个单元之后所有单元的最大值 举例说明 让我们用一个例子来解释上述过程 CKHVFCRVCICKKCFCKCV若在匹配位置用1标出 而不匹配则留空 可得以下矩阵 连续求和 从最后的单元开始 从最高分值单元开始找出最大分值路径 也就是最佳匹配 序列比对结果 间隔罚分 空位的缺失和插入 有助于获得最佳匹配但是不加限制的间隔 缺乏必要的生物学意义 局部比对算法 Simth Waterman算法序列局部比对的标准算法在识别局部相似性时 有很高的灵敏性 在矩阵最上面一行和最左边一列前分别添加一个边界行和边界列从左往右 从上往下 并沿对角线从左上角到右下角用三个函数分别计算由三条路径到达该单元的分值并找出其中的最大值 如此分值小于0 则用0代替 函数1 当前单元对角线方向的前一格的分值与当前单元相似性之和 相似性数值匹配时为1 0 不匹配是为 0 333函数2 当前行前面各分值与相应空位罚分值之差 并取最大值 所求空位罚分值的函数为Wk 1 0 0 333k k表示连续第k个空位函数3 当前列前面各分值与相应空位罚分值之差 并取最大值 如果出现负值就用0代替 表示没有相似性研究到当前位置 两种算法的比较 起始部位不同最高分值所在部位不同 53 BLAST简介 54 BLAST程序是目前最常用的基于局部相似性的数据库搜索程序 它们都基于查找完全匹配的短小序列片段 并将它们延伸得到较长的相似性匹配 它们的优势在于可以在普通的计算机系统上运行 而不必依赖计算机硬件系统而解决运行速度问题 55 BLAST数据库搜索策略 BLAST仅通过部分而不是全部序列计算最适联配值 赢得搜索速度 56 57 比对统计学意义的评价 E值 E Value P值 P Value 概率值 BLAST程序中使用了E值而非P值 这主要是从直观和便于理解的角度考虑 比如E值等于5和10 总比P值等于0 993和0 99995更直观 但是当E 0 01时 P值与E值接近相同 参数K和 可分别被简单地视为搜索步长 searchspacesize 和计分系统 scoringsystem 的特征数 58 BLAST软件包实际上是综合在一起的一组程序 不仅可用于直接对蛋白质序列数据库和核酸序列数据库进行搜索 而且可以将检测序列翻译成蛋白质或将数据库翻译成蛋白质后再进行搜索 以提高搜索结果的灵敏度 表7 59 BLAST程序检测序列和数据库类型 60 对一般用户来说 目前常用的办法是通过NCBI EBI等国际著名生物信息中心的BLAST服务器进行搜索 北京大学生物信息中心也提供了BLAST数据库搜索服务 需要说明的是 各生物信息中心BLAST用户界面有所不同 所提供的数据库也可能不完全相同 使用前最好先进行适当的选择 61 BLAST应用实例 多结构域蛋白 H1N1 脂质运载蛋白 62 多结构域蛋白 H1N1 的BLAST检索 63 gi 224983683 pdb 3GBN BChainB CrystalStructureOfFabCr6261InComplexWithThe1918H1n1InfluenzaVirusHemagglutininGLFGAIAGFIEGGWTGMIDGWYGYHHQNEQGSGYAADQKSTQNAIDGITNKVNSVIEKMNTQFTAVGKEFNNLERRIENLNKKVDDGFLDIWTYNAELLVLLENERTLDFHDSNVRNLYEKVKSQLKNNAKEIGNGCFEFYHKCDDACMESVRNGTYDYPKYSEESKLNREEIDGVSGR 多结构域蛋白 H1N1 的BLAST检索 H1N1聚合酶序列 64 65 BLAST结果综述 66 BLAST结果表述 67 BLAST结果逐条显示 68 BLAST结果逐条显示 69 BLAST 改变打分矩阵的作用 脂质运载蛋白 序列 sp P31025 LCN1 HUMANLipocalin 1OS HomosapiensGN LCN1PE 1SV 1MKPLLLAVSLGLIAALQAHHLLASDEEIQDVSGTWYLKAMTVDREFPEMNLESVTPMTLTTLEGGNLEAKVTMLISGR