讲师：庞老师 资深生物信息分析工程师
目录
1、序列比对相关概念
2、序列比对算法
——点阵法
序列比对又称序列重排或对准,根据进行比对的生物序列数目序列比对可分为双序列比对和多序列比对。
双序列比对
双序列的比对有比较成熟的动态规划算法,以及在此基础上提出的 FASTA 和 BALST算法。
(1)FASTA 算法。
1988 年由 Pearson 和 lipman提出了 FASTA算法,它是将动态规划中要考察的矩阵进行了简化,并且保证在使用动态规划计算最优路径不会跑出候选区域,由于通常候选区域包含的元素远小于整个矩阵元素的数目,因此这种简化极大的提升了计算速度。使用候选区域是 FASTA 算法的关键环节,算法过程简单描述为:首先,需找待查序列与已知序列长度为 k 的公共子串,命名为热点区域;第二,延长热点区域,形成更长的部分比对区域;第三,综合第二步的比对区域,获得一个得分更高的比对;最后,基于上述的比对片段,寻找另一个备选的比对。 在 FASTA 算法中,只有得分靠前的少量数据库序列,以及这些序列上的部分区域才会实施进一步的算法处理,因此,其比对速度的是非常快的,由于其是一种近似寻优的算法,其缺陷是结果的最优比对无法保证。
(2)BLAST 算法。
1990 年,Altschul等人提出了 BLAST 算法,它是一种利用启发式搜索比较序列的近似算法。BLAST 算法包括搜索算法和搜索结果的统计学评估两个组成部分,简要的介绍一下搜索算法的三个步骤:第一步,寻找查询序列与靶序列之间长度为 k 的匹配片段;第二步,筛选相距较远的匹配片段;第三步,向两端延长匹配片段,形成更长的比对区域,在延长过程中,若得分超过某个阈值,则称这些区域为高得分区域,所得的高得分区域按降序排列后作为算法的输出。 BLAST 算法包含五个程序和若干个相应的数据库,分别针对不同的目的序列和搜索的数据库类型。其中进行核酸-蛋白质搜索比对时,根据中心法则原理,可将核酸序列转换成蛋白质序列,然后进行蛋白质数据库的搜索。
