Based on Lin’s DP algorithm

Dynamic Programming (DP) 是一種用於在多階段決策問題中尋找最佳解決方案的方法

建立 AlignScore 矩陣

• 建立一個名為 AlignScore 的矩陣，用於儲存 query 和 target 序列之間比對的分數
• 矩陣的大小：行數為 query 序列長度加 1 （|𝑄| + 1），列數為 target 序列長度加 1 （|𝑇| + 1）
• AlignScore(i, j) 代表 query 序列中從 q1 到 qi 的初始片段，與 target 序列中從 t1 到 tj 的初始片段之間，最佳對齊方式的分數

邊界條件：設定初始值

• AlignScore(i, 0) = -i
• AlignScore(0, j) = -j

計算 AlignScore 矩陣的值

使用以下公式計算 AlignScore(i, j) 的最佳分數：

• AlignScore(i, j) = max {AlignScore(i - 1, j - 1) + matchScore(qi, tj), AlignScore(i - 1, j) - 1, AlignScore(i, j - 1) - 1 }

公式中的每一項代表不同的對齊方式：

• AlignScore(i - 1, j - 1) + matchScore(qi, tj)：query 和 target 序列的第 i 個和第 j 個元素對齊 matchScore(qi, tj) 函數給予匹配（qi = tj）一個正向分數，不匹配（qi ≠ tj）一個負向分數
• AlignScore(i - 1, j) - 1：query 序列的第 i 個元素與 target 序列的跳過（insertion）對齊-1 是跳過的懲罰
• AlignScore(i, j - 1) - 1：target 序列的第 j 個元素與 query 序列的跳過（deletion）對齊-1 是跳過的懲罰

定義 MatchScore 函數

• matchScore(qi, tj) = { 2, if qi = tj; -2, otherwise }
• 如果 query 序列的第 i 個音符 qi 等於 target 序列的第 j 個音符 tj，則分數為 2 否則，分數為 -2

插入和刪除的處理