搜索
查看: 1871|回复: 3

Blast 相关原理算法小节

[复制链接]

1

主题

2

帖子

60

积分

注册会员

Rank: 2

积分
60
发表于 2018-3-25 00:04:40 | 显示全部楼层 |阅读模式
几个需要理解的关键词
用手打提高自己的记忆性,不要用鼠标粘贴复制,用脑子粘贴复制。
sequence alignment Why do we need alignment?
scoring mstrix
    PAM(Point Accrpted Mutation)evolution
    BLOUSUM(BLOCKS Amino Acid Substitution Matrix)experience
gap penalty
    gap openingVSgap extension How does the penalty come?
Dot-matrixVSDynamic programming matrixVSBLAST
identityVSsimilarityDNA&Protein
Global alignmentVSLocal alignment How does the 0 come?
Alignment scoreVSE-value
LCRs(Low-complexity regions)  RLRLRLRLRLRLRLRLRLRLRLRL&xxxxxxnnnnnnn
nr(non-redundant protien sequences)
序列比对的原理
  • 记分矩阵 scoring matrix
    • 核酸:核酸的记分比较简单,一般采用最简单的比对方法。
    • 蛋白质:蛋白质应为分为不同种类,相同种类的错配罚分相对较低,正确配对的罚分也不同。
      • PAM矩阵:PAM矩阵(Point Accepted Mutation)基于进化的点突变模型,如果两种氨基酸替换频繁,说明自然界接受这种替换,那么这对氨基酸替换得分就高。一个PAM就是一个进化的变异单位, 即1%的氨基酸改变,但这并不意味100次PAM后,每个氨基酸都发生变化,因为其中一些位置可能会经过多次突变,甚至可能会变回到原来的氨基酸。
      • BLOSUM矩阵:模块替换矩阵BLOSUM(BLOcks Substitution Matrix)首先寻找氨基酸模式,即有意义的一段氨基酸片断(如一个结构域及其相邻的两小段氨基酸序列),分别比较相同的氨基酸模式之间氨基酸的保守性(某种氨基酸对另一种氨基酸的取代数据),然后,以所有 60%保守性的氨基酸模式之间的比较数据为根据,产生BLOSUM60;以所有80%保守性的氨基酸模式之间的比较数据为根据,产生BLOSUM80。
    • 两种比对概念略有不同。
  • 空位(间隔)罚分
    • 空位一般对应插入或者缺失,但是罚分一本分为两个概念,可以看得出来,两者产生肯定是前者罚分更高,对于已有的gap上,增加gap的长度罚分应该要少一些。
    • 空位开放(gap opening):cost to create a gap.
    • 空位开放(gap opening):cost to make a gap bigger (must already have created a gap).
    • high gap opening penalty: point insertions/deletions would ruin your alignment.
    • high gap extension penalty: this will affect the size of indels in your alignment.
  • 对矩阵的分析方法
    • 点阵分析(Dot-matrix) 如果出现相反序列的情况
      • 如果对角线出现完全相同或者其他位置出现完全相同的序列,会在图形上显示出斜率为-1的线,如果序列相反,相当于把上面一条序列反过来,斜率自然就变成了1.
      • 对于反向重复序列"GGGATCACGTATGCATTAGCATACATCACGCGG"与"GGGATCACGTATGCATTAGCATACATCACGCGG",在NCBI上的Blast上面得到的点阵图也是一个斜率为-1的图片。推测Blast算法也会把序列互补一遍比对一下,看能不能有比较好的结果。
    • 动态规划(Dynamic programming) dynamic programming matrix
      • 用来研究两序列比对的最佳算法,简单来说就是把一个大问题分解成很多“重叠子问题”,在这些重叠的子问题里面寻找所有子问题的最优解,把最优解合在一起就是大问题的最优解。图中的罚分规则不一样但是原理是一样的。这个算法我还算比较了解就不写更多的内容了。
    • 词或K串的方法(Blast) Basic Local Alignment Search Tool
      • 算法原理:blast首先找到两条序列的高度相似小片段,也就是所谓的种子,而后以此为基础向两端延伸,并构建比对,最后为了避免假阳性,还需要计算统计显著性。这里我们会提到关于一种局部比对算法为Smith-Waterman,相比于Needleman-Waterman的全局算法它一定程度上解决的速度的问题,但是它对整个计算量的要求还是太高,因此才有了启发式近似算法(Heuristic approach)Blast的产生,它虽然不如前者精确,但是速度确是其50倍。>
      • 详细解答(我了解的不深入,具体的公式没有计算过,参考)
        • 首先确定seed,成为seed word。假设w为seed的长度,那么对于长度为n的序列种子的个数为n-w+1。seeding这个过程就是相当于建立一个索引,用里面每一个seed去比对data base中的序列,这样得到一个这样的图片。当然,根据前面的动态规划算法我们可以知道最优解应该平行于主对角线,我们可以去掉零散的一些hits。顺便向两边延伸并且寻求最优解,当罚分低于一个指定的值的时候终止比对。



全局比对到局部比对
  • 写在前面的话
    上世纪70年代,Needleman-Wunsch提出了End-to-end的全局比对算法,我们解决了把两条序列进行比对的问题,但是随着越来越多的蛋白质被测序,人们越来约发现某些蛋白差异虽然很大,但是在局部的功能域上却很相似,这些功能域相当保守且发挥相近的重要功能,但是仅靠全局比对算法却很那发现他们,其次,70年代内含子的发现让人们不得不考虑在核酸序列进行比对的时候,内含子导致的大片段差异。所以我们还需要能够发现局部相似的序列。然后就有了Smith-Whaterman算法。如果大家仔细查看过这两篇文章大家一定会发现一个神奇的事情,后面这两个人仅仅给之前的算法设置了一个最低罚分不超过0的选项,就发了一篇生物信息学历史上引用率最高的文章之一。真的是酷的不行。
  • 如果前面大家理解了前面的全局比对,那么局部比对的算法用这个公式来说明再简单不过了。这个0花了整整10年时间,其实这个0只是赋予了一部分(局部)重新开始的机会。这里面给出一个链接大家自己看看就明白了B站视频




上一篇:protein coding gene及其上下2kb范围内平均DNA甲基化水平图怎么画
下一篇:以前用RNAi技术,现在改为CRISPR
回复

使用道具 举报

1

主题

2

帖子

60

积分

注册会员

Rank: 2

积分
60
 楼主| 发表于 2018-3-25 00:07:07 | 显示全部楼层
学习学校课程有感而发,顺带Google加上看北京大学生物信息学课程小小总结一下,关于E-value和Score的计算方法有点没看懂倒是。
回复 支持 反对

使用道具 举报

2

主题

23

帖子

409

积分

中级会员

Rank: 3Rank: 3

积分
409
发表于 2018-3-25 14:27:40 | 显示全部楼层
非常感谢,很好
回复 支持 反对

使用道具 举报

2

主题

23

帖子

409

积分

中级会员

Rank: 3Rank: 3

积分
409
发表于 2018-3-25 14:41:06 | 显示全部楼层
另外手打错误还是再修正一下吧,既然是为了记忆
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

QQ|手机版|小黑屋|生信技能树    

GMT+8, 2019-3-24 03:28 , Processed in 0.032254 second(s), 27 queries .

Powered by Discuz! X3.2

© 2001-2013 Comsenz Inc.