生物信学第三章序列比对.pptVIP

* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * /NW-align/ * * * * * * * * * 期望值代表了随机变量的“平均”值。它是把每个可能取值乘以对应的概率，然后累加起来。 标准方差描述了随机变量中具有正概率值的分散性。所有可能的值离期望值的距离的平方，再乘以对应的概率。 * * * * * * * * * * * * * * * * * B2：抽样 B1：剩余 A2：阳性 A1：阴性 * * * * * 点阵法：重复序列 A K G F D K G F E A 1 0 0 0 0 0 0 0 0 K 1 0 0 0 1 0 0 0 G 1 0 0 0 1 0 0 F 1 0 0 0 1 0 D 1 0 0 0 0 K 1 1 0 0 0 G 1 1 0 0 F 1 1 0 E 1 点阵法：反向重复/回文 A U G C A C G U C A 1 0 0 0 1 0 0 0 0 U 1 0 0 0 0 0 1 0 G 1 0 0 0 1 0 0 C 1 0 1 0 0 0 A 1 0 0 0 0 C 1 1 0 0 1 G 1 1 0 0 U 1 1 0 C 1 点阵法：不同序列的比对 P K D F C K A L V P 1 0 0 0 0 0 0 0 0 K 1 0 0 0 1 0 0 0 F 0 1 0 0 0 0 0 T 0 0 0 0 0 K 1 1 0 0 0 A 1 0 0 I 0 0 V 0 1 1:PKDFCKALV 2:PK-FTKAIV Seq 1 Seq2 点阵法的序列比对 Sequence 1# 1 n Sequence 2# 1 m “-” 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年，德国数学家David Hilbert提出的23个历史性数学难题。 千禧年大奖难题美国克雷数学研究所（Clay Mathematics Institute,CMI）于2000年5月公布七个世界数学难题。 千禧年大奖难题 P/NP问题：P = NP ？ 霍奇猜想 庞加莱猜想（已证明） 黎曼猜想 杨-米尔斯存在性与质量间隙 纳维-斯托克斯存在性与光滑性 贝赫和斯维讷通-戴尔猜想 P/NP/NPC问题 P问题： Polynomial Problems 可以在多项式( polynomial )时间内解决的问题; NP: “Non-deterministic Polynomial”,并非 “Non-Polynomial” 可以在多项式的时间里验证一个解的问题; NPC: NP-complete 2. 动态规划算法 1. 打分模型、替代矩阵以及空位罚分。 2. 比对算法：递归及动态规划算法； 3. 全局优化比对：Needleman-Wunsch 4. 局部优化比对：Smith-Waterman 5. 工具资源： .au/course/lectures2005/Likic.pdf /posts/show/2199 /NW-align/ / 打分模型 1. 字符相同：identity 2. 字符替代：similarity，相似性，氨基酸/碱基之间的替代和突变 3. 插入和缺失 4. 空位罚分 BLOSUM62替代矩阵 空位罚分 1. 线性罚分：d, 每次罚分的分数；g，空位数 2. 修正的罚分：d, 第一次罚分的分数； g，空位数；e, 修正后的参数 递归和动态规划算法 两条序列的比较，无空位：时间复杂度为O(n2); 两条序列比对，允许空位，时间复杂度为： 因此，有空位的双序列比对，时间复杂度为：O(22n)，指数增加，NPC问题！ 递归和动态规划算法 (2) 数学上保证提供最优解。 动态规划算法：比较所有可能的字符对，考虑匹配、错配以及空位罚分，并且将比对次数控制在多项式时间内。 替代矩阵：BLOSUM62， 空位罚分：11 延伸的空位罚分：1 (BLAST工具) 例：全局比对