【5.1】基本序列算法

序列算法:为研究生物序列而开发出的计算复杂度尽可能低的算法。

比如:如何从序列中快速准确的找到重复序列

生物序列:包括核酸序列,蛋白质序列或其他由生物问题转化而来的数字串或字符串。

一、构建后缀树

  • 最后一个字符 后面还要加上 一个$,表示 结尾。
  • 序列本身就是自己的一个子序列
  • 后缀2= S2,S3,…,S10
  • 后缀3= S3,S4,…,S10
  • 后缀i= Si,Si+1,…,S10
  • 后缀$是序列 S最短的一个 后缀。

二、后缀树的作用

$的作用:如果某一个后缀是另一个后缀的 前缀,那么需要用$标识出一个独立的叶片。

三、最高分-子序列

生物学的应用

四、算法复杂度

参考资料:

山东大学 生物信息学课题组荣誉出品 http://www.crc.sdu.edu.cn/bioinfo 巩晶老师课件

个人公众号,比较懒,很少更新,可以在上面提问题:

更多精彩,请移步公众号阅读:

Sam avatar
About Sam
专注生物信息 专注转化医学