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

最近更新 : 2022-04-12 09:59

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,而後者是兩序列各選取連續的一段(長度可為 $0$ )來做 alignment。

輸入兩字串,計算 local alignment 的最大分數。

Input

第一行與第二行個有一個字串,

字串均只由 $ATCG$ 四個字母組成,

長度不超過 $500$。

Output

Local alignment 的最大分數。

Sample Input #1
ATATCTTAACTGG
CGCGGATCATAA
Sample Output #1
43
Sample Input #2
AAAACTGAGGG
GGCTATT
Sample Output #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{Comp.}\ \&\ \mathsf{Info.}\ \mathit{Club}$)
]


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