DNA sequence alignment and Delannoy numbers
a day ago
- #Memoization
- #DNA Sequence Alignment
- #Delannoy Numbers
- 第n个中心德拉诺伊数Dn计算了王在棋盘上从一个角落移动到对角角落而不走回头路的方式数量。
- 广义德拉诺伊数Dm,n计算在m×n矩形棋盘上的路径，也代表具有m和n个碱基对的DNA链序列比对的数量。
- 德拉诺伊数可以通过递归公式计算：对于m, n > 0，D(m, n) = D(m-1, n) + D(m, n-1) + D(m-1, n-1)，且基本条件为D(0, n)=1和D(m, 0)=1。
- 使用@lru_cache进行记忆化可以显著加快计算速度，对于D12,15来说，与未使用记忆化相比速度提升超过一百万倍。
- D12,15 = 2653649025，这表明即使对于短序列，也有许多比对方式，除非施加限制条件。
- log10(Dm,n)的热图显示该函数随m和n增加而增大，在对角线上（中心德拉诺伊数）达到最大，并在m=n的东北-西南对角线上达到峰值。