序列比对与数据库搜索

第四章序列比较与数据库搜索,主讲：张宏西北农林科技大学农学院遗传教研组,第一节序列比对,序列比较的根本任务是：寻找序列之间的相似性辨别序列之间的差异是进行序列相似性与同源性分析的一种研究方法目的：相似序列相似的结构，相似的功能判别序列之间的同源性推测序列之间的进化关系,1.序列的相似性与同源性,同源（homology）-具有共同的祖先,趋异进化。直系（向）同源（Orthologous）基因功能相同，出现在不同物种旁系（共生）同源（paralogous）在同一基因组，功能不同相似（similarity）同源序列一般是相似的相似序列不一定是同源的进化趋同（同功能）,数据库搜索的基础是序列的相似性比对，而寻找同源序列则是数据库搜索的主要目的之一。所谓同源序列，简单地说，是指从某一共同祖先经趋异进化而形成的不同序列。同源性可以用来描述染色体“同源染色体”、基因“同源基因”和基因组的一个片断“同源片断”必须指出，相似性(similarity)和同源性(homology)是两个完全不同的概念。,相似性和同源性,相似性是指序列比对过程中用来描述检测序列和目标序列之间相同DNA碱基或氨基酸残基顺序所占比例的高低。相似性本身的含义，并不要求与进化起源是否同一，与亲缘关系的远近、甚至于结构与功能有什么联系。当相似程度高于50%时，比较容易推测检测序列和目标序列可能是同源序列；而当相似性程度低于20%时，就难以确定或者根本无法确定其是否具有同源性。总之，不能把相似性和同源性混为一谈。所谓“具有50%同源性”，或“这些序列高度同源”等说法，都是不确切的，应该避免使用。,定性的描述定量的数值相似度距离,1.1序列的相似性描述,序列比较的基本操作是比对（Alignment）两个序列的比对是寻找这两个序列中各个字符的一种一一对应关系，或字符的对比排列。分析序列同源性和相似性的过程。,设有两个序列：GACGGATTAG，GATCGGAATAG,Alignment2:GA-CGGATTAGGATCGGAATAG,Alignment1:GACGGATTAGGATCGGAATAG,序列比较可以分为四种基本情况：（1）两条长度相近的序列相似找出序列的差别（2）判断一条序列的前缀与另一条序列的后缀相似（3）判断一条序列是否是另一条序列的子序列（4）判断两条序列中是否有非常相似的子序列,序列比对的基本思想，是找出检测序列和目标序列的相似性。比对过程中需要在检测序列或目标序列中引入空位(一般用”-”来表示)，以表示插入或删除（图2）来比较两个（双序列比对）或多个序列（多序列比对）,使得这些序列获得最大匹配。,图2序列比对，图中“-”表示插入和删除，用字符表示相同的残基，“+”表示相似残基,1.2序列比对的基本思想,序列比对的最终实现，必须依赖于某个数学模型。不同的模型，可以从不同角度反映序列的特性，如结构、功能、进化关系等。很难断定，一个模型一定比另一个模型好，也不能说某个比对结果一定正确或一定错误，而只能说它们从某个角度反映了序列的生物学特性。此外，模型参数的不同，也可能导致比对结果的不同。,序列比对的数学模型大体可以分为两类:整体比对（globalalignment）:序列的整体局部比对（Localalignment）:序列部分区域局部相似性比对的生物学基础:蛋白质功能位点往往是由较短的序列片段组成的，这些部位的序列具有相当大的保守性，尽管在序列的其它部位可能有插入、删除或突变。局部相似性比对往往比整体比对具有更高的灵敏度，其结果更具生物学意义。,1.3序列比对的数学模型,计算两条序列间的最适比对的经典算法：算法：做任何事情都有一定的步骤。为解决一个问题而采取的方法和步骤，就称为算法。Needleman-Wunsch算法：整体比对算法，最佳比对（两条蛋白质序列具有最多匹配残基）中包括了全部的最短匹配序列。Smith-Wateman算法：在Needleman-Wunsch算法基础上发展而来的一种局部比对算法。这二种算法均可以用于核酸和蛋白质序列。在给定空位罚值和替换矩阵情况下，它们总是能给出具有最高联配值的联配。但是，这个联配并不需要达到生物学意义上的显著水平。,1.4序列比对的经典算法,1.5序列比对的实施方法1.5.1距离的编辑与计算,GCATGACGAATCAGTATGACAAACAGC,GCATGACGAATCAGTATGAC-AAACAGC,说明两条序列的相似程度定量计算,两条序列的相似程度的定量计算相似度：其值越大，序列越相似距离：距离越大，序列的相似度就越小,ACCGACAATATGCATAATAGGTATAACAGTCA,扩展的编辑操作,1.5.2通过点矩阵进行序列比较-“矩阵作图法”或“对角线作图”,1.5.3滑动窗口技术,问题？两条序列中有很多匹配的字符对，因而在点矩阵中会形成很多点标记。解决方案使用滑动窗口代替一次一个位点的比较是解决这个问题的有效方法。假设窗口大小为10，相似度阈值为8，则每次比较取10个连续的字符，如相同的字符超过8个，则标记。基于滑动窗口的点矩阵方法可以明显地降低点阵图的噪声，并且明确无误的指示出了两条序列间具有显著相似性的区域。,1.5.4序列两两比对,序列两两比对（PairwiseSequenceAlignment）按字符位置重组两个序列，使得两个序列达到一样的长度。例如：s:AGCACACAt:ACACACTAcost=2s:AGCACACAt:ACACACTAscore(s，t）=5序列比对的目的是寻找一个得分最大（或代价最小）的比对。,1.5.5打分矩阵（WeightMatrices）,（1）核酸打分矩阵设DNA序列的字母表为=A，C，G，Ta.等价矩阵b.BLAST矩阵c.转移矩阵（transition，transversion）（嘌呤：腺嘌呤A，鸟嘌呤G；嘧啶：胞嘧啶C，胸腺嘧啶T）,表3.1等价矩阵表,表3.3转移矩阵,表3.2BLAST矩阵,（2）蛋白质打分矩阵,等价矩阵氨基酸突变代价矩阵GCM疏水矩阵PAM矩阵（PointAcceptedMutation）BLOSUM矩阵（BlocksAminoAcidSubstitutionMatrices）,PAM矩阵（PointAcceptedMutation）,基于进化原理，基于进化的点突变模型证据：编码相同蛋白质的基因随着进化发生分歧，相似度降低。一个PAM就是一个进化的变异单位,即1%的氨基酸改变，如PAM120矩阵用于比较相距120个PAM单位的序列。分析同源蛋白在进化中氨基酸变化的可能性。可针对不同的进化距离采用相应的PAM矩阵序列相似度=40%50%60%1427|打分矩阵=PAM120PAM80PAM60PAM250,基于蛋白质模块数据库,以序列片段为基础为解决序列的远距离相关，从蛋白质模块数据库BLOCKS中找出一组替换矩阵分析蛋白的功能保守区域的可能性。通过设置不同的百分比，产生了不同矩阵。=80%相同的序列组成的串对应BLOSUM80矩阵=62%相同的序列组成的串对应BLOSUM62矩阵,BLOSUM矩阵（BlocksAminoAcidSubstitutionMatrices）,第二节序列两两比对,1、序列两两比对的基本算法,直接方法生成两个序列所有可能的比对，分别计算代价函数，然后挑选一个代价最小的比对作为最终结果。本质问题：优化动态规划寻优策略动态规划算法（DynamicProgramming）,1、子序列与完整序列的比对（局部比对）,-AGCT-ATGCAGCTGCTT目标：？使序列最大匹配，不计前缀的得分,也不计删除后缀的得分序列S:-AGCT-序列t:ATGCAGCTGCTT,2、准全局比较,准全局比较：在评价序列比对时不计终端“空缺”（endspace，或空位）的得分或代价,序列1长度为8序列2长度为18（a）准全局比对：6个匹配，1个失配，1个空位（b）全局比对：8个匹配,3、连续空位,K阶空位K个连续的空位字符“-”ATG-A-T-C-A-GATG-ATCAGATGCAGTGCAATGATGTTTTTATCAG空位罚分生物学意义“插入”或“删除”突变突变次数连续空位可能对应于一次突变非连续空位对应于多次突变,第三节序列多重比对,目的：发现多个序列的共性发现与结构和功能相关的保守序列片段设：有k个序列s1,s2,.,sk，每个序列由同一个字母表中的字符组成，k大于2。通过插入操作，使得各序列达到一样的长度。,1、SP（Sum-of-Pairs）模型,评价多重序列比对的结果,按照每个对比的列进行打分，然后加和处理每一列：k个变量的打分函数用一个k维数组来表示该函数（类似于打分矩阵）期望：函数在形式上应该简单具有统一的形式不随序列的个数而发生形式变化,2、多重比对的动态规划算法,多重序列比对的最终目标是通过处理得到一个得分最高（或代价最小）的序列对比排列，从而分析各序列之间的相似性和差异。,3、计算方法的优化,标准动态规划算法存在的问题：搜索空间大剪枝技术：将搜索空间限定在一个较小的区域范围内。若问题是搜索一条得分最高（或代价最小）的路径，则在搜索时如果当前路径的得分低于某个下限（或累积代价已经超过某个上限），则对当前路径进行剪枝，即不再搜索当前路径的后续空间。,4、星形比对,星形比对的基本思想是：在给定的若干序列中，选择核心序列，通过该序列与其它序列的两两比对形成所有序列的多重比对，并使得所有多重比对在核心序列和任何一个其它序列方向的投影是最优的两两比对。利用标准的动态规划方法求出最优两两比对将这些两两比对聚集起来并采用“只要是空白，则永远是空白”的原则。,使用最广泛的多重序列比对程序是ClustalWClustalW是一种渐进的比对方法，先将多个序列进行两两比对，基于这些比较，计算得到一个距离矩阵，该矩阵反映了每对序列的关系,EBI的CLUSTALW网址是：http:/www.ebi.ac.uk/clustalw/,5、统计特征分析,对于所得到的多重序列比对，我们往往需要进行归纳分析，总结这些序列的特征，或者给出这些序列共性的表示,HLVVGVLVGGNLVVLHCLV-VHCL-,（1）保守序列表示序列每个位置上最可能出现的字符（或者所有可能出现的字符）ATNTSC(N-A,T,C,G;S-G,C),（2）特征统计图（Profile）令P=(P1,P2,PL)，P表示每一列上各种字符出现的概率分布Pj=(pj0,pj1,pj|A|)A代表字母表，Pjk代表字母表A中第k个字符在第j列出现的概率。第0个字符是特殊的空位符号“-”。,利用保守序列或者特征统计图，可以判断一个序列是否满足一定的特征一条序列与特征统计图相对照，如果代价值小，说明该序列具有相应的特征，否则该序列不具备相应的特征。,第四节数据库搜索,数据库使用关键字查询目标搜索序列搜索问题搜索效率标准算法O(n2)最流行的序列数据库快速搜索程序BLASTFastA,数据库查询：为生物学研究提供了一个重要工具，在实际工作中经常使用。研究中的问题？新测定的碱基序列或由此翻译得到的氨基酸序列，往往需要通过数据库搜索，找出具有一定相似性的同源序列，以推测该未知序列可能属于哪个基因家族，具有哪些生物学功能？氨基酸序列，是否可能找到已知三维结构的同源蛋白质而推测其可能的空间结构？数据库搜索与数据库查询一样，是生物信息学研究中的一个重要工具。,1.数据库使用,数据库搜索的基础：序列的相似性比对，即双序列比对(pairwisealignment)。检测序列(probesequence)：新测定的、希望通过数据库搜索确定其性质或功能的序列；目标序列(subjectsequence)：通过数据库搜索得到的和检测序列具有一定相似性的序列。BLAST和Fasta程序目前最常用的基于局部相似性的数据库搜索程序，基于查找完全匹配的短小序列片段，并将它们延伸得到较长的相似性匹配。优势在于可以在普通的计算机系统上运行，而不必依赖计算机硬件系统而解决运行速度问题。,2.BLAST,BLAST基本局部对比排列搜索工具（BasicLocalAlignmentSearchTool）。研制BLAST的最初目的改善FastA的算法的性能提高计算速度国际著名生物信息中心都提供基于Web的BLAST服务器。BLAST程序之所以使用广泛，主要因为其运行速度比Fasta等其它数据库搜索程序快，且改进后的BLAST程序允许空位的插入。,2.1BLAST的基本思想,序列S:,序列t:,找出两个序列共同的短片段经过扩展后形成更长的相似片断,扩展,扩展,BLAST基本算法,BLAST算法：将查询序列分为多个短片段及相似片段；筛选数据库以发现具备以上片段的序列；将匹配序列进行延伸，插入和延伸gap，根据突变矩阵或模块替代矩阵计分排序；返回分值最高的匹配序列保证快速高效,BLAST算法的基本要点是序列片段对（segmentpair）。序列片段对是指两个给定序列中的一对子序列，它们的长度相等，且可以形成无空位的完全匹配。BLAST算法的过程设定阈值S，或采用程序缺省的推荐值；找出查询序列和目标序列间所有匹配程度超过该阈值的序列片段对，即“种子”序列，它是两个序列之间的一个非常短的片段对；对具有一定长度的片段对根据给定的相似性阈值延伸，得到一定长度的相似性片段，称高分值片段对（high-scoringpairs,HSPs）。也就是种子序列向两个方向扩展，直至达到扩展的最大可能的得分。,BLAST软件包实是综合在一起的一组程序，不仅可用于直接对蛋白质序列数据库和核酸序列数据库进行搜索，而且可以将检测序列翻译成蛋白质或将核酸数据库翻译成蛋白质后再进行搜索，以提高搜索结果的灵敏度。,BLAST程序检测序列和数据库类型,BLAST程序的适用特点,BLAST程序免费软件，可以从美国国家生物技术信息中心NCBI等文件下载服务器上获得，安装在本地计算机上，包括UNIX系统和WINDOWS系统的各种版本。BLAST格式的数据库但必须有BLAST格式的数据库，可以从NCBI下载，也可以利用该系统提供的格式转换工具由其它格式的核酸或蛋白质序列数据库经转换后得到。高性能的服务器对核酸序列数据库而言，不论用哪种方式，都需要很大的磁盘空间；而程序运行时，需要有较大的内存和较快的运算速度，因此必须使用高性能的服务器。,2.2BLAST的使用,一般用户，目前常用的办法是通过NCBI、EBI等国际著名生物信息中心的BLAST服务器进行搜索。北京大学生物信息中心也提供BLAST数据库搜索服务。需要说明的是，各生物信息中心BLAST用户界面有所不同，所提供的数据库也可能不完全相同，使用前最好先进行适当的选择,BLAST程序、数据库及参数的选择,蛋白序列：BlastPtBLastN核酸序列：BlastN-Blastx-tblastx数据库的选择：nr最为常用；month跟踪每个月新增数据；swissprot蛋白库注释详尽等等,BLAST服务器提供的数据库和参数很多，用户可以根据不同要求，选择不同的数据库和各种参数。一般情况下，可以先按照系统给定的缺省参数进行初步搜索，对结果进行分析后再适当调整参数，如改变相似性矩阵、增加或减少空位罚分值、调节检测序列滑动窗口大小等。对于核酸序列数据库，一般选择重复序列屏蔽功能；对于蛋白质序列，特别是球蛋白，通常不必选择重复序列屏蔽功能。,在此粘贴序列,选择序列区段选择数据库,3.3BLAST程序结果解读程序名称、版本号以及文献引用出处检索序列的名称、数据库名称；图示主要比对结果列出相似性值较高的序列条目，以及它们在数据库中的编号和简要说明，每个条目后面给出相似性分数值Score和期望频率值E，以相似性分数值大小为序排列，相似性分数越高，相似性越大；E值则表示随机匹配的可能性，E值越大，随机匹配的可能性也越大。最后给出检测序列和目标序列的比对结果。,BLAST结果的评价,比对好坏的评价：Bit分值考虑了比对中相同和相似基团、gap、替代矩阵，并经过标准化；Bit分值越高,比对越好一致性：蛋白序列25%，核酸序列70%（参考）比对统计学意义的评价：E值（E-value）E值越低,则比对就更有可能具有显著性其他：比对的长度,3.1Fasta的基本思想,序列s:,序列t:,找出两个序列具有最大匹配的相对位移,3.Fasta,位移=6,6810s：-A-A-T-t:-A-A-T-357,位移=3,基本思路识别与查询序列相匹配的很短的序列片段，称为k-tuple。蛋白质序列数据库时，一般是1-2个残基长；DNA序列数据库时，通常采用3-4，最多为6个碱基。通过比较两个序列中的短片段及其相对位置，可以构成一个动态规划矩阵的对角线方向上的一些匹配片段。FastA程序采用渐进（heuristicapproach）算法将位于同一对角线上相互接近的短片段连接起来，即通过不匹配的残基将这些匹配残基片段连接起来，得到较长的相似性片段。FastA输