d074: Q-6-8. Local alignment
Tags : DP
Accepted rate : 1人/1人 ( 100% ) [非即時]
評分方式:
Tolerant

最近更新 : 2020-09-23 21:31

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:
DP
出處:
AP325 [管理者:
TCIRC ($\mathbb{TCFSH}\mathtt{Computer}\mathsf{Information}\mathit{Club}$)
]


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