北京大学生物信息学学习(3动态规划进行2序列比对的原理 )
链接 https://www.bilibili.com/video/BV1by4y1k7rc?p=6
北京大学生物信息学公开课之动态规划进行2序列比对
掌握主流的生物信息学的原理，然后让生物信息学为你所用，，知其道用其妙
对当前流行的软件的分析
主要包括以下几方面
生物信息学分析
来自灵魂的拷问
1.生物学问题 软件需要解决的生物学问题和背景是什么??？
2.使用这种方法需要什么样的数据，需要哪些参数??
3.如何将生物学问题通过建模形成计算机能够解决的生物学模型??
4.模型的实现需要的算法??
比如序列比对分析
生物学问题
序列比对的重要性(主要基于的问题 ::: 1.相似的结构具有相似的功能，2.不同的物种中，相似的序列是构建演化关系的重要因素
那么经典的常用的动态规划进行序列比对的方法Needleman-Wunsch 算法
序列比对常见的网站https://www.ebi.ac.uk/Tools/psa/emboss_matcher/
比对结果的解读
比对的结果通过一个替换矩阵来分析
第5个位置S向T 的替换得到的矩阵的分数是1>0，在结果显示中是冒号：
而对于替换的结果是-1 的时候，在结果显示中是. 表示相似性较差。
每个氨基酸的比对是相互独立的
那么对于其中空位的部分，正在一条序列上的空位，另一条序列上就是插入
对于空位会产生罚分
最终的得分是是全部的惩罚分数之和。
利用动态规划进行全局比对
2条序列的比对
核苷酸的数目为n
那么所有比对的结果是在2n 个位置上放n个空位的组合
也即是2n 个数据里面选取n个的组合数
1个碱基序列比对的结果，比对到另一个核苷酸或者1个空位
因此总的比对分数等于当前每个残基比对的结果之和，因此序列比对的问题可以分解为
当前最好的比对结果加上后期比对最好的结果，也就是转化为动态规划的问题
动态规划进行全局的比对，理论公式全局最优解等于当前最优解+下一个比对的最优解
设置最初始的比对结果是F(0,0)=0
在本例中的惩罚分数是d=-5，不同的替代之间的结果是，同一替代是2分，A/C是-7，A/G是-5，A/T也是-7。
动态最优规划
在计算的过程中，每个格子只考虑它上方和左侧的分数来源，在所有的结果中，取最大的分数作为最终的分数，用于下一次的计算
举例子
动态规划矩阵
每个格子选取所有可能性中最大的分数，那么对于上述的矩阵，第一列和第一行的分数分别为-5，-10，-15，然后从左边和上边分别得到当前的分数，选取最大的作为最大的得分
最终得到的最优的比对结果
最后优AAG 和AGC 三个碱基的比对序列，得到的最优结果如上2个，最终的得分为-6。
生物信息学序列比对