第四章双序列比对

第四章双序列比对第1页，共58页，2023年，2月20日，星期三本章内容双序列比对（PairwiseSequenceAlignment）多序列比对（MultipleAnlignment）核酸序列分析在生物学研究中，将未知序列同已知序列进行比较分析已经成为一种强有力的研究手段，生物学领域中绝大部分问题在计算机科学领域中主要体现为序列或字符串的问题。第2页，共58页，2023年，2月20日，星期三概念1双序列比对（pairwisealignment）：指通过一定的算法对两个DNA或蛋白质序列进行比较，找出两者之间最大相似性匹配。这种算法是基于序列本身的属性而不是关于该序列第注释信息。目的是推测它们在结构、功能会进化上的联系。（达尔文－－自然选择）理论基础：进化学说－－如果两个序列之间具有足够的相似性，就推测二者可能有共同的进化祖先，经过序列内残基的替换、残基或序列片段的缺失、以及序列重组等遗传变异过程分别演化而来。分为2类：基于序列的局部相似性基于序列第全局相似性第3页，共58页，2023年，2月20日，星期三相似性（similarity）：是指一种很直接的数量关系，可以量化的参数。一般是以百分比来衡量。

同源性（homology）：进化过程中源于同一祖先的分支之间的关系，它是质的判断。粗略的说，如果序列之间的相似性超过30%，它们就很可能是同源的。基因之间要么同源，要么不同源。而相似性则具有多或少的数量关系。第4页，共58页，2023年，2月20日，星期三直系同源物（orthologs）：不同物种中具有相同功能的同源基因或蛋白质。并系同源物（paralogs）：个体中有一定的关系又不相同的蛋白，由同一个基因经连续复制而形成。复制所得基因经历了各自动进化途径，从而使新物种通过变异和适应产生。第5页，共58页，2023年，2月20日，星期三1009080706050403020100相同残基所占百分比朦胧区暗区双序列比对多序列比对朦胧区：序列比对结果的相似性小于20％，则比对不具有统计学意义，这个区域称为～第6页，共58页，2023年，2月20日，星期三算法：是指按照一定的方式描述计算过程或处理某个问题的一系列步骤。程序：用某种计算机语言编写的实现某个算法的一组指令集合。全局性比对：考察2个序列之间的整体相似性。局部性比对：着眼于序列中的某些特定片断，比较这些片断之间的相似性。主要用于找出序列中的功能位点，更具有生物学意义。第7页，共58页，2023年，2月20日，星期三记分矩阵ACGTA0.9-0.1-0.1-0.1C-0.10.9-0.1-0.1G-0.1-0.10.9-0.1T-0.1-0.1-0.10.9

GCGCCTC记分值：5*0.9+2*（-0.1）

GCGGGTC第8页，共58页，2023年，2月20日，星期三蛋白质序列则复杂的多TTYGAPPWCSTTYGAPPWCSTGYAPPPWSTGYAPPPWS第9页，共58页，2023年，2月20日，星期三相似性计分矩阵1突变数据（mutationdata，MD）计分方法是基于蛋白质序列中单点可接受突变（pointacceptedmutation,PAM）,1个PAM表示每100个残基中有1个可接受单点突变。PAM250计分矩阵能在20%的水平上反映出2个序列之间的相似性，是许多比对软件的缺省值。对于比对的2个序列之间的相似性越高，一般使用PAM值较低的计分矩阵。突变数据计分方法在检测序列进化距离较远的序列之间是否具有同源性上具有一定的局限性。第10页，共58页，2023年，2月20日，星期三残基差异百分率与进化距离PAM值之间的对照1102030405060708011123385680112159246残基差异％PAM第11页，共58页，2023年，2月20日，星期三相似性计分矩阵2BLOSUM取代矩阵：基本的数据来源于BLOCKS数据库。与PAM一样，也有许多编号的BLOSUM矩阵。BLOSUM80:具有80％或以上相同残基地序列组成的序列模块用于产生BLOSUM80矩阵。克服了突变数据计分方法在检测序列进化距离较远的序列之间是否具有同源性的弊端。第12页，共58页，2023年，2月20日，星期三比对的算法Needleman-Wunsch

