= Solution
Use \b[<global sequence alignment>], for example the <Needleman-Wunsch algorithm> with an appropriate <substitution matrix> and <gap penalty>. The two full-length <globin> <proteins> are related by <orthology> and are from closely related species, so the expected correspondence extends across both complete sequences. Unmatched ends should normally contribute to the score rather than being discarded.
With a <linear gap penalty> of magnitude $g$, the <dynamic programming> entry $F_{ij}$ is the best score for the first $i$ and $j$ residues. It satisfies
$$
F_{ij}=\max\{F_{i-1,j-1}+s(a_i,b_j),\ F_{i-1,j}-g,\ F_{i,j-1}-g\},
$$
with $F_{i0}=-ig$, $F_{0j}=-jg$, and traceback from $F_{mn}$. An <affine gap penalty> uses separate match and gap states.
Back to article page
