DNA序列比对与棋盘上的王
本文探讨了德兰诺伊数（Delannoy numbers）在DNA序列比对和棋盘国王路径两个看似不相关的领域中的奇妙联系。中心德兰诺伊数Dn计算了国王在棋盘中从一个角落移动到对角角落且不回溯的路径数量，而更一般的德兰诺伊数Dm,n则对应矩形棋盘的情况。这些数字在生物信息学中同样具有重要意义，用于衡量两个DNA序列之间的相似度。
背景速读
Delannoy numbers 是一类组合数学（combinatorics）中的整数序列。其中“中心 Delannoy 数” Dn 统计的是国际象棋中的王（king）从一个角走到对角（只许向右、向下或右下对角线移动）的所有路径数量。而更广泛的 Delannoy 数 Dm,n 则适用于 m×n 矩形棋盘。
- 这篇文章的核心关联：Delannoy 数恰好等于 **DNA 序列比对（sequence alignment）** 中一种常见算法的计分方式。在生物信息学里，当比对两条 DNA 序列时，允许三种操作——匹配（match）、插入/删除（insert/delete，即 indel）、以及替换（substitution）——而 Delannoy 数给出了所有可能对齐方式的总数。
- 作者 John D. Cook 是一位数学程序员和博客作者，常写数学与工程、生物学、计算机科学交叉的短篇科普，尤其擅长用棋盘游戏或几何直觉来解释抽象的整数序列。
- 这篇短文的价值在于：它用“国王走棋盘”这个直观棋题，把抽象的组合数学数与真实的生物信息学问题连接了起来，让不熟悉 DNA 比对技术的读者也能理解 Delannoy 数为何在算法中有实际应用。