Beware of alignment inference

In "Edit distance alignment¹" we introduced the concept of an alignment of two genetic strings having differing lengths with respect to edit distance. This provided us with a way of visualizing a specific collection of symbol substitutions, insertions, and deletions that could have taken place on the evolutionary path between the two strings.

However, simply finding one optimal alignment and declaring that it represents a true evolutionary history is a dangerous idea because the actual evolutionary picture may be suboptimal. For that matter, the collection of all optimal alignments may be huge, and the characteristics of these alignments could differ widely.

In order to begin analyzing the collection of optimal alignments for a pair of strings, the first question we will ask is simple: just how many optimal alignments exist?

Assignment

Recall from "Edit distance alignment²" that if $s^{\prime }$ and $t^{\prime }$ are the augmented strings corresponding to an alignment of strings $s$ and $t$, then the edit alignment score of $s^{\prime }$ and $t^{\prime }$ was given by the Hamming distance $d_{\text{H}}(s^{\prime },t^{\prime })$, because $s^{\prime }$ and $t^{\prime }$ have the same length and already include gap symbols to denote insertions/deletions.

As a result, we obtain $d_{\text{E}}(s,t)=mi{n}_{s^{\prime },t^{\prime }}{d}_{\text{H}}(s^{\prime },t^{\prime })$, where the minimum is taken over all alignments of $s$ and $t$. Strings $s^{\prime }$ and $t^{\prime }$ achieving this minimum correspond to an optimal alignment with respect to edit alignment score.

Write a function optimalAlignments that takes two protein strings $s$ and $t$. The function return the total number of optimal alignments of $s$ and $t$ with respect to edit alignment score, modulo $134,217,727$ ($2^{27}-1$).

Example

In the following interactive session, we assume the FASTA file data.faa³ to be located in the current directory.

>>> optimalAlignments('PLEASANTLY', 'MEANLY')
4

>>> from Bio import SeqIO
>>> optimalAlignments(*SeqIO.parse('data.faa', 'fasta'))
4