Gaps on the Ends are Free
We have covered both global and local alignments. However, sometimes we need a hybrid approach that avoids the weaknesses of these two methods. One such alternate approach is that of fitting alignments outlined in “Finding a Motif with Modifications”.
Another tactic is to allow ourselves to trim off gaps appearing on the ends of a global alignment for free; this is relevant if one of our strings to be aligned happens to contain additional symbols on the ends that are not relevant for the particular alignment at hand.
Return: The maximum semiglobal alignment score of
>Rosalind_79 CAGCACTTGGATTCTCGG >Rosalind_98 CAGCGTGG
4 CAGCA-CTTGGATTCTCGG ---CAGCGTGG--------
This problem follows Jones & Pevzner, An Introduction to Bioinformatics Algorithms, Problem 6.24.