Let S and T be two sequences of length n and m, respectively. When calculating the dynamic programming table to find the optimal global alignments between the two sequences S and T, we can keep pointers to find the optimal alignments by following these pointers from cell (n, m) to cell (0,0). Each of the paths represents a different optimal alignment for the two sequences.

To illustrate, we have an example of a table between the sequences ACGTTA and AACTA. By following the arrows from the cell (6,5) to (0,0) we get a possible optimal alignment. There are many ways to get to (0,0). Each of those ways is a distinct possible optimal alignment.

The challenge is to find a dynamic programming algorithm that will give me the number of the possible paths from this first table probably by looking at pointers.

Because dynamic programming involves having a programming table I’m not sure how it should look like. What would be the appropriate policy that determines which cells to look at to find the result in the next cell.

I notice that each possible alignment is a path from (n,m) to (0,0). This implies that each different path is a divergence from a common path.

You will notice that the red path and the blue path have some parts in common. This seems to justify a dynamic programming solution because we have certain solutions in common that we can use to find the next solution.

My whole problem with this is how do I formalize this thinking into a policy that looks like:

The left part is the intial conditions. It basically tells how to find the solution for the next cells based on previous cells. This is not specific to this problem it’s just an example of what I’m looking for.