d077. Q_6_8 Local alignment

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

評分機制為：兩字母相同得8分，相異-5分，字母與空白對應-3分。

Input

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

Output

Local alignment的最大分數。

Sample Input #1

ATATCTTAACTGG
CGCGGATCATAA

Sample Output #1

Sample Input #2

AAAACTGAGGG
GGCTATT

Sample Output #2

測資資訊：

記憶體限制： 256 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 ：

計算global alignment與LCS很類似，計算local alignment與global的差別在於：可以”昨日種種譬如昨日死”，DP過程中，如果前面的分數不好，可以放棄繼承，此外，最大分數未必出現在最後的位置。

Tags:

ch6

出處:

Prof. Wu [管理者：

ktlai (K．我已霸榜．Tlai)

]

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