Adaptation of the Needleman-Wunsch algorithm (which computes a global alignment between sequences) with custom gaps length and associated costs. A description of the vanilla NW algorithm can be found here : Needleman–Wunsch algorithm.
However, in this implementation you can define the possible gaps length and their associated costs when opening or extending a gap by the length considered. You can also change the costs of matches and mismatches (they are set to -1 and 1 by default).
For instance, {1 : (4,2), 3 : (5,3)} means we can have gaps of length 1, for which the costs for opening and extending such a gap are 4 and 2 respectively. We can also have gaps of length 3, for which the costs for opening and extending are 5 and 3 respectively.
Then the algorithm prints the alignment in a way similar to Blast.
We considered the gaps {1 : (4,2), 3 : (5,3)}.
Example 1 : comparing a coding sequence of Covid-19 with a coding sequence of a previous Coronavirus
