生物信息学第2章

1、人民卫生出版社8年制及7年制临床医学等专业用生物信息学表3.1 等价矩阵表表3.3 转移矩阵表3.2 BLAST矩阵jijiRij01其中Rij代表打分矩阵元素i、j分别代表字母表第i和第j个字符。A S G L K V T P E D N I Q R F Y C H M W Z B X A 01122111112222222222222S 10112211221121111221222G 11022122112221221221222L 21202121222111122111222K 22220212121111222212122V 12112022112122122212222T 112

2、21201221121222212222P 11212210222211222122222E 12121122012212222222122D 12122122101222212122212N 21221212210122212122212I 21211112221021122212222Q 22211221122201222122122R 21111211222110221111222F 21212122222122011222222Y 21222222211222101132212C 21122222222221110221222H 22212221211211212022212M 222

3、11112222121232202222W 21112222222221221220222Z 22221222122212222222122B 22222222211222212122212X 22222222222222222222222R K D E B Z S N Q G X T H A C M P V L I Y F W R 1010998866655555433333210K 1010998866655555433333210D 9910108876665555544433321E 9910108876665555544433321B 888810108888777766655544

4、3Z 8888101088887777666555443S 667788101010109999887777664N 666688101010109999888777664Q 666688101010109999888777664G 556688101010109999888877665X 555577999910101010998888775T 555577999910101010998888775H 555577999910101010999888775A 555577999910101010999888775C 4455668888999910109999885M 33446688889

5、9991010101099887P 33446678888899910101099987V 3344557778888891010101010987L 33335577778888999101010998I 33335577778888999101010998Y 2233446666777788999910108F 1122446666777788889910109W 001133444555556777888910PAM矩阵（矩阵（ point accepted mutaion） 基于氨基酸进化的点突变模型基于氨基酸进化的点突变模型 如果两种氨基酸替换频繁，说明自然界接受这种替换，那么这对氨

6、基酸替换得分就高 一个一个PAM就是一个进化的变异单位就是一个进化的变异单位, 即即1%的氨基酸改变的氨基酸改变但这并不意味但这并不意味100次次PAM后，每个氨基酸都发生变化，因为其中一些位置可能后，每个氨基酸都发生变化，因为其中一些位置可能会经过多次突变，甚至可能会变回到原来的氨基酸。会经过多次突变，甚至可能会变回到原来的氨基酸。PAM矩阵的制作步骤矩阵的制作步骤构建序列相似（大于构建序列相似（大于85）的比对）的比对计算氨基酸计算氨基酸 j 的相对的相对突变率突变率mj（j被其他氨基酸替换的次数）被其他氨基酸替换的次数）针对每个氨基酸对针对每个氨基酸对 i 和和 j , 计算计算 j 被

7、被 i 替换次数替换次数替换次数替换次数除以除以相对突变率相对突变率（mj）利用每个氨基酸出现的利用每个氨基酸出现的频度频度对对j 进行进行标准化标准化取常用对数取常用对数，得到，得到PAM-1(i, j)将将PAM-1自乘自乘N次次，可以得到，可以得到PAM-nTotal Mutation Rateis the total mutation rate of all amino acidsThis defines an evolutionary period: the period during which the 1% of all sequences are mutated (accept

8、ed of course)Mutation Probability Matrix Normalized Such that the Total Mutation Rate is 1%Mutation Probability Matrix (transposed) M*10000elements are shown multiplied by 10,000 From: http:/www.icp.ucl.ac.be/opperd/private/pam1.htmlPAM-250Two classes of widely used protein scoring matricesBLOSUM 62

9、Choice of Scoring Matrix针对不同的进化距离采用针对不同的进化距离采用PAM 矩阵矩阵序列相似度序列相似度 = 40% 50% 60% | | |打分矩阵打分矩阵 = PAM120 PAM80 PAM 60PAM250 14% - 27% 序列两两比对基本算法序列两两比对基本算法直接方法直接方法 生成两个序列所有可能的比对，分别计算生成两个序列所有可能的比对，分别计算代价函数，然后挑选一个代价函数，然后挑选一个代价最小代价最小的比对作为最终结果，的比对作为最终结果，需要计算需要计算 2300 次次天文数字天文数字ATTCCGAAGA AGTCGAAGGT假设比较300个氨

