生物情報学基礎論Ⅰまとめ

第1回

計算機やアセンブリの基本的な仕組み、ISerなら分かるでしょ。

第2回

つり銭問題

第3回

制限酵素地図の作成

部分消化問題

$${::}_nC_2$$個の整数からなる2点間の距離Lが与えられたとき、$$\Delta X=L$$となるようなn個の整数の集合Xを返す
e.g.{2,2,3,3,4,5,6,7,8,10} $$->$$ {0,2,4,7,10}

0

2

4

7

10

0

2

4

7

10

2

2

5

8

4

3

6

7

3

10

解がひとつとは限らない

モチーフ発見問題

中央文字列発見問題

配列集合を現すt*n行列DNAと、見つけるべきパタンの長さlを受け取って、TotalDistance(v,DNA)が最小となる長さlの文字列vを返す

探索木から、分枝限定法(枝刈り)をして、最悪$$O(4^lnt)$$でできる。

== 第4回 貪欲法== 速いが必ずしも最適解とは限らない

反転距離問題

記号列の、ある範囲をどんどん反転していって、(123456$$->$$125436)ある記号列に変換する際に、最低何回で一方から他方に移せるか

記号列が置換のとき、一方を恒等置換として、以下の反転ソート問題に帰着できる

反転ソート問題(接頭辞反転問題)

与えられた置換に対し、それを恒等変換に変換する最小の反転操作列を求めよ

効率のよい多項式時間アルゴリズムはまだ知られていない

簡単な貪欲な方法(SimpleReversalSort)

アルゴリズムの各ステップで、左から見て、その位置がまだソートされていなければ、続く文字まで反転して、ソートする。最悪n-1ステップでできるが、612345など、効率が悪くなってしまうところも多い。

近似アルゴリズム

最適解を$$OPT(\pi)$$,近似解を$$A(\pi)$$とおいて、$$A(\pi)/OPT(\pi)$$を入力$$\pi$$に対するアルゴリズムAの近似比、最小化問題の場合は、その入力に対する最大値を、アルゴリズムAの近似比という。SimpleReversalSortの近似比(性能保障)は(n-1)/2なので、n=1001だと、500倍も悪い解が返って来得る。

よりよい貪欲法

未整列隣接ペア数(2つ以上離れている隣接しているペア)の数を減らして(最小にして)いくように置換を行っていく

これの近似比は4になる、すなわち、ここで返ってきた答えは、最適解の4倍より悪いことはないということを表している。

第5,6,7回 動的計画法

動的計画法の簡単な例:フィボナッチ数列

$$F(n)=F(n-1)+F(n-2)$$

漸化式を立てたときに、F(n)から再帰的に求めていくのではなく、F(0)から、求めたものを積み立てていく。

つり銭問題

1,3,7セントコインがあるとする。
$$F(M)=min(F(M-1)+1,F(M-3)+1,F(M-7)+1)$$
これを、下のほうから計算していくと楽

マンハッタン観光問題

碁盤の目状の道路の各道に(観光名所という)重みが付いており、(観光客の車は)必ず右下方向に移動する。重みを最大にするようなパスを探す。

表を作り、2次元で動的計画法を適応していく。そのとき、計算していく順番は、左から1列ずつ行っても、上から一行ずつ計算しても、斜めに計算してもよい。

斜めのルートがあったりする場合は、表ではなく、ルートを含まない有向グラフ(DAG)として、動的計画法を適用していく。 DAGで動的計画法を使うときは、DAGの位相ソートで、きちんとした順番で計算をしていくことになる。

動的計画法の典型的な問題

アラインメント

挿入と削除、置換の編集を何回実行すると1つの記号列を他の記号列へと編集できるか

最長共通部分列

共通して現れる部分列:挿入と削除、置換にスコア0,変化なしにスコア1を与えたアラインメントに相当

最短超部分列

2つの文字列をともに部分列として含むような文字列:挿入と削除、置換にスコア1,変化なしにスコア0を与えたアラインメントに相当

最長増加部分列

数列の中で、増加しているような部分を取り出す:F(n)を位置nまでに出た増加部分列の長さと最大値のリストとし、これを使って動的計画法

アラインメント

グローバルアラインメント

挿入と削除、ミスマッチ、マッチにスコアを与え、動的計画法を行う。

たとえば、マッチに+1,ミスマッチに-0.5,挿入と削除に-2など。

ローカルアラインメント

ペナルティに負の数を使っている場合は、最後のマスではなく、最大のスコアを得たマスからトレースバックすることで、より局地的なアラインメントが得られる。

オーバーラップアラインメント

接頭辞と接尾辞のアラインメント:端の移動はペナルティ0にするとか

断片化したDNAをくっつけるときに役に立つ

当てはめ問題

連続した部分列でのアラインメント:一番上と下を移動するときはペナルティなし

タンデムリピート

