課題（DNA塩基配列のアラインメント）

DNAの塩基配列はA（アデニン）、C（シトシン）、G（グアニン）、T（チミン）の４種類の塩基（文字）から構成される。DNA配列のアラインメントとは、２本の異なる塩基配列の類似性を判定するため、配列を構成する各文字（塩基）同士の対応付けをとる操作である。具体的には、２本の配列において適切な場所にギャップと呼ばれる空白記号（"–"で表す）を挿入することにより，両者で対応する文字のスコアおよびギャップに科すペナルティの和（アラインメントスコア）が最大になる並べ方を求める。これを最適アラインメントと呼ぶ。

最適アラインメントを効率的に求めるために、Needleman-Wunsch法と呼ばれる動的計画法（DP）に基づくアルゴリズムが提案されている。扱う２本の配列をそれぞれx = x₁ ... x_n、y = y₁ ... y_mとし、２本の部分配列x₁ ... x_i (1 ≤ i ≤ n)、y₁ ... y_j (1 ≤ j ≤ n)に対するアラインメントスコアの最大値をF(i, j)で表す。このとき、F(i, j)はF(i, j) = 0という初期条件の下で、以下のDPの漸化式で再帰的に計算できる。

F(i, j) = max{F(i – 1, j) – d, F(i, j – 1) – d, F(i – 1, j – 1) + s(x_i, y_j)}

ここで、d > 0はギャップペナルティで、s(x_i, y_j)はx_i = y_jのときに正の値を、x_i ≠ y_jのときには負の値をとるスコア関数（一致・不一致スコア）である。反復の最後の段階でF(n, m)が得られ、その値が入力配列全体に対する最大アラインメントスコアとなる。ただし、このままでは最適アラインメントスコアが得られたのみであることに注意されたい。実際にアラインメントそのものを得るためには、DPの漸化式の右辺において、３つの場合のどれを選択したのかを記憶しておき、F(n, m)の値からF(0, 0)まで、どの場合を適用したのかの情報を後戻りで復元するトレースバックと呼ばれる操作が必要である。

(1) Needleman-Wunsch法の時間計算量および領域計算量を（ n と m を用いて）評価せよ。また、n = mと仮定したときの可能なアラインメントの数を求め、Needleman-Wunsch法の利点を考察せよ。

ヒント: Stirlingの公式n! ≈ (2πn)^1/2 (n/e)ⁿを使えばn!の見積もりが容易になる。

(2) Needleman-Wunsch法を実現するプログラムを作成せよ。ただし、ギャップペナルティをd = 1とし、スコア関数をs(x_i, y_j) = {1 (x_i = y_j), – 1 (x_i ≠ y_j)}とする。入力例はExample sequence 1、Example sequence 2であり、プログラム上でテキストファイルを読み込む設定にすること。また、アラインメント結果をこのようなフォーマットでファイル出力できるようにすること。

(3) (2)の入力例の各々に対し、塩基組成を保存したまま（つまりA、C、G、Tの各個数を保存したまま）ランダムシャッフルした塩基配列を生成するプログラムを作成せよ。また、入力配列、パラメータをいろいろ変えてみて、アラインメント結果を考察せよ。

参考文献

上記内容で不明な点がある場合は以下の文献を参照されたい。

1. 阿久津達也, バイオインフォマティクスの数理とアルゴリズム, 共立出版, 2007
2. R. Durbin, S. Eddy, A. Krogh and G. Mitchison, Biological Sequence Analysis, Cambridge University Press, 1998
3. A. ポランスキ, M. キンメル 著 (後藤修 訳), バイオインフォマティクス, シュプリンガー・ジャパン, 2010