演算法›Ch3 動態規劃第 3 題/共 40 題
3. Dynamic Programming、序列比對、Sequence Alignment
#AL-03-003中Dynamic Programming序列比對Sequence Alignment
Consider two protein sequences and of lengths and respectively. You are tasked with implementing a dynamic programming algorithm to find the optimal global alignment between these sequences. Given the following definitions:
- A match score of for identical amino acids.
- A mismatch penalty of for different amino acids.
- A gap penalty of for each gap introduced.
Which of the following statements is correct regarding the dynamic programming solution for this alignment problem?
參考答案與解析
此系列選項都有明顯錯誤:(A) 時間複雜度應為 O(mn) 不是 O(m+n);(B) 空間複雜度確實可以是 O(mn)(若不壓縮)——這句是對的;(C) 遞迴式寫錯(兩個分支都寫成 S(i,j-1)-2,應該要有一個是 S(i-1,j)-2);(D) traceback 應從右下角開始往回推,不是左上角;(E) 只保證找到「一個」最佳解,不保證找出所有最佳解。故正確答案為 (B)。
📄 台大114
▤完整推導請見《WH 資工筆記 · 演算法》Ch3 動態規劃