【生物信息学】考虑仿射空位罚分的序列比对以及如何计算N-W算法的时间复杂度 | 学习课

导读

生物信息学是一门强大的新技术，是用来分析、存储、搜索海量生物医学数据的信息技术和计算技术。另一方面，生物信息学是一种研究生命科学问题的新方法、新思路，是一种从全基因组出发、从系统水平出发、基于数据整合，提出新假说、发现新规律的研究方法。

联川生物正在开展全员学习的生物信息学系列视频课程是由北京大学魏丽萍、高歌等教授主讲的“生物信息学：导论与方法课程”，几位教授通过14周的课程，系统地讲授生物信息学主要概念及方法，以及如何应用生物信息学手段解决生命科学问题。课程内容从基础的序列比对开始，循序渐进，围绕深度测序数据分析、计算基因组学、分子通路鉴定等当前研究的前沿热点内容进行介绍与讨论。

联川的小伙们想通过本次的全员学习，不断提升自己的知识水平。小编想来，这次学习的内容来自北大知名教授，关注我们的小伙伴们也能一起学习、进步，就将视频课程内容整理好分享给大家，与大家一起学习、一起进步，一起探讨生物信息学的相关知识。大家也可以在文末对照视频一起学习哦~

若有整理不当的地方，敬请大家留言交流呐~

往期回顾：

考虑仿射空位罚分的序列比对以及如何计算N-W算法的时间复杂度

(课程内容视频，请点击文末阅读原文)

•  课程内容一：空位罚分的改进

  •  前期回顾

   •  在序列比对概念中提到gap open和gap extending，但在前两节课程中我们把这两种状态的罚分设定为了一个值d。

  •  如何正确区分gap open和gap extending

   •  3种状态：一对残基之间可能的比对关系只有三种，我们分别将之称为三个不同的状态

     •  1. M表示两个残基彼此对上，但不一定相等；

     •  2. X表示序列X的残基对到了一个空位，或者说在序列X上发生了一次插入；

     •  3. Y则表示序列Y的残基对到了一个空位，或者说在序列Y上发生了一次插入。

    •  有限状态机 Finite State Automation, FSA

     •  概念：其在任意时刻都处于有限状态集合中的某一状态。当其获得一个输入字符时，将从当前状态转换到另一个状态，或者仍然保持在当前状态。任何一个FSM都可以用状态转换图来描述，图中的节点表示FSM中的一个状态，有向加权边表示输入字符时状态的变化。如果图中不存在与当前状态与输入字符对应的有向边，则FSM将进入“消亡状态(Doom State)”，此后FSM将一直保持“消亡状态”。

      •  在序列比对中的应用

        •  通过FSA，将序列比对描述为在不同状态之间的转移

         •  1. 从M到X或Y的转移对应一次gap open；

         •  2. 从X和Y到自身的转移对应于gap extending；

          •  3. 从M到自身的转移则对应为无空位情况下比对的延伸

      •  相应的动态规划迭代公式

         •  1. M(i,j)表示在Xi比对到Yj，即两个残基对在了一起的时候，第一条序列X从第1位到第i位、第二条序列Y从第1位到第j位最好的比对分数；

        •  2. X(i,j)和Y(i,j)则分别表示在Xi或Yj残基比对到空位时，序列X从第1位到第i位、序列Y从第1位到第j位最好的比对分数。

•  课程内容二：全局比对算法的时间复杂性

 •  优点：Needleman-Wunsch算法将时间代价由穷举法的指数时间下降到了平方时间， 有效降低了时间复杂度。

课程内容就介绍完了，本系列课程均是整理自视频内容，大家也可以在文末对照视频一起学习哦~

相关阅读