Dynamic Programming for Sequence Alignment | Dataford Interview Questions

Genentech sequence-analysis workflows compare DNA sequences that may contain substitutions and insertion or deletion events. Given two sequences and scoring parameters, compute an optimal global alignment using affine gap penalties, then return its score and aligned sequences.

A gap of length k costs gap_open + (k - 1) * gap_extend. Matches and mismatches receive the supplied scores. The alignment may insert - characters, but removing those characters from each aligned sequence must recover the original inputs.

Formal Specification

Implement global_alignment(seq_a, seq_b, match, mismatch, gap_open, gap_extend). The sequences are strings containing uppercase DNA bases. Return a tuple (score, aligned_a, aligned_b), where score is the maximum possible alignment score and the two aligned strings have equal length.

If multiple alignments have the same optimal score, return any one of them.

Constraints

0 <= len(seq_a), len(seq_b) <= 500
Each sequence contains only A, C, G, and T
match > 0
mismatch <= 0
gap_open > 0 and gap_extend > 0
Gap penalties are subtracted from the score

Function Signature

def global_alignment(seq_a, seq_b, match, mismatch, gap_open, gap_extend):

Your question is Dynamic Programming for Sequence Alignment. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem