DNA Sequence Alignment and Kings

- This blog post by John D. Cook connects two seemingly unrelated topics: how a king can move across a chessboard and DNA sequence alignment algorithms. - The king moves described are counted by "Delannoy numbers" (Dn for a square board, Dm,n for a rectangle). These numbers count how many distinct paths a king can take from one corner to the opposite corner, moving only east, north, or northeast (no backtracking). - This same combinatorial math appears in bioinformatics when aligning DNA or protein sequences using the "Needleman–Wunsch" or "Smith–Waterman" algorithms, which compare two sequences by allowing matches (diagonal moves), insertions/deletions (horizontal/vertical moves) — the exact same three movement types as the king's moves on a board. - So the number of ways to align two sequences is equivalent to the number of king paths, making Delannoy numbers directly relevant to computational biology and genomics.