As we change the parameters contributing to alignment score, the nature of alignments achieving the maximum score may change. One feature of maximum-score alignments worthy of consideration is the number and size of their gaps. In this problem, we would like to determine the maximum number of possible gaps in any optimal alignment based solely on the parameter values chosen.
For the computation of an alignment score generalizing the edit alignment score, let $$m$$ denote the score assigned to matched symbols, $$d$$ denote the score assigned to mismatched non-gap symbols, and $$g$$ denote the score assigned a symbol matched to a gap symbol - (i.e., $$g$$ is a linear gap penalty).
Write a function maximalGaps that takes two DNA strings $$s$$ and $$t$$. The function must return the maximum number of gap symbols that can appear in any maximum score alignment of $$s$$ and $$t$$ with score parameters satisfying $$m > 0$$, $$d < 0$$ and $$g < 0$$.
In the following interactive session, we assume the FASTA file data.fna1 to be located in the current directory.
>>> maximumGaps('AACGTA', 'ACACCTA') 3 >>> from Bio import SeqIO >>> maximumGaps(*SeqIO.parse('data.fna', 'fasta')) 2905