生物信息学概论第二章数据库搜索与两两比对.ppt
《生物信息学概论第二章数据库搜索与两两比对.ppt》由会员分享,可在线阅读,更多相关《生物信息学概论第二章数据库搜索与两两比对.ppt(46页珍藏版)》请在三一文库上搜索。
1、第二章 数据搜索与两两比对,本章描述了 如何比对两条或多条相关核苷酸或多肽序列, 如何搜索存储序列信息的数据库。 通过比对得到预测蛋白质、新基因结构和功能以及基因间、蛋白质间乃至物种之间进化关系的重要信息。,2.1 点阵图,评估两条序列相似度最简单的方法之一是利用点阵图。 第一条被比较的序列排列在点阵图空间的横轴,第二条序列则排列在纵轴。点阵空间中两条序列中的残基相同时,在对应的位点上画上圆点,两条序列间连续相同的区域在图中会形成由圆点组成的上斜线。,具有连续相似区域的两条DNA序列的简单点阵图,滑动窗口技术 使用滑动窗口代替一次一个位点的比较是解决这 个问题的有效方法。 假设窗口大小为10,
2、相似度阈值为8,则每次比较取10个连续的字符,如相同的字符超过8个,则标记 基于滑动窗口的点矩阵方法可以明显地降低点阵图的噪声,并且明确无误的指示出了两条序列间具有显著相似性的区域。,(a)对人类(Homo sapiens)与黑猩猩(Pongo pygmaeus)的球蛋白基因序列进行比较的完整点阵图。(b)利用滑动窗口对以上的两种球蛋白基因序列进行比较的点阵图,其中窗口大小为10个核苷酸,相似度阈值为8。,(a) (b),2.2 简单比对,比对就是两条序列字符间简单的两两匹配。比对可以反映出两条或多条同源序列间的进化关系. 最简单的情况下即不考虑空位,当两条序列对比时,要做的仅是为较短的序列选
3、择比对的起始点。,考虑这样的两条核苷酸序列: AATCTATA和AAGATA 仅有三种比对方式,不考虑空位的简单比对,它的打分函数是有对比奖励和罚分的和来决定,上例中三个比对从左至右分别是 4、 1、 3,匹配得分:1 失配得分:0,2.3 空位,两条或多条序列比对时,如果考虑到插入与删除时间发生地可能性,那么候选的比对数量就会大大增加,也就导致了比对的复杂性。上节中两条核苷酸序列,在不考虑空位时仅有三种比对,而较短的那条加入了两个空位后,变产生了28种不同的比对,例如:,等等,2.3.1 简单空位罚分,对含有空位的比对打分时,空位罚分就必须包含到打分函数中,空位比对的简单打分公式如下:,例如
4、:假设匹配得分为1,失配得分为0,空位罚分为-1,三种空位比对的得分从左至右分别是1、3、3,2.3.2 起始罚分与长度罚分,使用简单空位罚分对两条序列进行比对时,经常能找到若干同格式最优的比对。进一步区分这些比对的方法是找出哪些比对包含较多的不连续空位,哪些包含较少长度较长的空位片段。,插入/删除事件,假设两条序列长度分别是12和9 假设这两条序列是真正的同源序列,那么它们之间长度的差异可以解释为 (1)较长的序列有核苷酸的插入,或者 (2) 较短的序列发生了核苷酸的删除,或者(3) 两者都发生了。 在不知道原始父辈序列的情况下,无法判断导致空位的原因是由于一条序列的插入事件还是另一条的删除
5、事件,通常把这类事件称为插入/删除事件。,多联核苷酸的插入删除事件相对于单个核苷酸来说会较经常发生。 统计结果表明,两条序列长度上的差异更可能是单个三联核苷酸的插入删除事件导致的,而多个不连续核苷酸插入删除事件的可能性比较小。 空位罚分 由序列中产生的新空位串引起的起始罚分和根据缺少的字符数而定的长度罚分。预设长度罚分小于起始罚分,以此建立的打分函数便能奖励空位连在一起的比对。,假设起始罚分为-2,长度罚分为-1,匹配得分为+1,失配得分为0,则对于,这三个比对,从左至右比对的得分分别是 -3,-1,+1,在后两种比对在使用简单空位罚分时,最后得分都是+3,现在却得到了不同的分数。,2.4打分
6、矩阵,正如空位罚分可以奖励与进化相关的的比对,失配罚分也可以用来进一步区分相似比对。 统计结果表明,两条同源的序列比对时,某些替换比其他替换常见的多。 例: 两条蛋白质序列,其中一条在某一个位置上是丙氨酸,如果该位点被替换成另一个较小的且疏水的氨基酸,比如缬氨酸对蛋白质的影响很小,如果被替换成较大且带电的残基,比如赖氨酸,那么对蛋白质的影响可能就会非常大。直观的讲,比较保守的替换比随机替换更可能维持蛋白质的功能,更不容易被淘汰,因此在打分上更倾向于丙氨酸而不是赖氨酸。,打分矩阵(Scoring Matrix),核酸打分矩阵设DNA序列所用的字母表为 = A,C,G,T a. 单位矩阵 b. B
7、LAST矩阵 c. 转换-颠换矩阵(transition,transversion) (嘌呤:腺嘌呤A,鸟嘌呤G;嘧啶:胞嘧啶C,胸腺嘧啶T),单位矩阵,转换-颠换矩阵,BLAST矩阵,PAM矩阵(Point Accepted Mutation) 基于进化的点突变模型 一个PAM就是一个进化的变异单位, 即1%的氨基酸改变,相对突变率仅仅是某种氨基酸 被其他任意氨基酸替换的次数 例如:ma是指丙氨酸与非丙氨酸残基比对的次数,Ma为概率 然而我们针对每个氨基酸对i 和j,计算氨基酸j 被氨基酸i 替换的次数 Aij 例如:Acm 是被比对序列中,甲硫氨酸被半胱氨酸替换的次数 以Aij除以ma 利
8、用每个氨基酸出现的频度对起进行标准化,得到PAM-1矩阵中的元素Rij,式中Mab为任意氨基酸b替代a的概率 式中pa为氨基酸a未被替换的概率,100个残基发生一次替换的PAM-1矩阵,针对不同的进化距离采用PAM 矩阵,序列相似度 = 40% 50% 60%,| | | 打分矩阵 = PAM120 PAM80 PAM 60,PAM250 14% - 27%,2.5 动态规划: Needleman 和 Wunsch 算法,一旦选定了序列比对打分的方法,就可以为寻找最佳比对设计算法了。 最显而易见的方法就是对每个可能的比对进行穷举搜索,但这一般是不可行的。 我们可以用动态规划解决这个问题,即把一
9、个问题分解成计算量合理的子问题,并使用这些子问题的结果来计算最终答案。 S. Needleman与C. Wunsch首次运用动态规划方法来进行序列分析。,假设两条序列:CACGA和CGA,使用统一的空位和失配罚分 则:1、给第一条序列加一个空位 2、给第二条序列加一个空位 3、两条序列都不加空位,如果知道了ACGA与GA最佳比对的得分,就可以立即计算出表中第一行的得分。同样地,如果知道了表中第二、第三行剩余序列的最佳比对的得分,就可以计算出起始位点的不同的三种比对得分。 动态规划算法通过计算部分序列比对得分并填入一个表格,直到整个序列比对被计算出来, 由此得到最优比对。,(匹配得分为1,失配得
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 生物 信息学 概论 第二 数据库 搜索
链接地址:https://www.31doc.com/p-3486610.html