第三节 双序列比对算法

在生物信息学中，对各种生物大分子的序列进行分析是非常基本的工作。序列的测定和拼接、RNA和蛋白质的结构功能预测、种系树的构建等都需要对生物分子进行序列相似性的比较。处理子序列与完整序列（或短序列与长序列）的比对的一般过程是：设短序列a和长序列b，它们的长度分别为La和Lb，比对是在b序列中寻找La长度的a序列的过程。然后由位置（i，j）出发，反推比对路径，最终通过斜线（非空位）到达（0，j）。 ......