Significance:
This is the algorithm — Needleman–Wunsch with affine (Gotoh) gap penalties — underlying essentially every full-length pairwise sequence alignment tool used in real bioinformatics pipelines, including the alignment core of BLAST-adjacent tools and multiple sequence aligners like Clustal and MUSCLE. Affine gaps (a high cost to *open* a gap, a smaller cost to *extend* it) reflect real biology: a single large indel event is more likely than many independent single-base indels, so the scoring should penalize the first gap base more than subsequent ones. This problem is the most algorithmically demanding "easy DP" problem in the bank — it requires tracking **three** DP matrices simultaneously instead of one.
Statement
Given two DNA strings `a` and `b`, and a scoring scheme: - Match: **+1** - Mismatch: **−1** - Gap opening: **−2** (cost of the *first* gap character in a run) - Gap extension: **−1** (cost of each *additional* consecutive gap character)
Compute the **optimal global alignment score** using the Gotoh algorithm (three-matrix affine-gap dynamic programming: one matrix `M` for match/mismatch states, and two matrices `X`, `Y` for gaps in each sequence). The entire length of both sequences must be aligned (this is a *global*, not local, alignment — see Problem 17 for the local variant). You only need to output the optimal **score**, not the alignment itself.
Sample Input
a = ACGTACGT
b = ACGGACGT
Sample Output
6
Constraints
- `1 ≤ length(a), length(b) ≤ 200` - Scoring constants are fixed as given above (do not make them configurable inputs for this version)
My Notes
Log in to save personal notes.
Console output will appear here when you click Run Code or Submit...