10、基酸长度的两条序列动态规划方法动态规划方法 Dynamic Programming起点起点终点终点ATTCCGAAGA AGTCGAAGGTATTCCGAAG AGTCGAAGGAT+（1）ATTCCGAAGA AGTCGAAGG-T+（2）ATTCCGAAG AGTCGAAGGTA-+（3）最短路经问题最短路经问题起点起点终点终点C1 C2 W1 W2路径1：C1 + w1 ？路径2：C2 + w2 ？ 取最小值！取最小值！算法求解算法求解: 从起点到终点逐层计算从起点到终点逐层计算计算过程：计算过程：计算过程：计算过程：按行计算按行计算其他方式其他方式计算过程：计算过程：（3）求最佳路径）

11、求最佳路径算法分析：算法分析：数据结构数据结构d i , j空间复杂度：空间复杂度：O (mn)时间复杂度：时间复杂度：O (mn)由于在所考虑的子问题空间中，总共有(mn)个不同的子问题，因此，用动态规划算法自底向上地计算最优值能提高算法的效率。 矩阵赋值算法矩阵赋值算法 forfor i=0 toto lengthlength(A) F(i,0) 0 forfor j=0 toto lengthlength(B) F(0,j) 0 forfor i=1 toto lengthlength(A) forfor j = 1 toto lengthlength(B) Choice1 F(i-1,

12、j-1) + S(A(i), B(j) Choice2 F(i-1, j) + d Choice3 F(i, j-1) + d F(i,j) maxmax(Choice1, Choice2, Choice3) 反向构造匹配序列反向构造匹配序列 AlignmentA AlignmentB i lengthlength(A) j lengthlength(B) whilewhile (i 0 andand j 0) Score F(i,j) ScoreDiag F(i - 1, j - 1) ScoreUp F(i, j - 1) ScoreLeft F(i - 1, j) ifif (Score

13、 = ScoreDiag + S(A(i-1), B(j-1) AlignmentA A(i-1) + AlignmentA AlignmentB B(j-1) + AlignmentB i i - 1 j j - 1 elseelse ifif (Score = ScoreLeft + d) AlignmentA A(i-1) + AlignmentA AlignmentB - + AlignmentB i i - 1 otherwiseotherwise (Score = ScoreUp + d) AlignmentA - + AlignmentA AlignmentB B(j-1) +

14、AlignmentB j j - 1 序列S:序列t: i j不计前缀0:t:i 的得分, 也不计删除后缀的j+1:t:|t|得分不计删除后缀的不计删除后缀的j+1:t:|t|得分得分 处理最后一行处理最后一行):,:(),():,:(),():,:(max):,:() 1(000) 1(0) 1(0) 1(000jmmjmjmjmjmtsSsptsStsptsStsS+ p ( -, tj )不计前缀不计前缀0 0:t:t:i i 的得分的得分处理第一行处理第一行0):,:(000itsS最后一行不计代价最后一行不计代价子序列s在全序列t的后面出现时不会被罚分影响数据库的搜索简数据库的搜索简

15、介介第四节 双序列比对工具 数据库查询为生物学研究提供了一个重要工具，在实际工作中经常使用。然而，在分子生物学研究中，对于新测定的碱基序列或由此翻译得到的氨基酸序列，往往需要通过数据库搜索，找出具有一定相似性的同源序列，以推测该未知序列可能属于哪个基因家族，具有哪些生物学功能。对于氨基酸序列来说，有可能找到已知三维结构的同源蛋白质而推测其可能的空间结构。因此，数据库搜索与数据库查询一样，是生物信息学研究中的一个重要工具。 数据库搜索的基础是序列的相似性比对，即双序列比对(pairwise alignment)。 新测定的、希望通过数据库搜索确定其性质或功能的序列称作检测序列(probe seq

16、uence)；通过数据库搜索得到的和检测序列具有一定相似性的序列称目标序列(subject sequence)。 为了确定检测序列和一个已知基因家族之间的进化关系，在通过数据库搜索得到某些相似序列后，还需要判断其序列相似性程度。如果检测序列和目标序列的相似性程度很低，还必须通过其他方法或实验手段才能确定其是否属于同一基因家族 。BLAST程序是目前最常用的基于局部相似性的数据库搜索程序，它们都基于查找完全匹配的短小序列片段，并将它们延伸得到较长的相似性匹配。它们的优势在于可以在普通的计算机系统上运行，而不必依赖计算机硬件系统而解决运行速度问题。BLAST数据库搜索策略数据库搜索策略 BLAST

17、仅通过部分而不是全部序列计算最适联配值赢得搜索速度 比对统计学意义的评价 E值值(E-Value)P值值(P-Value)(概率值概率值) BLAST程序中使用了E值而非P值，这主要是从直观和便于理解的角度考虑。比如E值等于5和10，总比P值等于0.993和0.99995更直观。但是当Egi|224983683|pdb|3GBN|B Chain B, Crystal Structure Of Fab Cr6261 In Complex With The 1918 H1n1 Influenza Virus HemagglutininGLFGAIAGFIEGGWTGMIDGWYGYHHQNEQGS

18、GYAADQKSTQNAIDGITNKVNSVIEKMNTQFTAVGKEFNNLERRIENLNKKVDDGFLDIWTYNAELLVLLENERTLDFHDSNVRNLYEKVKSQLKNNAKEIGNGCFEFYHKCDDACMESVRNGTYDYPKYSEESKLNREEIDGVSGR序列sp|P31025|LCN1_HUMAN Lipocalin-1 OS=Homo sapiens GN=LCN1 PE=1 SV=1MKPLLLAVSLGLIAALQAHHLLASDEEIQDVSGTWYLKAMTVDREFPEMNLESVTPMTLTTLEGGNLEAKVTMLISGRCQEVKAV

19、LEKTDEPGKYTADGGKHVAYIIRSHVKDHYIFYCEGELHGKPVRGVKLVGRDPKNNLEALEDFEKAAGARGLSTESILIPRQSETCSPGSDFastA简介简介 FastA算法是由Lipman和Pearson于1985年发表的（Lipman和Pearson，1985）。FastA的基本思路是识别与代查序列相匹配的很短的序列片段，称为k-tuple。 蛋白质序列数据库搜索时，短片段的长度一般是12个残基长；DNA序列数据库搜索时，通常采用稍大点的值，最多为6个碱基。通过比较两个序列中的短片段及其相对位置，可以构成一个动态规划矩阵的对角线方向上的一些匹配片段

20、。 FastA程序采用渐进（heuristic approach）算法将位于同一对角线上相互接近的短片段连接起来。也就是说，通过不匹配的残基将这些匹配残基片段连接起来，以便得到较长的相似性片段。这就意味着，FastA输出结果中允许出现不匹配残基。这和BLAST程序中的成对片段类似。如果匹配区域很多，FastA利用动态规划算法在这些匹配区域间插入空位。 由FastA搜索产生的典型输出结果的第一行列出程序名称和版本号，以及该程序发表的杂志。接下来列出所提交的序列，然后是所用参数和运行时间，紧跟这些一般信息的是数据库搜索结果。 首先列出搜索得到的目标序列简单说明，其数目可由用户定义。所列出的目标序列

21、的信息包括：序列所在数据库名称的缩写，目标序列的标识码、序列号和序列名等部分信息。括号中标明匹配部分的残基数。紧接着是由程序计算得到的初始化和优化后的分数值。最后一列是期望值即E值，用来判断比对结果的置信度。接近于0的E值表明两序列的匹配不大可能是由随机因素造成的。以两条氨基酸序列的比较为例介绍算法的基本思路，算法可以分为以两条氨基酸序列的比较为例介绍算法的基本思路，算法可以分为4步：步：第一步：第一步： FASTA首先找出进行比较的两条序列所有长度为k-tuple 的连续的一致序列片段。例如以下两条蛋白质序列： 设k-tuple =2，则序列2中有两个符合条件的片段(用下划线表示)，相对于序列1的偏移(offset)分别是4和1对于一对开始位置为(x1,x2)的一致片段，偏移定义为x1-x2。在上例中有两对(x1，x2)，即（5,1）和(5,4)。这种片段的一致性可以表示为对角线图，两条序列中的一对一致片段在图中表示为一段对角线。序列FLWRTW和STWKTWT比较形成的对角线图 对于图中每一条完整的对角线(即同一偏移)上的一致片段，如果片段间距小于用户界定的界限，则将片段连接起来作为一条一致片段。. 本例是两条非常短的氨基酸序列，在实际比较长的蛋白质序列或DNA序列时，对角线图如图A所示。 对这些片段