卷別

資料結構與演算法

選擇

國立臺灣大學 2025 · 考試 · 第 4 題

(5 points) Consider two protein sequences $A$ and $B$ of lengths $m$ and $n$ respectively. You are tasked with implementing a dynamic programming algorithm to find the optimal global alignment between those sequences. Given the following definitions:

A match score of $+2$ for identical amino acids.
A mismatch penalty of $-1$ for different amino acids.
A gap penalty of $-2$ for each gap introduced.

Which of the following statements is correct regarding the dynamic programming solution to this alignment problem?

(A)
The time complexity of the algorithm is $O(m + n)$ .
(B)
The space complexity of the algorithm is $O(mn)$ .
(C)
The recurrence relation for the optimal alignment score $S(i,j)$ at position $(i,j)$ in the dynamic programming matrix is: $S(i,j) = \max\{\,S(i-1,j-1) + \mathrm{match}(A[i], B[j]),\ S(i-1,j) - 2,\ S(i,j-1) - 2\,\}$ .
(D)
The traceback procedure to reconstruct the optimal alignment always starts from the top-left corner of the dynamic programming matrix.
(E)
The algorithm guarantees finding all possible optimal alignments between the two sequences.

標準解析

AI 已複查