Affine gap penalties exist because indels are not independent events: a single mutational event
often removes several adjacent bases, so a run of gaps should cost less than the same number of
isolated gaps. Every serious aligner — Needleman-Wunsch with Gotoh's method, BLAST, the aligners
behind every genome browser — uses an affine model for this reason.
Statement
Compute the optimal global alignment score of two DNA strings under an affine gap model.
Scoring:
- match:
+1 - mismatch:
-1 - opening a gap (the first gap character in a run):
-3 - extending a gap (each further gap character in the same run):
-1
Both strings must be aligned end to end (global alignment). The two strings arrive on two
separate lines.
Print a single integer: the maximum achievable score.
(Only the score is required. Several different alignments can achieve the optimal score, so
printing an alignment could not be graded unambiguously.)
Input — read from standard input
| Variable | Type | Description |
|---|---|---|
a
line 1
|
str |
The first sequence
1 <= len(a) <= 200, uppercase A, C, G, T only
|
b
line 2
|
str |
The second sequence
1 <= len(b) <= 200
|
These variables are already read for you in the starter code on the right.
Output
int the optimal global alignment score, as a single integer
Sample Cases
ACGTACGT
ACGGACGT
6AAAA
AAAA
4Submit also runs your code against 4 hidden test cases. Hidden inputs are never shown — if one fails you'll get its number and a description of the mismatch, not the data.
Constraints
1 <= length(a), length(b) <= 200- match
+1, mismatch-1, gap open-3, gap extend-1 - A run of
ggap characters therefore costs-3 - (g - 1)
Further Reading
- Gotoh's algorithm keeps three matrices: one for alignments ending in a match/mismatch, one
ending in a gap ina, one ending in a gap inb. - Initialise the gap rows and columns with
-3 - (i - 1), not-3 * i.