DNA sequence alignment and Delannoy numbers
a day ago
- #Memoization
- #DNA Sequence Alignment
- #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.
- General Delannoy numbers Dm,n count paths on an m × n rectangular board and also represent the number of sequence alignments for DNA strands with m and n base pairs.
- Delannoy numbers can be computed recursively using D(m, n) = D(m-1, n) + D(m, n-1) + D(m-1, n-1) for m, n > 0, with base cases D(0, n)=1 and D(m, 0)=1.
- Memoization via @lru_cache dramatically speeds up computation, making it over a million times faster for D12,15 compared to without memoization.
- D12,15 = 2653649025, showing many alignments even for short sequences unless restrictions are placed.
- A heatmap of log10(Dm,n) shows the function increases with m and n, is largest on the diagonal (central Delannoy numbers), and peaks where m=n along NE-SW diagonals.