生物信学第三章序列比对-课件

生物信息学第三章序列比对为什么要序列比对？寻找进化过程中的同源序列;基于同源物鉴定的功能预测;基本假设：序列的保守性功能的保守性注意：1.蛋白质一般在三级结构的层面上执行功能；2.蛋白质序列的保守性决定于其编码DNA的保守性；通常本章内容提要第一节：数学基础：概率及概率模型第二节：双序列比对算法的介绍Dotmatrix动态规划算法(Needleman-Wunsch,Smith-Waterman算法)

FASTA和BLAST算法第三节：打分矩阵及其含义第四节：多序列比对第一节序列比对的数学基础排列组合从N个物品中取出k个物品的排列数：从N个物品中取出k个物品的组合数：概率模型概率模型:一个能够通过不同的概率产生不同结果的模型。概率模型可以模拟或者仿真某一类型的所有事件，并且对每个事件赋予一个概率。色子模型：一个色子存在6个概率值：p1,p2,…,p6，其中，掷出i的概率为pi(i=1,2,…,6)。因此：pi≥0，且考虑三次连续的掷色子，结果为[1，6，3]，则总概率为：p1p6p3概率分布考虑连续变量x，例如：物体的重量。则当重量确切为1公斤时的概率，为0。变量的区间：P(x0≤x≤x1)

当区间无限小->0时，上式：P(x-δx/2

≤x≤x+δx/2

)=f(x)δx f(x)称为概率密度函数因此：且二项分布1.事件只有两种可能出现的结果。例如掷硬币，正面记为“1”，反面记为“0”。2.则掷硬币N次，有k次是1的概率为：二项分布的期望值与标准方差期望值E(x)=μ方差VarX=σ2泊松分布

(Poissondistribution)1.稀有事件发生的概率：在一个连续的时间或空间中，稀有离散变量出现的概率2.N->∞,E(x)=μe=2.71828…泊松分布与二项分布的近似对于大的N及小的p值的二项分布，能够相当准确地用一个参数为μ=Np的泊松分布近似。当实验次数很多而概率很小时：二项分布~泊松分布例1：鸟枪法的覆盖率假设：需要测序的BAC长度200kbp;总共测序的序列数量：N;每次测序：500bp；每次测序的覆盖率p：500/200kbp=0.0025因此：每个点平均覆盖到的次数:μ=N*pk:测序能够覆盖到点X的次数。鸟枪法：覆盖率点X被覆盖k次的概率：(二项分布~泊松分布)当点X一次都不被覆盖时，k=0;此时的概率为：覆盖率vs.准确性例2：泊松分布Prof.Gene发现一种序列上的调控信号，在人的基因组上平均每500kbp一个。那么，随机给一条1mbp的序列，在上面发现5个这样的信号，完全是随机产生的概率是多少？本例中，E(x)=μ=2(1mbp/500kbp)统计显著性：p-value<0.05超几何分布与二项式分布的区别：不放回抽样。例：有N个球，其中红球M个，白球N-M个，每次拿出一个球再放回，总共n次，其中有m个球是红球的概率为(二项式分布)：p=M/N超几何分布(2)上例改为：有N个球，其中红球M个，白球N-M个，每次拿出一个球不放回，总共n次，其中有m个球是红球的概率为：并且，0≤m≤M<N超几何分布右尾概率上例再改为：有N个球，其中红球M个，白球N-M个，每次拿出一个球不放回，总共n次，其中至少有m个球是红球的概率为：并且，0≤m≤M<N超几何分布左尾概率上例再改为：有N个球，其中红球M个，白球N-M个，每次拿出一个球不放回，总共n次，其中最多有m个球是红球的概率为：并且，0≤m≤M<N超几何分布双尾概率所有出现概率<=观察表概率的概率之和Fisher'sExactTest超几何分布的精确概率计算。前提是固定边际分布，即a+b、c+d、a+c与b+d的值不变。RAFisher,1935年文章示例：猜测先放的饮料牛奶茶合计实际先放的饮料牛奶a=3b=1a+b=4茶c=1d=3c+d=4合计a+c=4b+d=4n=8Fisher'sExactTest

