Question

Which of the following does not describe the local alignment algorithm?

• A. In traceback step, beginning is with the highest score, it ends when 0 is encountered
• B. First row and first column are set to 0 in initialization step
• C. The score can be negative
• D. Negative score is set to 0

Hint:

Remember the key distinction:
- Global Alignment (Needleman-Wunsch): Scores can be negative; traceback always starts at the bottom-right corner and ends at the top-left corner.
- Local Alignment (Smith-Waterman): Scores cannot be negative (minimum score is 0); traceback starts at the maximum score and ends at a value of 0.

Answer 1

The Correct Option is C

Step 1: Understanding the Concept

In bioinformatics, sequence alignment is used to identify regions of similarity between biological sequences. These similarities may indicate functional, structural, or evolutionary relationships.

The Smith-Waterman algorithm is a dynamic programming algorithm used for local sequence alignment.

Local alignment identifies the best matching sub-regions within two sequences. In contrast, global alignment, such as the Needleman-Wunsch algorithm, attempts to align the sequences over their entire lengths.

Step 2: Detailed Explanation

Let us examine the main rules of the Smith-Waterman algorithm to evaluate the given statements.

Option B: Initialization

The first row and the first column of the scoring matrix are initialized with \(0\).

\[ H_{i,0}=0 \qquad \text{and} \qquad H_{0,j}=0 \]

This allows the local alignment to begin at any position in either sequence without an initial penalty. Therefore, Option B is correct.

Options C and D: Recurrence Relation and Scoring

The score of each cell \(H_{i,j}\) is calculated using the following recurrence relation:

\[ H_{i,j} = \max \begin{cases} 0,\\ H_{i-1,j-1}+S(a_i,b_j),\\ H_{i-1,j}-d,\\ H_{i,j-1}-d \end{cases} \]

Here:

• \(S(a_i,b_j)\) is the match or mismatch score for the two sequence characters.
• \(d\) is the gap penalty.

The value \(0\) is included in the maximization step. Therefore, whenever the calculated score becomes negative, it is replaced by \(0\).

\[ H_{i,j} \geq 0 \]

Hence, negative values are not stored in the Smith-Waterman scoring matrix. Therefore, Option D is correct, while the statement "The score can be negative" in Option C is incorrect.

Option A: Traceback

In global alignment, traceback generally begins from the bottom-right cell of the scoring matrix. However, in local alignment, traceback begins from the cell containing the highest score anywhere in the matrix.

The traceback then moves diagonally, vertically, or horizontally and stops when a cell containing \(0\) is reached.

\[ \text{Traceback: Maximum-score cell} \longrightarrow 0 \]

This traceback identifies the best locally aligned regions of the two sequences. Therefore, Option A is correct.

Step 3: Final Answer

The statement that does not correctly describe the Smith-Waterman local alignment algorithm is:

\[ \boxed{\text{Option C: The score can be negative}} \]

In Smith-Waterman local alignment, all negative scores are reset to \(0\).