2024年6月14日发(作者：)

序列比对（Sequence Alignments）总结

Stefan Grünewald （贾壮总结）

1. 序列比对分类

序列比对用于比对基因碱基序列或蛋白质的氨基酸序列大致可以分成三类：

①全局比对（Global alignment）研究两个给定的序列A和B的同源性。

②半全局比对（Semi-global alignment）搜索序列B是否在基因组A中。

③局部比对（Local alignment）寻找序列A和B同源性的区域（domain），使用的最为广

泛，因为多数情况下是A的一个domain与B的某个domain存在较高的同源性，并不是A

和B整个序列，著名的BLAST（Basic Local Alignment Search Tool）算法就是一种局部

比对算法。

这三种序列比对方法使用了极为相似的算法，参考往年的考试类型是要求会手算的，下面

会详细讲解；另外还存在一种叫Motif Finding的方法，使用了完全不同的算法，实现起来

也较为繁琐，会在最后简单讲解。

2. 序列比对基本概念

序列比对使用了动态规划算法，基本理念是每一步最优，直到序列比对结束得到全局最

优，再回溯（Backtrack）得到最优的路径。它的基本算法见式1，具体实现是在一张二维

表中进行的（图1）。

$

D(i

−

1,j

−

1)

+δ

(A

i

,B

j

)

!

D(i,j)

=

max

#

D(i

−

1,j)

+

g

B

!

D(i,j

−

1)

+

g

A

"

D就是图1中的二维表格，存放的是从开始到比对进行到