DNA Sequence Alignment and Kings

This article discusses the relationship between Delannoy numbers, king moves on a chessboard, and DNA sequence alignment. It explains how the nth central Delannoy number counts the number of paths a king can take across a chessboard, which is analogous to the number of possible alignments between two DNA strands. The article provides a recursive Python implementation for computing Delannoy numbers and demonstrates the dramatic performance improvement from memoization using @lru_cache, showing a speedup of over a million times. It also includes a heatmap visualization of log10(Dm,n) and references a scientific paper on DNA sequence alignment.