二つの塩基配列(またはアミノ酸配列)を比較するには一定の長さの部分塩基配列を取り出し、一致しているかどうかを調べるとよい。 さらにこの方法を発展させた一定の長さに含まれる一致した塩基を数えるハープロットがある。 これらの方法は二つの塩基配列の類似度を視覚化するすぐれた方法であるが、複数の配列間で比較をするときには数量化する必要がある。 本講義では類似度を数量化する方法を学ぶ。
下の図は簡略化したマンハッタンの地図である。 図中の1から15までの黒四角は観光名所を示す。 一番左上の59th St.と8the Ave.の交差点でバスを降り、自由時間となった。 集合は右下の42nd St.と3rd Ave.の交差点である。 自由時間は短く、南と東へのみに歩く時間しかない(観光名所は外からみるだけ)。 できるだけ多くの名所を写真に収めるためにはどのような道順をえらぶのがよいか。
下の図は図式化したマンハッタン観光客問題である。 左上の丸から出発し、矢印の方向に進んでいく。 そのときそれぞれの矢印に与えられた点数を獲得していくものとする。 右下の丸まで進むとき、最も多くの点数を獲得できる経路を探すにはどのようにしたらよいか。
動的計画法(Dynamic programming)とは問題をより小さな問題に分割しそれを解く。小問題の結果を記録(記憶)し、最初の問題の解につなげる方法である。 グラフ化したマンハッタン観光客問題ではある地点で得られる最大値をそれより前の地点の最大値から順に計算して導くことができた。 すなわち、頂点(n,m)に至る道筋は(n-1,m)からか(n, m-1)からのみであることを利用して、(n,m)の最大値はいずれかの頂点で得られる値に通る辺の値を加えたものと計算することができる。 そうすることで全解探索と比べて計算量を大きく減らすことができる。
二つの塩基配列の比較にマンハッタン観光客問題を応用する。 二つの塩基を縦と横に並べ、位置塩基ずつ比較する。 縦と横の塩基が一致したとき、斜めの線に点を与える。 最も多くの点を獲得できる経路が二つの塩基配列の類似度となる。
二つの塩基配列を比較し、一致、置換、挿入、欠失に適切な点数を与えることでその塩基配列間の類似度を数量化することができる。 一致、置換、挿入または欠失に与える点数はどのような類似度を評価したいのかという目的によって変わる。 例えばタンパク質をコードしている遺伝子であれば挿入や欠失は大きな機能の変化を与える可能性があるのでそれらは減点とする一方、イントロンやプロモーターといった塩基配列の場合特定の塩基の繰り返しはそれほど影響がないので減点を小さくするといったことが考えられる。
下記のように-を挿入して一致する塩基を上下に並べたものをアライメントと呼ぶ。
ATCGT-AC AT-GTTAT
下の二つの塩基配列を比較すると、最大の点数を与える経路は類似度をよく評価していない。
二つの塩基配列の端から端までのアライメントをグローバルアライメントと呼ぶ。 これに対して部分的に似ているところを比較したものをローカルアライメントと呼ぶ。 ローカルアライメントを適切に評価するためには、原点から各点への近道と各点から終点への近道を考えるとよい。
ATG-ACTG- A-GCA-TGA
ATGACTG AGCATGA