第四章双序列比对精选PPT.ppt
《第四章双序列比对精选PPT.ppt》由会员分享,可在线阅读,更多相关《第四章双序列比对精选PPT.ppt(58页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、第四章双序列比对第1页,此课件共58页哦本章内容本章内容双序列比对(双序列比对(Pairwise Sequence Alignment)多序列比对(多序列比对(Multiple Anlignment)核酸序列分析核酸序列分析在生物学研究中,将未知序列同已知序列进行在生物学研究中,将未知序列同已知序列进行比较分析已经成为一种强有力的研究手段比较分析已经成为一种强有力的研究手段,生,生物学领域中绝大部分问题在计算机科学领域中物学领域中绝大部分问题在计算机科学领域中主要体现为序列或字符串的问题主要体现为序列或字符串的问题。第2页,此课件共58页哦概念概念1双序列比对(双序列比对(pairwise a
2、lignment):指通过一定的算法:指通过一定的算法对两个对两个DNA或蛋白质序列进行比较,找出两者之或蛋白质序列进行比较,找出两者之间最大相似性匹配。这种间最大相似性匹配。这种算法算法是基于序列本身的属是基于序列本身的属性而不是关于该序列第注释信息。目的是推测它们在性而不是关于该序列第注释信息。目的是推测它们在结构、功能会进化上的联系。结构、功能会进化上的联系。(达尔文自然选(达尔文自然选择)择)理论基础:理论基础:进化学说如果两个序列之间具有足够的进化学说如果两个序列之间具有足够的相似性,就推测二者可能有共同的进化祖先,经过相似性,就推测二者可能有共同的进化祖先,经过序列内残基的替换、残
3、基或序列片段的缺失、以及序列内残基的替换、残基或序列片段的缺失、以及序列重组等遗传变异过程分别演化而来。序列重组等遗传变异过程分别演化而来。分为分为2类:类:1.基于序列的基于序列的局部局部相似性相似性2.基于序列第基于序列第全局全局相似性相似性第3页,此课件共58页哦相似性(相似性(similarity):是指一种很直接的数):是指一种很直接的数量关系,量关系,可以量化的参数。一般是以百分比来可以量化的参数。一般是以百分比来衡量。衡量。同源性(同源性(homology):进化过程中源于同一):进化过程中源于同一祖先的分支之间的关系,它是质的判断。祖先的分支之间的关系,它是质的判断。粗粗略的说
4、,如果序列之间的相似性超过略的说,如果序列之间的相似性超过30%30%,它,它们就很可能是同源的。们就很可能是同源的。基因之间要么同源,要么不同源。而相似性则基因之间要么同源,要么不同源。而相似性则具有多或少的数量关系。具有多或少的数量关系。第4页,此课件共58页哦直系同源物(直系同源物(orthologs):不同物种中具:不同物种中具有相同功能的同源基因或蛋白质。有相同功能的同源基因或蛋白质。并系同源物(并系同源物(paralogs):个体中有一定的:个体中有一定的关系又不相同的蛋白,由同一个基因经关系又不相同的蛋白,由同一个基因经连续复制而形成。复制所得基因经历了连续复制而形成。复制所得基
5、因经历了各自动进化途径,从而使新物种通过变各自动进化途径,从而使新物种通过变异和适应产生。异和适应产生。第5页,此课件共58页哦1009080706050403020100相相同同残残基基所所占占百百分分比比朦胧区朦胧区暗区暗区双序列比对双序列比对多序列比对多序列比对朦胧区朦胧区:序列比对结果:序列比对结果的相似性小于的相似性小于20,则,则比对不具有统计学意义,比对不具有统计学意义,这个区域称为这个区域称为第6页,此课件共58页哦算法算法:是指按照一定的方式描述计算过程:是指按照一定的方式描述计算过程或处理某个问题的一系列步骤。或处理某个问题的一系列步骤。程序程序:用某种计算机语言编写的实现
6、某个:用某种计算机语言编写的实现某个算法的一组指令集合。算法的一组指令集合。全局性比对:全局性比对:考察考察2个序列之间的整体相个序列之间的整体相似性。似性。局部性比对:局部性比对:着眼于序列中的某些特定片着眼于序列中的某些特定片断,比较这些片断之间的相似性。主要断,比较这些片断之间的相似性。主要用于找出序列中的功能位点用于找出序列中的功能位点,更具有生,更具有生物学意义。物学意义。第7页,此课件共58页哦记分矩阵记分矩阵 A C G TA 0.9 -0.1 -0.1 -0.1C -0.1 0.9 -0.1 -0.1G -0.1 -0.1 0.9 -0.1T -0.1 -0.1 -0.1 0.
7、9 GCGCCTC 记分值:5*0.9+2*(-0.1)GCGGGTC第8页,此课件共58页哦蛋白质序列则复杂的多TTYGAPPWCS TTYGAPPWCSTGYAPPPWS TGYAPPPWS第9页,此课件共58页哦相似性计分矩阵相似性计分矩阵1突变数据(突变数据(mutation data,MD)计分方法是基)计分方法是基于蛋白质序列中于蛋白质序列中单点可接受突变(单点可接受突变(point accepted mutation,PAM),1个个PAM表示每表示每100个个残基中有残基中有1个可接受单点突变。个可接受单点突变。PAM250计分矩阵能在计分矩阵能在20%的水平上反映出的水平上反
8、映出2个个序列之间的相似性,是许多比对软件的缺省值。序列之间的相似性,是许多比对软件的缺省值。对于比对的对于比对的2个序列之间的相似性越高,一般使个序列之间的相似性越高,一般使用用PAM值较低的计分矩阵。值较低的计分矩阵。突变数据计分方法在检测序列进化距离较远的突变数据计分方法在检测序列进化距离较远的序列之间是否具有同源性上具有一定的局限性。序列之间是否具有同源性上具有一定的局限性。第10页,此课件共58页哦残基差异百分率与进化距离残基差异百分率与进化距离PAM值之间的对照值之间的对照1102030405060708011123385680112159246残基差异残基差异PAM第11页,此课
9、件共58页哦相似性计分矩阵相似性计分矩阵2BLOSUM取代矩阵:基本的数据来源取代矩阵:基本的数据来源于于BLOCKS数据库。与数据库。与PAM一样,也一样,也有许多编号的有许多编号的BLOSUM矩阵。矩阵。BLOSUM80:具有具有80或以上相同残基或以上相同残基地序列组成的序列模块用于产生地序列组成的序列模块用于产生BLOSUM80矩阵。矩阵。克服了突变数据计分方法在检测序列克服了突变数据计分方法在检测序列进化距离较远的序列之间是否具有同进化距离较远的序列之间是否具有同源性的弊端。源性的弊端。第12页,此课件共58页哦比对的算法比对的算法Needleman-Wunsch 算法适用于整体水平
10、算法适用于整体水平上相似性程度较高的上相似性程度较高的2个序列。是整体比对个序列。是整体比对算法,其结果反映了算法,其结果反映了两个序列中所有残基两个序列中所有残基地整体相似性。地整体相似性。Smith-Waterman算法算法在识别局部相似性时,在识别局部相似性时,具有很高的灵敏度,具有很高的灵敏度,但只是寻找序列中一但只是寻找序列中一些小的、具有些小的、具有局部相局部相似性似性的片断。的片断。第13页,此课件共58页哦Basic Pairwise AlignmentBasic Pairwise AlignmentConsider two amino acid sequences calle
11、d S1 and S2Dynamic Programmingglobal alignment:(Needleman-Wunsch)local alignment:(Smith-Waterman):Stochastic Based Current ImprovementsHeuristic Approximation(Database Search)FASTABLAST 2(Altschul et al.1997)BLATSpeedSpacePsi-BlastBLASTNBLASTPPLASTX.qAny prefix of the optimal alignment between S1 an
12、d S2 is an optimal alignment between a prefix of S11,i of S1 and a prefix of S11,.,j of S2.i,j are the length of S1 and S2,respectively.Define:F(i,j)=Max Similarity(S11,i,S21,j)qF(i,j)=MaxF(i-1,j-1),f(I-1,j),f(I,j-1)seek the best local,gapped alignment between the query string and each of the databa
13、se sequences.some preliminary work.DP100 times faster than Smith-Waterman,and nearly as sensitive and selective,Time:O(log(n)n is the size of databasestandard substitution matrixstandard substitution matrixPAMBLOSUMCONNETGap modelGap modelCONSTANTAFFINECONVEXSegment MethodsExhaustive assessment by m
14、atrix comparison(DotPlot)第14页,此课件共58页哦基于双序列比对的数据库搜索基于双序列比对的数据库搜索FastA 和BLAST程序是目前最常用的基于局部相似性数据库搜索程序。主要的优点在于运行速度较快,可以在普通计算机上运行。第15页,此课件共58页哦FASTAFASTA算法由Pearson and Lipman(1985)提出。基本思路是识别与检测序列相匹配的很短的序列片断,称为k-tuple.用于蛋白质序列比对时,k-tuple长度为12个残基,用于DNA序列比对时,k-tuple长度最多为6个碱基。通过比较2个序列中断片断及其相对位置可以构成一个动态规划矩阵地对
15、角线方向上的一些匹配片断期望值E:E值越接近0,表明2序列第匹配不大可能是由随机因素造成的,即E值越低,置信度越高。第16页,此课件共58页哦FASTA-Stages1.Find k-tups in the two sequences(k=1,2 for proteins,4-6 for DNA sequences)2.Score and select top 10 scoring“local diagonals”a.For proteins,each k-tup found is scored using the PAM250 matrixb.For DNA,the number of k-
16、tups foundc.Penalize intervening gaps第17页,此课件共58页哦Finding k-tupsposition 1 2 3 4 5 6 7 8 9 10 11protein 1 n c s p t a.protein 2.a c s p r k position in offsetamino acid protein A protein B pos A-posB-a 6 6 0c 2 7 -5k -11n 1 -p 4 9 -5r -10s 3 8 -5t 5 -Note the common offset for the 3 amino acids c,s
17、and pA possible alignment is thus quickly found-protein 1 n c s p t a|protein 2 a c s p r k第18页,此课件共58页哦FASTA,K-tups with common offset第19页,此课件共58页哦FASTA-Stages3.Rescan top 10 regions,score with PAM250(proteins)or DNA scoring matrix.Trim off the ends of the regions to achieve highest scores.4.Try to
18、 join regions with gapped alignments.Join if similarity score is one standard deviation above average expected score5.After finding the best initial region,FASTA performs a global alignment of a 32 residue wide region centered on the best initial region,and uses the score as the optimized score.第20页
19、,此课件共58页哦FASTAFastA is a family of programs:FastA,TFastA,FastX,FastYQuery:DNA ProteinDatabase:DNAProtein第21页,此课件共58页哦FastA Blosum50 default.Lower PAM higher blosum to detect close sequencesHigher PAM and lower blosumto detect distant sequencesGap opening penalty-12,-16 by default for fasta with prot
20、eins and DNA,respectivelyGap extension penalty-2,-4 by default for fasta with proteins and DNA,respectively The larger the word-length the less sensitive,but faster the search will beMax number of scores and alignments is 100第22页,此课件共58页哦FastA OutputDatabase code hyperlinked to the SRS database at E
21、BIAccession numberDescriptionLengthInitn,init1,opt,z-score calculated during runE score-expectation value,how many hits are expected to be found by chance with such a score while comparing this query to this database.E()does not represent the%similarity第23页,此课件共58页哦FASTA Output第25页,此课件共58页哦BLASTBasi
22、c Local Alignment Search Tool(基本基本局部比对搜索工具局部比对搜索工具),基于,基于unix系统,速系统,速度很快,但又最小程度的牺牲灵敏度。度很快,但又最小程度的牺牲灵敏度。并建立在严格的统计学基础之上并建立在严格的统计学基础之上。BLAST算法要点是基于算法要点是基于序列片断对序列片断对的概的概念:两个给定序列中的一对子序列,它念:两个给定序列中的一对子序列,它们长度相等,且可以形成无空位的完全们长度相等,且可以形成无空位的完全匹配。匹配。NCBINCBI提供了基于提供了基于WebWeb的的BLASTBLAST服务。服务。第26页,此课件共58页哦BLAST运
23、行步骤找出待测序列与目标序列间所有匹配程找出待测序列与目标序列间所有匹配程度超过一定阀值得度超过一定阀值得序列片断对序列片断对对具有一定长度的片断对根据给定的相对具有一定长度的片断对根据给定的相似性阀值延伸,得到一定长度的相似性似性阀值延伸,得到一定长度的相似性片断高分值片断对(片断高分值片断对(high-scoring pairs,HSPs).无空位的无空位的BLAST比对算法(原算法)比对算法(原算法)。新算法经过改进允许插入空位,而且比新算法经过改进允许插入空位,而且比原算法快原算法快3倍。倍。第27页,此课件共58页哦Blast ApplicationBlast is a family
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第四 序列 精选 PPT
限制150内