【5.1】基本序列算法

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

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

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

一、构建后缀树

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

二、后缀树的作用

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

三、最高分-子序列

生物学的应用

四、算法复杂度

参考资料：

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