DNA Sequence Alignment and Kings

This morning I wrote a post that included the central Delannoy numbers. The nth central Delannoy number Dn counts the number of ways a king can move from one corner of a chessboard to the diagonally opposite corner without backtracking. The more general Delannoy numbers Dm,n are the analogy for an m × n rectangular board, not necessarily square. Dm,n is also the number of possible sequence alignments for a strand of DNA with m base pairs and a strand with n base pairs [1]. At each step in the alignment process, you can introduce a gap in the first strand, the second strand or neither, which is analogous to the king who can move N, E, or NE at each step. The Delannoy numbers can be computed recursively: def D(m, n): if m == 0 or n == 0: return 1 return D(m - 1, n) + D(m, n - 1) + D(m - 1, n - 1) The code above can be sped up tremendously by adding the decorator @lru_cache(maxsize=None) above the function definition to turn on memoization. I did an experiment computing D12,15 with and…