计算公式：=统计显著性

假设检验中的P值(Pvalue)Pvalue：一种在原假设为真的前提下出现观察样本以及更极端情况的概率。显著性水平A：认为预先设定的显著性水平阈值，P<A为显著。一般以P<0.05为显著，P<0.01为非常显著，其含义是样本间的差异由抽样误差所致的概率小于0.05或0.01。假设检验本例中，零假设H0：该女同事只是随便乱猜答案；备择假设H1：该女同事所言不虚；

Pvalue计算：

P(a=3|a+b=c+d=a+c=b+d=4)=0.229P(a=4|a+b=c+d=a+c=b+d=4)=0.014例3：超几何分布Prof.Gene从人的26873个蛋白质中预测了2264个能结合某类金属离子X。现已知，人的26873个蛋白质中有421个蛋白质具有某种功能结构域D，而在预测的2264个X金属蛋白中，有94个具有结构域D。问：结构域D在2264个X金属蛋白中是显著出现，显著不出现，还是随机出现？例3：超几何分布问题转化：在26873个蛋白质的体系中，取出2264个蛋白质，其中至少有94个蛋白质具有功能结构域D的概率是多少？N=26873;n=2264;M=421;m=94;例3：超几何分布非X金属蛋白X金属蛋白合计不含结构域DN-M+m-nM-mN-n含结构域Dn-mmn合计N-MMN例3：超几何分布a+b+c+d=26873c+d=2264b+d=421d=94langsrud/fisher.htm第二节，双序列比对算法1.DotMatrix，点阵法2.动态规划算法：Global:Needleman-WunschLocal:Smith-Waterman3.Wordork-tuple算法：FASTA,BLAST1.点阵法1970年，Gibbs&McIntyre；寻找两条序列间所有可能的比对；发现蛋白质或者DNA序列上正向或者反向的重复；发现RNA上可能存在的互补区域。工具：myhits.isb-sib.ch/cgi-bin/dotlet/molkit/dnadot/点阵法：自身的比对AKGFKCADEA100000100K10010000G1000000F100000K10000C1000A100D10E1点阵法：重复序列AKGFDKGFEA100000000K10001000G1000100F100010D10000K11000G1100F110E1点阵法：反向重复/回文AUGCACGUCA100010000U10000010G1000100C101000A10000C11001G1100U110C1点阵法：不同序列的比对PKDFCKALVP100000000K10001000F0100000T00000K11000A100I00V011:PKDFCKALV2:PK-FTKAIVSeq1Seq2点阵法的序列比对Sequence1#1nSequence2#1m“-”Insertion“-”Insertion计算效率用CPU的计算时间和内存占用量来衡量；对于需要解决的问题，其单位数量n在某算法下运算的基本操作重复执行次数表示为f(n)；时间复杂度:T(n)=O(f(n))；如果需要解决的问题的大小与单位数量n的平方成正比，则O(n2)对于算法来说：O(1)>O(log(n))>O(n)>O(n2)>O(an)>O(n!)NP问题1.一般的，O(nk),当k≤3时，为多项式时间，较为容易处理。2.当O(an)，则难以处理。3.NP完全问题（NPC）：无法找到能够在多项式时间复杂度内解决方法的问题；4.近似算法/优化算法，求近似解。P/NP问题-千禧年大奖难题之一1900年，德国数学家DavidHilbert提出的23个历史性数学难题。千禧年大奖难题美国克雷数学研究所（ClayMathematicsInstitute,CMI）于2000年5月公布七个世界数学难题。千禧年大奖难题P/NP问题：P=NP？霍奇猜想庞加莱猜想（已证明）黎曼猜想杨-米尔斯存在性与质量间隙纳维-斯托克斯存在性与光滑性贝赫和斯维讷通-戴尔猜想P/NP/NPC问题P问题：PolynomialProblems可以在多项式(polynomial)时间内解决的问题;NP:“Non-deterministicPolynomial”,并非

“Non-Polynomial”