片方の文字列が、短い文字列のリピートだった場合、その繰り返しになっている短い文字列との全パタンのアラインメントを見ることで、その繰り返しレベルでのアラインメントに持ち込める。

キメリックアラインメント

文字列集合の中から2つ選んでくっつけたものとのアラインメント

Multiple Alignment

3本以上のアラインメントは、そのままやると、$$O(N^M)$$となり、計算量爆発

アラインメントは、2本ずつやって、統合できることもあるが、できないこともあるので、各アラインメントのスコアの総和を考えたり、エントロピーを考えたりして近似解を出す

遺伝子予測

第8,9回 分割統治法

Sorting

Space efficient alignment

Herscherg’s linear space alignment

alignmentは通常、2行分のデータだけ保持すればよい

Space-efficient バージョン

表の、左右両側から行っていくことで、空間計算量mn かかるところが、4n まで節約できる。その代わり、時間は2 倍かかる。

ブロックアラインメント(グリッドを必ず通るアラインメント)

アラインメントの問題で、必ずアラインメントにおいて、$$t \times t$$のグリッドを通らないといけない場合を考える。 ここで、グリッド内の全パターンをあらかじめprecomputing しておき、ハッシュなどに入れておく。 要素になりうる物の数をk として、プレコンピューティングに$$ktkt t^2$$、アラインメントに$$O(m/t n/t)$$ ハッシュから取り出すのに$$O(\log 4t \times 4t)$$ かかるので、$$t = (log n)/4$$ととったとき、あわせて$$O({mn}/ log n)$$

ブロックアラインメントを応用した通常のアラインメント

precomputing の際、値だけでなく、道も保持しておく。すなわち、入る点と出る点の全てのパターンを保持しておく。 precomputing にかかる空間計算量は$$t = {\log t}/4$$ のとき$$n\sqrt{n}$$ ぐらいでいけて、時間計算量は上のまま。

ナイトの巡回問題

3*3のチェス盤で

K1

K2

K1

K2

(K1:白のナイト、K2:黒のナイト)

を、

K1

K2

K2

K1

に移動できない

なぜなら、位置を

C1

C6

C3

C4

C8

C7

C2

C5

と置いたとき、
$$C1 <-> C2 <-> C3 <-> C4 <-> C5 <-> C6 <-> C7 <-> C8 <-> $$
という順番でしか移動できないので、馬が他の駒を飛び越えない限り、この順番は守らないといけないため。

グラフ

シーケンサで検出したDNA断片をグラフ理論でつなげる(アセンブル)

例えば、もとはATGCAGGTCC の配列を分解して、ATG,TGCAG,GT,TCC,GG になったとする。これを復元する。

Hamiltonian Path Problem

グラフG を与えられたとき、全ての頂点をちょうど一個ずつ渡り歩くパスがあるか。 NP-complete である。

DNA断片を頂点に見て、つなぎうるところを辺で結んでも、この問題に帰着することになるため、よろしくない。

Eularian-Path Problem

グラフG を与えられたとき、全ての辺をちょうど一個ずつ渡り歩くパスがあるか。(要するに一筆書き)

各断片を長さ2の断片にさらに分解したものを頂点にし、その間を辺にしておく。

$$->$$

AT

TG

TG

GG

TG

GC

GT

TG

GG

GC

CG

GT

GC

CG

GC

CA

CA

AT

Sequence By Hybridization(SBH)

マイクロアレイにより、10 配列の全パタン(約100 万) を、マイクロチップ上に植えつけることが(理論上)できる。 (実際には、探知などの問題で1 万くらいが限界) これにより、DNA 配列を、Hybridization により知ることができる。

Spectrum Graph

アミノ酸のペプチド結合を酵素で切って質量分析にかける。様々な要因で質量分析にエラーがおきるので、質量に対して、強度のグラフが得られる。 これを、頂点を各ピーク、辺を1.アミノ酸,2.アミノ酸の「ずれ」に対応させる。 サイクルのないDirected Acyclic Graph になる。

Spectral Alignment

スペクトルのDB search に必要。斜め下へのギャップのあるアラインメントに相当。動的計画法を使う。

$$D_{ij}(k)=max(D_{i',j'}(k)+1,D_{i',j'}(k-1)+1)$$

$$O(n^4k)$$まで落とせる。(k:ギャップの数)

$$M_{i,j}=max(D_{i,j}(k),M_{i-1,j}(k),M_{i,j-1}(k))$$

ここで$$M_{i,j}(k)=max_{i'<i,j'<j}D_{i',j'}(k)$$

そして$$D_{i,j}(k)=max(D_{直線方向のi,j}(k)+1,M_{i-1,j-1}(k-1)+1)\Rightarrow O(n^2k)$$

生物情報学基礎論Ⅰ/メモ (last edited 2009-03-08 22:38:17 by xyx)