2️⃣ 双序列比对(1)：算法及数据库
序列比对和序列特征分析总目录
包括DNA,RNA和蛋白组在内的生物序列（也就是一级结构）本质是固定的字母表中的字母组成的字符串，两条序列s和t的比对可以简单的解释为： s和t两条序列上下排列起来，在某些位置需要插入空位gap，然后依次比较它们在每个位置上字符的匹配情况，从而找出使这两条序列产生最大相似度得分的排列方式和空位插入方式。 注意，这其中有自身比对的问题。自身比对可以
- 寻找序列中的正向和反向重复序列
- 查找蛋白质的重复结构域
- 相同残基重复出现的低复杂区
- RNA二级结构中的互补区域
常用的算法有
1 最早的：点阵图法dotplot
- 网页版工具 Dotlet DNAdot 作者已经不再维护
- Mac DNA Strider
- Mac/Linux,Windows Dotter 和Dotter手册
2 最经典最精确的：动态规划算法
全局比对: 参与比对的两条序列里面的所有字符进行比对。 优点是非常精确 缺点是运行时间长，不适合数据量庞大的序列数据库搜索
3 目前大多数数据库搜索工具中使用的算法：BLAST算法(Basic local alignment search tool)
速度快，精确，所以常用。
注意：动态规划和BLAST适用于不同比对情况。前者适合较少量序列间比对，BLAST适合从一组大量序列中搜索与查询相似的序列
BLAST总体比对算法的思想是：首先通过完全匹配来查找序列，然后通过允许有误匹配的方式来扩展比对区域。具体来说，其基本要点是序列片段对segment pair的概念。序列片段对是指两个给定序列中的一对子序列，它们的长度相等，并且可以形成五孔维的完全匹配。BlAST首先找出查询序列和目标序列之间所有匹配程度（得分）超过一定阈值的序列片段对，然后对片段对根据给定的相似性阈值进行延伸，得到一定长度的相似性片段，最后给出高分值片段对（high-scoring pairs, HSPs）。
BLAST可以用来做什么
-1 推断和鉴定查询序列的功能 -2 指导实验设计论证该功能 -3 找到在模式生物中与查询序列相似的序列，进一步研究其功能 -4 在目标物种发行与查询序列相似的同原序列 -5 全基因组之间进行比较，识别不同生物体间的相似和差异 -6 用序列相似性推断两个或更多的基因或蛋白质之间的同源性和结构相似性 -7 识别一个蛋白中更多的保守区域，特别是有重要功能的区域识别 -8 基于同一个位点或区域的基础上比较和同源对照 -9序列相似性除非推荐进化距离或进化过程