可以在多项式的时间里验证一个解的问题;NPC:NP-complete2.动态规划算法1.打分模型、替代矩阵以及空位罚分。2.比对算法：递归及动态规划算法；3.全局优化比对：Needleman-Wunsch4.局部优化比对：Smith-Waterman5.工具资源：.au/course/lectures2019/Likic.pdfsnippets.dzone/posts/show/2199/NW-align/jaligner.sourceforge/打分模型1.字符相同：identity2.字符替代：similarity，相似性，氨基酸/碱基之间的替代和突变3.插入和缺失4.空位罚分BLOSUM62替代矩阵空位罚分1.线性罚分：d,每次罚分的分数；g，空位数2.修正的罚分：d,第一次罚分的分数；g，空位数；e,修正后的参数递归和动态规划算法两条序列的比较，无空位：时间复杂度为O(n2);

两条序列比对，允许空位，时间复杂度为：因此，有空位的双序列比对，时间复杂度为：O(22n)，指数增加，NPC问题！递归和动态规划算法(2)

数学上保证提供最优解。动态规划算法：比较所有可能的字符对，考虑匹配、错配以及空位罚分，并且将比对次数控制在多项式时间内。替代矩阵：BLOSUM62，空位罚分：11延伸的空位罚分：1(BLAST工具)例：全局比对序列1：VDS–CY序列2：VESLCY替代矩阵中的分数：424-1197两序列比对的总分：Score=Σ(AApairscores)–gappenalty=15动态规划算法：全局比对GapVDSCYGap01gap2gap…V1gapE2gapS…LCY本例：线性罚分全局比对(2)GapVDSCYGap0-11-22-33-44-55V-11SijE-22S-33L-44C-55Y-66要求解Sij的分数，我们必须先知道Si-1,j-1,Si-1,j,以及Si,j-1的分数，这种方法叫做递归算法；采用这种方法，可以把大的问题分割成小的问题逐一解决，即动态规划算法；需要存储如何得到Sij分数的过程。全局比对(3)GapVDSCYGap0-11-22-33-44-55V-11SijE-22S-33L-44C-55Y-66ijNeedleman-Wunsch算法；Sij=maxofSi-1,j-1+σ(xi,yj)

Si-1,j-d(从左到右)Si,j-1-d(从上到下)全局比对(4)GapVDSCYGap0-11-22-33-44-55V-11SijE-22S-33L-44C-55Y-66ij4-11-11Needleman-Wunsch算法；Sij=maxofSi-1,j-1+σ(xi,yj)

Si-1,j-d(从左到右)Si,j-1-d(从上到下)全局比对(5)GapVDSCYGap0-11-22-33-44-55V-114E-22S-33L-44C-55Y-664-11-11全局比对(6)GapVDSCYGap0-11-22-33-44-55V-114SijE-22S-33L-44C-55Y-66-3-11-11Needleman-Wunsch算法；Sij=maxofSi-1,j-1+σ(xi,yj)

Si-1,j-d(从左到右)Si,j-1-d(从上到下)全局比对(7)GapVDSCYGap0-11-22-33-44-55V-114-7E-22S-33L-44C-55Y-66-3-11-11全局比对(8)GapVDSCYGap0-11-22-33-44-55V-114-7-18-29-40E-22-76-5-16-27S-33-18-510-1-12L-44-29-16-19-3C-55-40-27-1287Y-66-51-38-23-31542回溯：比对结果GapVDSCYGap0-11-22-33-44-55V-114-7-18-29-40E-22-76-5-16-27S-33-18-510-1-12L-44-29-16-19-3C-55-40-27-1287Y-66-51-38-23-31542VDS–CYVESLCY局部优化比对下例：局部优化打分两条序列如下：LDS–CHGESLCK目标：使用局部优化算法寻找比对的结果局部优化比对(2)1.Smith-Waterman算法；2.时间复杂度O(n2)；3.Sij=maxof0 Si-1,j-1+σ(xi,yj) Si-1,j-d(从左到右) Si,j-1-d(从上到下)本例中：gap:12，线性罚分模型。局部优化比对(3)GapLDSCHGap00