d074. Q-6-8. Local alignment - TCFSH CIRC Judge

Content

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 的最大分數。

Input

第一行與第二行個有一個字串，字串均只由 ATCG 四個字母組成，長度不

超過 500。

Output

Local alignment 的最大分數。

Sample Input

//case 1
ATATCTTAACTGG
CGCGGATCATAA
//case 2
AAAACTGAGGG
GGCTATT

Sample Output

//case 1
43
//case 2
21

測資資訊：

記憶體限制： 64 MB
公開測資點#0 (20%): 1.0s , <1K
公開測資點#1 (20%): 1.0s , <1K
公開測資點#2 (20%): 1.0s , <1K
公開測資點#3 (20%): 1.0s , <1K
公開測資點#4 (20%): 1.0s , <1K

Hint ：

Tags:

出處:

AP325 [管理者：

TCIRC ($\mathbb{TCFSH}\mathtt{Computer}\mathsf{Information}\mathit{Club}$)

]

ID	User	Problem	Subject	Hit	Post Date
沒有發現任何「解題報告」