序列比对（25）编辑距离

• 2019 年 10 月 4 日
• 筆記

本文介绍两个字符串的编辑距离并给出代码。

编辑距离

编辑距离的求解过程和全局比对是十分相似的（关于全局比对，可以参见前文《序列比对（一）全局比对Needleman-Wunsch算法》），都需要全部符号参与比对，都允许插入、缺失和错配。所以，编辑距离可以用动态规划算法求解，其迭代公式是：

效果如下：

编辑距离与最长公共子序列

在只允许插入和缺失而不允许错配的情况下，两个字符串的编辑距离可以通过最长公共子序列的长度（关于最长公共子序列，可以参看前文《序列比对（24）最长公共子序列》）间接算出来。

解编辑距离的代码

#include <stdio.h>  #include <stdlib.h>  #include <string.h>  #define MAXSEQ 1000  #define GAP_CHAR '-'  #define min(a, b) ((a) < (b) ? (a) : (b))  #define diff(a, b) ((a) == (b) ? 0 : 1)    struct Unit {      int W1;   // 是否往上回溯一格      int W2;   // 是否往左上回溯一格      int W3;   // 是否往左回溯一格      int M;      // 得分矩阵第(i, j)这个单元的分值，即序列s(1,...,i)与序列r(1,...,j)比对的最低得分  };  typedef struct Unit *pUnit;    void strUpper(char *s);  void printAlign(pUnit** a, const int i, const int j, char* s, char* r, char* saln, char* raln, int n);  void align(char *s, char *r);    int main() {      char s[MAXSEQ];      char r[MAXSEQ];      printf("The 1st seq: ");      scanf("%s", s);      printf("The 2nd seq: ");      scanf("%s", r);      align(s, r);      return 0;  }    void strUpper(char *s) {      while (*s != '