《生物计算技术》第4篇 多重序列比对分析-2006.ppt

sc s1 s2 … sk HMM的三个经典问题: Biocomputing technology— Multiple sequence alignment 问题1（评测问题，evaluation）： 已知模型 和输出序列O，求由 生成O的概率。 问题2（译解问题，decoding）： 已知模型 和输出序列O，求最有可能生成O的状态 转移序列。 问题3（学习问题，learning）： 已知模型 和输出序列O，求最有可能生成O时模型 的参数。 Profile——概形、谱 Biocomputing technology— Multiple sequence alignment * 概形是对一组序列进行全局多重比对时被发现的,是将比对 中具有较高保守区域变成小的多重比对,然后得到多重比对 记分矩阵. * 概形由更像小的多重排列的列构成,可以包括: 匹配、失配、 插入、缺失. * 概形一旦生成,就可用于寻找一个可能与之匹配的目标序列, 它利用表中记分来评价每个位置的可能性. 例: 25个氨基酸长的概形表格,有25列,每列将有20个记分值. 一列中每个匹配氨基酸的记分都在概形中对应的位置上. 缺点：偏向性 Profile HMM (1) 模型结构 Biocomputing technology— Multiple sequence alignment * 对于生物序列而言,HMM的字符当然是20个字母的氨基酸 或4个字母的核苷酸。但依据不同的问题,其它的一些字符 也可以使用,如64个密码子的三联体字母,3个字母(α,β, coil )的二级结构等. * 编码蛋白质的原始DNA序列,在生物的进化过程中会受到 自然环境和各种因素的影响,使翻译出的蛋白质序列经历 突变、遗失或引入外源序列等变化,最后按不同的进化路 径分化,形成多种功能相近的蛋白质。 所以,可以把这些蛋白质看作由一个基本蛋白质序列经过插 入、删除或替换了某些氨基酸残基而形成的。这个过程可以 用HMM来表示。 图4.9 Biocomputing technology— Multiple sequence alignment 图中: 方形代表匹配状态(主状态)，即输出的氨基酸和基本序列中对应 的氨基酸匹配; 圆形表示删除或缺失状态，即从原始蛋白质序列中去掉一个特定 的氨基酸。 菱形表示氨基酸的插入，即在原始蛋白质序列插入一个氨基酸。 各状态间的箭头表示状态间的转换途径。 注意: ① 不同的参数会使模型以不同的概率产生新的氨基酸。 ② 一个训练好的模型可以代表有共同特征的蛋白质序列。 图4.10 Biocomputing technology— Multiple sequence alignment Profile HMM 与标准的Profile的比较 Biocomputing technology— Multiple sequence alignment ① Profile HMM有正规的概率作基础，对于序列的删除和 插入状态的记分也有较为可靠的理论依据。而标准的 Profile纯粹是一种启发式的方法。 ② HMM用统计方法估计序列某一位点核苷酸或氨基酸残基 出现的真正概率，而标准的Profile却是用自身的观察频率 给核苷酸或氨基酸残基指派分数。 ③ 由于②,Profile HMM方法从10至20个核苷酸序列构成的 比对中提取的信息，相当于用标准的Profile从40至50个 核苷酸序列构成的比对中提取的信息。 具体实现过程: Biocomputing technology— Multiple sequence alignment 设节点j 是一个依赖于节点i 的相关节点， 如果j 不在缓冲区内，则将其放入缓冲区，并计算 a[ j ] a[ i ]+SP_Score( Colum(s, i, b) ) (3) 如果j 早已在缓冲区中，则按下式更新 a[ j ] max( a[ j ], a[ i ]+SP_Score( Colum(s,i, b) ) ) 注意: Carrilo-Lipman 算法要求待比较的多个序列具有较大 的相似性，并且序列数不能太多。 4.2.4 星形比对 Biocomputing technology— Multiple sequence alignment * 启发式方法作为首选。 * 启发式方法不一定保证最终能得到最优解，但在大多