DNA序列比对与国际象棋中的“王”DNA Sequence Alignment and Kings

今天早上我写了一篇包含中心德兰诺伊数（central Delannoy numbers）的文章。第 n 个中心德兰诺伊数 Dn 表示在国际象棋棋盘上，王从一角移动到对角的另一角且不走回头路的路径数量。

更一般的德兰诺伊数 Dm,n 则适用于 m × n 的矩形棋盘，不一定是正方形。

Dm,n 也是由 m 个碱基对组成的 DNA 链和由 n 个碱基对组成的 DNA 链之间可能的序列比对数量 [1]。在比对过程的每一步中，你可以在第一条链、第二条链中引入空位（gap），或者都不引入，这类似于王在每一步都可以向北（N）、向东（E）或向东北（NE）移动。

德兰诺伊数可以通过递归方式进行计算：

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)

上述代码可以通过添加装饰器（decorator）来极大地提速

@lru_cache(maxsize=None)

将其置于函数定义上方即可开启记忆化（memoization）。我分别在使用和不使用记忆化的情况下做了一个计算 D12,15 的实验，耗时分别为 77.1805 秒和 0.000062 秒，也就是说，记忆化让代码快了一百多万倍。

顺便提一下，D12,15 = 2653649025，因此即使是很短的序列也有许多种比对方式，除非你对允许的比对加以限制。

更新：这里有一张绘制了 log10(Dm,n) 的热力图。显然，该函数值随 m 和 n 的增加而增加：棋盘越大，可能的路径就越多。此外，对角线上的值更大（即中心德兰诺伊数）。如果你沿着东北到西南的对角线观察，该函数在 m = n 的中间位置取得最大值。

[1] Torres, A., Cabada, A., & Nieto, J. J. (2003). An exact formula for the number of alignments between two DNA sequences. DNA Sequence, 14(6), 427–430. https://doi.org/10.1080/10425170310001617894