Local alignment (AP325 Q-6-8)

Alignment 是生物序列（如 DNA 與蛋白質）分析的重要問題，輸入兩個字元序列，我們要將兩序列的字母依照原順序做一個對應，過程中可以將任一序列的某些位置加入空白，以輸入 CTTAACT 與 CGGATCAT 為例，以下是一個可能的 alignment（以 - 表示空白）：

CTTAAC-T
CGGATCAT

以下也是一個 alignment：

C---TTAACT
CGGATCA--T

Alignment 的目的是要評估兩序列有多相似，我們會有一個評分機制，以下是一個例子：兩字母相同得 \(8\) 分，相異 \(-5\) 分，字母與空白對應 \(-3\) 分。給定評分機制，輸入兩序列，要計算最大的 alignment 分數。Alignment 可分為 global alignment 與 local alignment，前者是輸入的序列整個要納入 alignment，而後者是兩序列各選取連續的一段來做 alignment。

輸入兩字串，計算 local alignment 的最大分數。評分機制為：兩字母相同得 \(8\) 分，相異 \(-5\) 分，字母與空白對應 \(-3\) 分。

輸入格式

第一行與第二行各有一個字串，字串均只由 A、T、C、G 四個字母組成。

限制

• 每個字串的長度介於 \(1\) 與 \(500\) 之間。

輸出格式

輸出 local alignment 的最大分數。

評分說明

每筆計分測資獨立計分，每筆 5 分，共 100 分；範例不計分。

範例輸入 1

ATATCTTAACTGG
CGCGGATCATAA

範例輸出 1

43

範例輸入 2

AAAACTGAGGG
GGCTATT

範例輸出 2

21

範例說明

範例一：第一個字串取 ATCTTAA，第二個取 ATCATAA。

範例二：第一個字串取 CTGA，第二個取 CTA。

題目來源

本題出自中正大學吳邦一教授所著《AP325－從 APCS 實作題檢測三級到五級》（v1.5）第 6 章 Q-6-8，第 180 頁；經作者同意於 AACPOJ 免費公開。教材下載：AP325 講義（Google Drive）；Python 版：AP325-Python（HackMD）。