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 的最大分數。
第一行與第二行個有一個字串,
字串均只由 $ATCG$ 四個字母組成,
長度不超過 $500$。
Local alignment 的最大分數。
ATATCTTAACTGG CGCGGATCATAA
43
AAAACTGAGGG GGCTATT
21
ID | User | Problem | Subject | Hit | Post Date |
沒有發現任何「解題報告」 |