Your analysis doesn't take into account $seqs[$i] . $char and $seq1 eq $seq2. They are both based on N and/or M. $seqs[$i] . $char won't affect the final O() because it's higher up in the loop, but $seq1 eq $seq2 is in the innermost loop.

for my $seq1 (subseqs($s1)) {
    for my $seq2 (subseqs($s2)) {
[download]

could be written as

my @s1 = subseqs($s1);
my @s2 = subseqs($s2);
for my $seq1 (@s1) {
    for my $seq2 (@s2) {
[download]

for faster code of the same complexity.