算法适用于整体水平上相似性程度较高的2个序列。是整体比对算法，其结果反映了两个序列中所有残基地整体相似性。Smith-Waterman算法在识别局部相似性时，具有很高的灵敏度，但只是寻找序列中一些小的、具有局部相似性的片断。第13页，共58页，2023年，2月20日，星期三BasicPairwiseAlignmentConsidertwoaminoacidsequencescalledS1andS2DynamicProgrammingglobalalignment:(Needleman-Wunsch)localalignment:(Smith-Waterman):StochasticBasedCurrentImprovementsHeuristicApproximation(DatabaseSearch)FASTABLAST2(Altschuletal.1997)BLATSpeedSpacePsi-BlastBLASTNBLASTPPLASTX………….AnyprefixoftheoptimalalignmentbetweenS1andS2isanoptimalalignmentbetweenaprefixofS1[1,…,i]ofS1andaprefixofS1[1,..,j]ofS2.i,jarethelengthofS1andS2,respectively.Define:F(i,j)=Max[Similarity(S1[1,i],S2[1,j])F(i,j)=Max[F(i-1,j-1),f(I-1,j),f(I,j-1)]seekthebestlocal,gappedalignmentbetweenthequerystringandeachofthedatabasesequences.somepreliminarywork.DP100timesfasterthanSmith-Waterman,andnearlyassensitiveandselective,Time:O(log(n))nisthesizeofdatabasestandardsubstitutionmatrixPAMBLOSUMCONNETGapmodelCONSTANTAFFINECONVEXSegmentMethodsExhaustiveassessmentbymatrixcomparison(DotPlot)第14页，共58页，2023年，2月20日，星期三基于双序列比对的数据库搜索FastA和BLAST程序是目前最常用的基于局部相似性数据库搜索程序。主要的优点在于运行速度较快，可以在普通计算机上运行。第15页，共58页，2023年，2月20日，星期三FASTAFASTA算法由PearsonandLipman(1985)提出。基本思路是识别与检测序列相匹配的很短的序列片断，称为k-tuple.用于蛋白质序列比对时，k-tuple长度为1～2个残基，用于DNA序列比对时，k-tuple长度最多为6个碱基。通过比较2个序列中断片断及其相对位置可以构成一个动态规划矩阵地对角线方向上的一些匹配片断期望值E：E值越接近0，表明2序列第匹配不大可能是由随机因素造成的，即E值越低，置信度越高。第16页，共58页，2023年，2月20日，星期三FASTA-StagesFindk-tupsinthetwosequences(k=1,2forproteins,4-6forDNAsequences)Scoreandselecttop10scoring“localdiagonals”Forproteins,eachk-tupfoundisscoredusingthePAM250matrixForDNA,thenumberofk-tupsfoundPenalizeinterveninggaps第17页，共58页，2023年，2月20日，星期三Ftein2.....acsprkpositioninoffsetaminoacidproteinAproteinBposA-posB-----------------------------------------------------a660c27-5k-11n1-p49-5r-10s38-5t5------------------------------------------------------Notethecommonoffsetforthe3aminoacidsc,sandpApossiblealignmentisthusquicklyfound-protein1ncspta|||protein2acsprk第18页，共58页，2023年，2月20日，星期三FASTA,K-tupswithcommonoffset第19页，共58页，2023年，2月20日，星期三FASTA-StagesRescantop10regions,scorewithPAM250(proteins)orDNAscoringmatrix.Trimofftheendsoftheregionstoachievehighestscores.Trytojoinregionswithgappedalignments.JoinifsimilarityscoreisonestandarddeviationaboveaverageexpectedscoreAfterfindingthebestinitialregion,FASTAperformsaglobalalignmentofa32residuewideregioncenteredonthebestinitialregion,andusesthescoreastheoptimizedscore.第20页，共58页，2023年，2月20日，星期三FASTAFastAisafamilyofprograms:FastA,TFastA,FastX,FastYQuery: DNA ProteinDatabase: DNA Protein第21页，共58页，2023年，2月20日，星期三FastA

Blosum50default.LowerPAMhigherblosumtodetectclosesequencesHigherPAMandlowerblosumtodetectdistantsequencesGapopeningpenalty-12,-16bydefaultforfastawithproteinsandDNA,respectivelyGapextensionpenalty-2,-4bydefaultforfastawithproteinsandDNA,respectivelyThelargertheword-lengththelesssensitive,butfasterthesearchwillbeMaxnumberofscoresandalignmentsis100第22页，共58页，2023年，2月20日，星期三FastAOutputDatabasecodehyperlinkedtotheSRSdatabaseatEBIAccessionnumberDescriptionLengthInitn,init1,opt,z-scorecalculatedduringrunEscore-expectationvalue,howmanyhitsareexpectedtobefoundbychancewithsuchascorewhilecomparingthisquerytothisdatabase.E()doesnotrepresentthe%similarity第23页，共58页，2023年，2月20日，星期三FASTA-EScoresInevaluatingtheEscores,thefollowingrulesofthumbcanbeused:Forsearchesofdatabase,sequenceswithElessthan0.01arealmostalwaysfoundtobehomologous.SequenceswithEbetween1and10frequentlyturnouttoberelatedaswell.第24页，共58页，2023年，2月20日，星期三FASTAOutput第25页，共58页，2023年，2月20日，星期三BLASTBasicLocalAlignmentSearchTool(基本局部比对搜索工具)，基于unix系统，速度很快，但又最小程度的牺牲灵敏度。并建立在严格的统计学基础之上。BLAST算法要点是基于序列片断对的概念：两个给定序列中的一对子序列，它们长度相等，且可以形成无空位的完全匹配。NCBI提供了基于Web的BLAST服务。第26页，共58页，2023年，2月20日，星期三BLAST运行步骤找出待测序列与目标序列间所有匹配程度超过一定阀值得序列片断对对具有一定长度的片断对根据给定的相似性阀值延伸，得到一定长度的相似性片断－－高分值片断对（high-scoringpairs,HSPs）.无空位的BLAST比对算法（原算法）。新算法经过改进允许插入空位，而且比原算法快3倍。第27页，共58页，2023年，2月20日，星期三BlastApplicationBlastisafamilyofprograms:BlastN,BlastP,BlastX,tBlastN,tBlastXBlastN-ntversusntdatabaseBlastP-proteinversusproteindatabaseBlastX-translatedntversusproteindatabasetBlastN-proteinversustranslatedntdatabasetBlastX-translatedntversustranslatedntdatabaseQuery: DNA ProteinDatabase: DNA Protein第28页，共58页，2023年，2月20日，星期三BLASTBLAST包含五个程序和若干个相应的数据库

第29页，共58页，2023年，2月20日，星期三P值：又称为概率值，判断比对的置信度，p值接近于0表明两序列匹配不大可能是由随机因素造成的，p值越小表明置信度越高。ExpectedFrequency(E)value–numberofhitsonecanexpecttoseebychance(noise)whensearchingadatabaseofaparticularsize.Evalueof1–onematchwithasimilarscorebychance.Evalueof0–nomatchesexpectedbychanceStatisticalSignificanceofBlast第30页，共58页，2023年，2月20日，星期三多序列比对多序列比对就是把两条以上可能有系统进化关系的序列进行比对的方法。意义在于描述一组序列之间的相似性关系，以便对一个基因家族的特征有一个基本的了解。构建多序列比对模型的方法有2种：基于序列信息和基于结构信息。从不同的角度反映了序列中所包含的生物学信息。第31页，共58页，2023年，2月20日，星期三12345678910ⅠⅡⅢⅣⅤYYFFYyDDEDEdGGG－GGGGGGGGA－IIAA/IV－LLVV/L－－VVVVEEEQQeAAAAAALLLVLl多序列比对调和序列：获得调和序列的原则：若每列中只有一种残基，则用该残基地大写字母表示；若该列中含有不同残基，则用大多数残基对应的小写字母表示；若该列中出现相同数目的不同残基，则用这些字母对应的大写字母表示。第32页，共58页，2023年，2月20日，星期三算法的复杂性同步法：把给定的所有序列同时进行比对，而不是两两比对或分组进行比对。对计算机系统的要求较高，通常只能进行少量较短序列的比对。步进法：先对所有的序列进行两两比对并计算它们的相似性分值，然后根据相似性分值分成若干组，并在每组之间进行比对，计算相似性分值，再根据分值进行分组继续比对，直到得到最后结果。基于步进法的最常用的多序列比对的程序是Clustal。ClustalW是基于UNIX系统，ClustalX是基于WINDOWS系统。Clustal为免费软件。可从网上下载。生物软件网：/第33页，共58页，2023年，2月20日，星期三CLUSTALW是一种渐进的比对方法，先将多个序列两两比对构建距离矩阵，反应序列之间两两关系；然后从最紧密的两条序列开始，逐步引入邻近的序列并不断重新构建比对，直到所有序列都被加入为止。CLUSTALW的程序可以自由使用，在NCBI的FTP服务器上可以找到下载的软件包。CLUSTALW对输入序列的格式比较灵活，输出格式也可以选择。

CLUSTALW网址：http：//www.ebi.ac.uk/clustalw下载网址：ftp：//ftp.ebi.ac.uk/pub/software第34页，共58页，2023年，2月20日，星期三HFDfingerprint多序列比对结果第35页，共58页，2023年，2月20日，星期三第36页，共58页，2023年，2月20日，星期三第37页，共58页，2023年，2月20日，星期三多序列比对数据库二次数据库：Pfam、PRINTS数据库等。基于多序列比对的数据库搜索程序正在不断地开发。其中位点特异性BLAST(Position-SpecificIteratedBLAST,PSI-BLAST)PSI-BLAST将双序列比对和多序列比对结合在一起的数据库，它运行速度较快，但却有迭代算法本身固有的缺陷，有时会得到错误结果。第38页，共58页，2023年，2月20日，星期三核酸序列分析第39页，共58页，2023年，2月20日，星期三核酸序列的预测方法针对核酸序列的预测就是在核酸序列中寻找基因，找出基因的位置和功能位点的位置，以及标记已知的序列模式等过程。一般而言，在重复片段频繁出现的区域里，基因编码区和调控区不太可能出现；如果某段DNA片段的假想产物与某个已知的蛋白质或其他基因的产物具有较高序列相似性的话，那么这个DNA片段就非常可能属于外显子片段；在一段DNA序列上出现统计上的规律性，即所谓的“密码子偏好性”，也是说明这段DNA是蛋白质编码区的有力证据；其他的证据包括与“模板”序列的模式相匹配、简单序列模式如TATABox等相匹配等。第40页，共58页，2023年，2月20日，星期三（1）重复序列分析对于真核生物的核酸序列而言，在进行基因辨识之前都应该把简单的大量的重复序列标记出来并除去，因为很多情况下重复序列会对预测程序产生很大的扰乱，尤其是涉及数据库搜索的程序。常见的重复序列分析程序有CENSOR和RepeatMasker等，可以在Web界面上使用这些程序，或者用e－Inail来进行。如果有大量序列需要处理，可以使用XBIAST程序。经处理的序列中重复序列所在位置一律由“X”代替。第41页，共58页，2023年，2月20日，星期三CENSOR的网址：http：///CENSOR的e-mail服务地址：censor＠下载XBLAST的网址：ftp：///pub/jmc（2）数据库搜索把未知核酸序列作为查询序列，在数据库里搜索与之相似的已有序列是序列分析预测的有效手段，尤其是对于EST序列而言。第42页，共58页，2023年，2月20日，星期三（3）编码区统计特性分析统计获得的经验说明，DNA中密码子的使用频率不是平均分布的，某些密码子会以较高的频率使用而另一些则较少出现。这样就使得编码区的序列呈现出可察觉的统计特异性，即所谓的“密码子偏好性”。利用这一特性对未知序列进行统计学分析可以发现编码区的粗略位置。密码子使用数据库（Codonusagedatabase），网址为http://www.kazusa.or.jp/codon

这一类技术包括：双密码子计数（统计连续两个密码子的出现频率）；核苷酸周期性分析（分析同一个核苷酸在3，6，9，…位置上周期性出现的规律）；均一／复杂性分析（长同聚物的统计计数）；开放可读框架分析等。第43页，共58页，2023年，2月20日，星期三常见的编码区统计特性分析工具将多种统计分析技术组合起来，给出对编码区的综合判别。著名的程序有GRAIL和GenMed等，GRAIL提供了基于Web的服务。GRAIL的网址是：http：///Crail-1.3/第44页，共58页，2023年，2月20日，星期三（4）启动子分析有一些程序根据实验获得的转录因子结合特性来描述启动子的序列特征，并依次作为启动子预测的依据，但实际的效果并不十分理想，遗漏和假阳性都比较严重。（5）内含子／外显子剪接位点常见的基因识别工具很多都包含了剪接位点识别功能，独立的剪接位点识别工具有NetGene等。NetGene服务器的e-mail地址：netgene＠cbs.dtu.dk。第45页，共58页，2023年，2月20日，星期三（6）翻译起始位点和终止信号对于真核生物，如果已知转录起始点，并且没有内含子打断5‘翻译区的话，“Kozak规则”可以在大多数情况下定位起始密码子。原核生物一般没有剪接过程，但在开放阅读框中找正确的起始密码子仍很困难。对于原核生物，关键是核糖体结合点的定位。，PolyA和翻译终止信号不象起始信号那么重要，但也可以辅助划分基因的范围。第46页，共58页，2023年，2月20日，星期三（7）tRNA基因识别tRNAscan－SE工具中综合了多个识别和分析程序，通过分析启动子组件的保守序列模式、tRNA二级结构的分析、转录控制组件分析和除去绝大多数假阳性的筛选过程，据称能识别99％的真tRNA基因。tRNAscan－SE的网址是：

http：//www.G/eddy/tRNAscan-SE/第47页，共58页，2023年，2月20日，星期三基因组序列信息分析DNA序列自身编码特征的分析是基因组信息学研究的基础，特别是随着大规模测序的日益增加，它的每一个环节都与信息分析紧密相关。到1998年底在人类的约10万个基因中有3万多个已被发现，尚有约7万个未被发现。EST序列到1999年12月已搜集了约200万条，它大约覆盖了人类基因的90％，1998年起，国际上又开展了以EST为主发现新SNPs的研究。因此利用EST数据库发现新基因、新SNPs以及各种功能位点是近几年的重要研究方向。第48页，共58页，2023年，2月20日，星期三5．1基因组序列分析工具（1）Wisconsin软件包（GCG）GeneticsComputerGroup公司开发的Wisconsin软件包，是一组综合性的序列分析程序，使用公用的核酸和蛋白质数据库。SeqLab是其图形用户界面（GUI），通过它可以使用所有Wisconsin软件包中的程序及其支持的数据库。GCG的主页是http：//www．gcg．com第49页，共58页，2023年，2月20日，星期三Wisconsin软件包由120多个独立的程序组成，每个程序进行一项单一的分析任务。GCG支持两种核酸数据库（GenBank数据库，简化版的EMBL核酸序列数据库）和三种蛋白质数据库（PIR，SWISS－PROT，SP－TrEMBL）。这些数据库既有GCG格式的（供大多数Wisconsin软件包程序使用），也有BLAST格式的（供BLAST数据库搜索程序使用）。同时还提供了用于LookUp程序以及数据库参考搜索的索引。第50页，共58页，2023年，2月20日，星期三

SeqLab可以解决的部分序列分析问题：①在两条mRNA中寻找开放阅读框架，翻译并对比mRNA与蛋白质序列；②通过参考搜索数据库中的相关条目并进行对比；③用查询序列搜索数据库，将找到的条目与查询序列进行对比并产生系统进化树；④拼接交叠序列片段产生一连续序列，寻找并翻译这一序列的编码区域并在数据库中搜索相似序列；⑤对比相关的蛋白质序列，计算对比结果的共有序列，据此搜索已知的蛋白质模式；⑥使用Profile进行相似性搜索并对比相关序列。第51页，共58页，2023年，2月20日，星期三（2）ACEDBACEDB是一种被广泛应用的管理和提供基因组数据的工具组，适用于许多动物和植物的基因组计划。该软件是免费的。数据库以丰富的图形界面提供信息，包括有具体显示的基因图谱，物理图谱，新陈代谢的途径和序列等。数据使用大家熟悉的类别进行组织，如相关的文献、基