blast算法介绍

亢雨笺2013年11月1日生物中最被关注的DNA、RNA、蛋白质，都具有线性的序列信息研究序列相似性关注其功能、演化历史无法通过穷举得到所有的两两比对结果动态规划一个大问题可以分成若干个子问题寻找每个子问题的最优解，就是最终的最优解例如有两条序列AAG和AGC进行比对要比较整条序列：CAGAGC子问题：每个残基的比较ACA–-CAC–AC-每步比对的分数为之前的分数加上这一步的最大值，对应公式为：gapopen=-5gapextension=-5假设比较序列AAGAGCgapopen=-5gapextension=-5假设比较序列AAGAGCgapopen=-5gapextension=-5假设比较序列AAGAGCgapopen=-5gapextension=-5需要比对序列的结构域，而不是整条序列时，Needleman-Wunsch算法并不适用同样考虑比较序列AAGAGC假设比较序列AAGAGCgapopen=-5gapextension=-5假设比较序列AAGAGCgapopen=-5gapextension=-5gapopen=-5gapextension=-5(JonathanPevsner,BioinformaticsandFunctionalGenomics)PAM矩阵是基于近相关蛋白数据的，并且假设高度相关蛋白的取代概率可以外推到远相关蛋白的概率而BLOSUM矩阵是基于实际观测到的远相关蛋白构建的因此在比对较远蛋白时，应选BLOSUM矩阵BLOSUM62BLOSUM80当数据库较大，查询序列较多或较长时，时间消耗太大eg.142*192206270*1μs≈7.5hrsHBA_HUMANSwissProt氨基酸数FASTA(Pearson和Lipman,1988)BasicLocalAlignmentSearchTool(Altschul等,1990)△启发式算法：以牺牲灵敏度（sensitivity）为代价，提升计算速度△与Smith-Waterman算法不同，不能保证找到最佳匹配找种子序列在数据库中定位种子延伸匹配把查询序列划成kmer,找所有覆盖到的种子序列k-merwords长度w,最后得到n-w+1个字串一般来说：对蛋白w=3，核酸w=11种子越短：灵敏度越高计算速度越慢1.根据查询序列划分出的字串2.这些单词分数高于neighborhoodwordscorethreshold（T）的邻居字串（这个分数根据计分矩阵得到，我们这里以BLOSUM62矩阵为例）BLAST2：T=11字串邻居字串对于单词列表中的每一个字串，在所有的数据库序列中找到其出现的每一个位置。由于数据库预先有建立索引，因此查询种子找到match是非常快的。可以利用如下方法：利用hash建index后缀树Aho-Corasick自动机算法利用打分矩阵沿左右两个方向延伸hitcluster直到打分低于一个临界值，得到的结果称为高分片段对（high-scoringsegmentpair,HSP）。hitclusterhithitmap两个hits没有overlap两个hits有同样的diagonal两个hits在同一个window内（windowlength一般为40）Diagonal：某个word在数据库序列中起始位置是x1，在查询序列中起始位置是x2，x1-x2即为diagonal通过局部实现Smith-Waterman算法，将之前得到的hitcluster的匹配进行延伸，直到分值降低到某个阈值时停止。从而得到为高分片段对（HSP）有时也将一个数据库序列中的多个HSP区域结合成一个更长的比对结果对于相邻或距离较近的HSP，可以把它们合并当需要比较这些结合区域之间分值高低时，有以下两种方法：1.Poisson法则（Poissonmethod）（old）2.总分法则（sum-ofscoresmethod）Eg.（65,40）和（52,45）Poisson法则：（52,45）→4540总分法则：（65,40）→65+40（105）52+45（97）查询序列中一些低复杂度区域会带来假阳性，例如：微卫星序列-CACACACACACACACA-AAAAAAAAAAAA-KLKLKLKLKLKLKL因此需要用如下字母去掩盖这些区域-Ns（核酸）-Xs（蛋白）将查询序列与一系列统一长度的随机序列进行比对时，分值通常符合Gumbel极值分布。累积概率分布：因此对于序列m和n，观察到一个大于等于x的比对分数S的概率：要使用该式，必须知道λ和μ。μ=[log(Kmn)]/λ⇒P(S≥x)=1-exp(-Kmne-λx)K、λ:与打分矩阵相关的参数m:查询序列长度n:数据库大小改进后BLAST有将m、n进行矫正用m’和n’（有效长度）来计算Evalue：在随机情况下，获得比当前比对分数相等或更高的可能比对条数。（期望值）BitscoreS’（比特分数）将原始分数对打分系统的变量进行归一化，使不同的BLAST搜索结果可以进行比较Pvalue：分值大于等于要求分值的比对的随机发生概率P0,显著性越高将随机序列（长度与实际查询序列一致）作为查询序列了搜索数据库，联系实际查询序列得到的比对分值得到：P=1–e-EPvalue和Evalue是反映比对显著性的两种不同方式当E＜0.1：E≈PP=1–e-EE值和P值关系：（BLAST的结果只列出了E值）(JonathanPevsner,BioinformaticsandFunctionalGenomics)数据库中某些蛋白相关性较小，搜索效果差PSI-BLAST比常规算法更敏感，主要用于搜索与我们感兴趣蛋白远缘相关的蛋白。用常规的blastp搜索数据库构建多序列比对，为每个比对建立一个专门的序列谱（profile）利用profile搜索原来的数据库检验比对后每个匹配的统计显著性重复多次，直至不再出现新的结果传统BLAST对计分矩阵依赖较大HSP的分值均依赖于固定的计分矩阵的均值每次比对都特异建立一个新的计分矩阵位点特异计分矩阵（PSSM）使不能被搜索到的远缘蛋白被比对上位点特异计分矩阵（PSSM）行：20个氨基酸列：查询序列分数：每个位点的lg(Qi/Pi)Qi–残基i在该位点出现的估计概率Pi–这个残基的背景概率Altschul,BasicLocalAlignmentTool,J.Mol.Biol.,1990Altschul,GappedBLASTandPSI-BLAST,J.Mol.Biol.,1997JonathanPevsner,BioinformaticsandFunctionalGenomics,2006SlidesfromGaoG