生物信息学第2章.

人民卫生出版社8年制及7年制临床医学等专业用《生物信息学》第二章双序列比对PairwiseSequenceAlignment河北大学刘建国闫蓬勃第一节引言同源（homology）-具有共同的祖先垂直同源（ortholog）水平同源（paralog）相似（similarity）同源序列一般是相似的，相似序列不一定是同源的通过点矩阵进行序列比较编辑距离（editdistance)相似性得分第二节替换记分矩阵（1）核酸打分矩阵设DNA序列所用的字母表为={A，C，G，T}a.等价矩阵(unitarymatrix)b.BLAST矩阵c.转换-颠换矩阵（transition-transversionmatrix）（嘌呤：腺嘌呤A，鸟嘌呤G；嘧啶：胞嘧啶C，胸腺嘧啶T）ATCGA1000T0100C0010G0001ATCGA5-4-4-4T-45-4-4C-4-45-4G-4-4-45ATCGA1-5-5-1T-51-1-5C-5-11-5G-1-5-51表3.1等价矩阵表表3.3转移矩阵表3.2BLAST矩阵（2）蛋白质打分矩阵（i）等价矩阵（ii）遗传密码矩阵（geneticcodematrix,GCM)（iii）疏水性矩阵（hydrophobicmatrix)（iv）PAM矩阵（pointacceptedmatrix,PAM）（v）BLOSUM矩阵（BLOckSUbstitutionMatrix，BLOSUM）jijiRij01其中Rij代表打分矩阵元素i、j分别代表字母表第i和第j个字符。遗传密码矩阵遗传密码矩阵通过计算一个氨基酸变成另一个氨基酸所需的密码子变化的数目而得到。通常为1或2，只有Met到Tyr为3。ASGLKVTPEDNIQRFYCHMWZBXA01122111112222222222222S10112211221121111221222G11022122112221221221222L21202121222111122111222K22220212121111222212122V12112022112122122212222T11221201221121222212222P11212210222211222122222E12121122012212222222122D12122122101222212122212N21221212210122212122212I21211112221021122212222Q22211221122201222122122R21111211222110221111222F21212122222122011222222Y21222222211222101132212C21122222222221110221222H22212221211211212022212M22211112222121232202222W21112222222221221220222Z22221222122212222222122B22222222211222212122212X22222222222222222222222GCM矩阵疏水矩阵RKDEBZSNQGXTHACMPVLIYFWR1010998866655555433333210K1010998866655555433333210D9910108876665555544433321E9910108876665555544433321B8888101088887777666555443Z8888101088887777666555443S667788101010109999887777664N666688101010109999888777664Q666688101010109999888777664G556688101010109999888877665X555577999910101010998888775T555577999910101010998888775H555577999910101010999888775A555577999910101010999888775C4455668888999910109999885M334466888899991010101099887P33446678888899910101099987V3344557778888891010101010987L33335577778888999101010998I33335577778888999101010998Y2233446666777788999910108F1122446666777788889910109W001133444555556777888910PAM&BLOSOM这类矩阵列出同源蛋白质在进化过程中氨基酸变化的可能性。这类矩阵是基于进化原理的证据：编码相同蛋白质的基因随着进化发生分歧，相似度降低。科学用得多PAM矩阵（pointacceptedmutaion）•基于氨基酸进化的点突变模型如果两种氨基酸替换频繁，说明自然界接受这种替换，那么这对氨基酸替换得分就高•一个PAM就是一个进化的变异单位,即1%的氨基酸改变但这并不意味100次PAM后，每个氨基酸都发生变化，因为其中一些位置可能会经过多次突变，甚至可能会变回到原来的氨基酸。PAM矩阵的制作步骤•构建序列相似（大于85％）的比对•计算氨基酸j的相对突变率mj（j被其他氨基酸替换的次数）•针对每个氨基酸对i和j,计算j被i替换次数•替换次数除以相对突变率（mj）•利用每个氨基酸出现的频度对j进行标准化•取常用对数，得到PAM-1(i,j)•将PAM-1自乘N次，可以得到PAM-nPAMMatricesMutationsacceptedbynaturalselectionConstructingPAMMatrix:TrainingDataPAM:PhylogeneticTreePAM:AcceptedPointMutationMutabilityofResiduejTotalMutationRateisthetotalmutationrateofallaminoacidsNormalizeTotalMutationRateto1%Thisdefinesanevolutionaryperiod:theperiodduringwhichthe1%ofallsequencesaremutated(acceptedofcourse)MutationProbabilityMatrixNormalizedSuchthattheTotalMutationRateis1%MutationProbabilityMatrix(transposed)M*10000elementsareshownmultipliedby10,000From:~opperd/private/pam1.htmlPAM-250PAM60—60%,PAM80—50%,PAM120—40%PAM-250matrixprovidesabetterscoringalignmentthanlower-numberedPAMmatricesforproteinsof14-27%similarityPAMMatrix:AssumptionsPAM=%AcceptedMutations:1500changesin71groups85%similarityBLOSUM=BlocksSubstitutionMatrix:2000“blocks”from500familiesTwoclassesofwidelyusedproteinscoringmatricesBLOSUM62ChoiceofScoringMatrix针对不同的进化距离采用PAM矩阵序列相似度=40%50%60%|||打分矩阵=PAM120PAM80PAM60PAM250→14%-27%PAM矩阵与BLOSUM矩阵的比较第三节双序列比对算法序列的两两比对（PairwiseSequenceAlignment）按字符位置重组两个序列，使得两个序列接近一样的长度序列两两比对基本算法直接方法——生成两个序列所有可能的比对，分别计算代价函数，然后挑选一个代价最小的比对作为最终结果，需要计算2300次——天文数字ATTC………CGAAGAAGTC………GAAGGT假设比较300个氨基酸长度的两条序列动态规划方法DynamicProgramming起点终点ATTC………CGAAGAAGTC………GAAGGTATTC………CGAAGAGTC………GAAGGAT+（1）ATTC………CGAAGAAGTC………GAAGG-T+（2）ATTC………CGAAGAGTC………GAAGGTA-+（3）最短路经问题起点终点C1C2W1W2路径1：C1+w1？路径2：C2+w2？取最小值！算法求解:从起点到终点逐层计算计算过程：计算过程：•按行计算•其他方式计算过程：（3）求最佳路径算法分析：数据结构di,j空间复杂度：O(mn)时间复杂度：O(mn)由于在所考虑的子问题空间中，总共有θ(mn)个不同的子问题，因此，用动态规划算法自底向上地计算最优值能提高算法的效率。矩阵赋值算法fori=0tolength(A)F(i,0)←0forj=0tolength(B)F(0,j)←0fori=1tolength(A)forj=1tolength(B){Choice1←F(i-1,j-1)+S(A(i),B(j))Choice2←F(i-1,j)+dChoice3←F(i,j-1)+dF(i,j)←max(Choice1,Choice2,Choice3)}算法程序反向构造匹配序列AlignmentA←AlignmentB←i←length(A)j←length(B)while(i0andj0){Score←F(i,j)ScoreDiag←F(i-1,j-1)ScoreUp←F(i,j-1)ScoreLeft←F(i-1,j)if(Score==ScoreDiag+S(A(i-1),B(j-1))){AlignmentA←A(i-1)+AlignmentAAlignmentB←B(j-1)+AlignmentBi←i-1j←j-1}elseif(Score==ScoreLeft+d){AlignmentA←A(i-1)+AlignmentAAlignmentB←-+AlignmentBi←i-1}otherwise(Score==ScoreUp+d){AlignmentA←-+AlignmentAAlignmentB←B(j-1)+AlignmentBj←j-1}}子序列与完整序列的比对----AGCT----ATGCAGCTGCTT目标：使S(s,i:t:j)最大序列S:序列t:ij不计前缀0:t:i的得分,也不计删除后缀的j+1:t:|t|得分不计删除后缀的j+1:t:|t|得分——处理最后一行)::,::(),()::,::(),()::,::(max)::,::()1(000)1(0)1(0)1(000jmmjmjmjmjmtsSsptsStsptsStsS+p(-,tj)不计前缀0:t:i的得分——处理第一行tsACACACTA000000000C-101010100A-200212110C-3-11132321A-4-202244440)::,::(000itsS最后一行不计代价子序列s在全序列t的后面出现时不会被罚分影响三、比对的统计学显著性（1）典型方法：将两条待比较的序列分别随机打乱使用相同的程序与打分函数（或打分矩阵）进行比对计算这些随机序列的相似性得分重复这一过程（50～100次）用和分别表示其平均值与标准差。设原来两条序列的比对得分为x，利用下式计算大于或等于x的比对得分概率：z=(x-)/根据z值判断两个序列相似得分的显著性，当z值是3.1、4.3、5.2时，x出现的概率为1