首先這些算法的主要目標是找到兩條DNA、RNA或蛋白質序列之間的相似性，以便進一步分析它們的功能、演化關係或可能的突變。在這篇文章中，我們將綜論一些常見的序列比對算法。

而生物學家會利用編輯距離，來衡量兩條DNA序列之間的相異程度。編輯距離越小，表示這兩條序列越相似，可能有相似的結構和功能。生物學家通常使用序列比對來衡量基因或蛋白質的相似性，並通過比對結果來推斷它們的演化關係或可能的功能。

編輯距離

當我們談論DNA序列的編輯距離時，我們通常考慮三種基本的編輯操作：取代、插入和刪除。讓我們以一個簡單的例子來演示編輯距離的計算。

假設我們有兩個DNA序列：

序列1： AGTCAAG 
序列2： AGGCTAG

我們希望計算出將序列1轉換成序列2所需的最小編輯操作數。

步驟1：建立編輯距離矩陣（矩陣的大小為(len(序列1) + 1) x (len(序列2) + 1)）：

   ""  A  G  G  C  T  A  G
""  0  1  2  3  4  5  6  7
A   1
G   2
T   3
C   4
A   5
A   6
G   7

步驟2：填充矩陣，計算每個單元格的值，以便找到最小的編輯距離。我們使用以下規則：

• 如果序列1的字符等於序列2的字符，則使用左上角的值（即不需要編輯操作）。
• 否則，取左、上和左上三個相鄰單元格的最小值，並加1。

      |   A   G   G   C   T   A   G
-------------------------------------
   |  0   1   2   3   4   5   6   7
A  |  1   0   1   2   3   4   5   6
G  |  2   1   0   1   2   3   4   5
T  |  3   2   1   1   2   2   3   4
C  |  4   3   2   2   1   2   3   4
A  |  5   4   3   3   2   2   2   3
A  |  6   5   4   4   3   3   2   3
G  |  7   6   5   4   4   4   3   2

一個簡單的編輯距離計算：

1. 開始比對兩個序列的第一個字母 "A"，它們相等，不需要操作。

2. 繼續比對第二個字母 "G"，它們相等，不需要操作。

3. 現在比對第三個字母，序列1中是 "T"，序列2中是 "G"，我們需要將 "T" 替換為 "G"，這是一個取代操作。
   現在的情況如下：
   序列1： AGGCAAG 序列2： AGGCTAG

4. 接下來，比對第四個字母 "C"，它們相等，不需要操作。

5. 接著比對第五個字母 "A"，它們相等，不需要操作。

6. 最後，比對第六個字母，序列1中是 "A"，序列2中是 "G"，我們需要將 "A" 替換為 "G"，這是一個取代操作。
   現在的情況如下：

序列1： AGGCAG 序列2： AGGCTAG

總共進行了2次取代操作，這就是編輯距離。在這個例子中，兩個DNA序列之間的編輯距離為2，表示我們需要進行2次操作才能將序列1轉換成序列2。

一個簡單的sample code

def min_edit_distance(s1, s2):
    # 創建一個二維矩陣，用於存儲編輯距離
    dp = [[0] * (len(s2) + 1) for _ in range(len(s1) + 1)]

    # 初始化第一行和第一列
    for i in range(len(s1) + 1):
        dp[i][0] = i
    for j in range(len(s2) + 1):
        dp[0][j] = j

    # 填充矩陣
    for i in range(1, len(s1) + 1):
        for j in range(1, len(s2) + 1):
            if s1[i - 1] == s2[j - 1]:
                cost = 0
            else:
                cost = 1
            dp[i][j] = min(dp[i - 1][j] + 1,  # 刪除
                           dp[i][j - 1] + 1,  # 插入
                           dp[i - 1][j - 1] + cost)  # 取代或不操作
    
    # 編輯距離存儲在右下角的單元格
    return dp[len(s1)][len(s2)]

# 測試
sequence1 = "AGTCAAG"
sequence2 = "AGGCTAG"
edit_distance = min_edit_distance(sequence1, sequence2)
print(f"編輯距離：{edit_distance}") #2

"""
print(dp)
   ""  A  G  G  C  T  A  G
""  0, 1, 2, 3, 4, 5, 6, 7
A   1, 0, 1, 2, 3, 4, 5, 6
G   2, 1, 0, 1, 2, 3, 4, 5
T   3, 2, 1, 1, 2, 2, 3, 4
C   4, 3, 2, 2, 1, 2, 3, 4
A   5, 4, 3, 3, 2, 2, 2, 3
A   6, 5, 4, 4, 3, 3, 2, 3
G   7, 6, 5, 4, 4, 4, 3, 2
"""