DNA配列アラインメントとキングの動き
本記事では、チェス盤の一角から対角線上の反対側の角へキングがバックトラックせずに移動する経路の数を数える「中央デラノイ数」と、それを一般化した「デラノイ数Dm,n」について解説。さらに、これらの数がDNA配列アラインメントの分野とも深く関わっていることを紹介する。
背景メモ
John D. Cookは応用数学者・プログラマーで、専門的な数学と日常的な応用を橋渡しするブログで知られる。
- デラノイ数（Delannoy numbers）: 碁盤目の格子で、特定の2点間を最短経路で移動する方法の数を数える整数列。チェスのキングが斜めにも進めるルールを反映している。
- この記事の核心: デラノイ数がDNA配列アラインメント（2つのDNA配列の類似性を評価するバイオインフォマティクスの基本手法）に使われるという、一見無関係に見える数学と生物学の意外な接続を解説している。
- 配列アラインメントでは、塩基の挿入・削除・置換（ミスマッチ）を「キングの動き」としてモデル化でき、その経路数の計算にデラノイ数が登場する。