Local Alignment with Affine Gap Penalty solved by 210

July 2, 2012, midnight by Rosalind Team

Topics: Alignment, Dynamic Programming

Building Upon Local Alignments

We have thus far worked with local alignments with a linear gap penalty and global alignments with affine gap penalties (see “Local Alignment with Scoring Matrix” and “Global Alignment with Scoring Matrix and Affine Gap Penalty”).

It is only natural to take the intersection of these two problems and find an optimal local alignment given an affine gap penalty.


Given: Two protein strings $s$ and $t$ in FASTA format (each having length at most 10,000 aa).

Return: The maximum local alignment score of $s$ and $t$, followed by substrings $r$ and $u$ of $s$ and $t$, respectively, that correspond to the optimal local alignment of $s$ and $t$. Use:

If multiple solutions exist, then you may output any one.

Sample Dataset


Sample Output


Please login to solve this problem.