DNAシーケンスのアルゴリズムにビビった

DNAシーケンスですごいアルゴリズムが開発されていたと聞いて、そのブログを読みました。
そして、かなり脳内がビリビリ来ました。

de Bruijn Graph を使った de novo アセンブリの発想がすごい件 - ほくそ笑む

分からない方のために、簡単に説明すると、DNAの配列を読む（シーケンス）というのは、そのままさくっと一行が読めるわけではないんです。

例えば、

GATCCCAGGA

という真の配列があったとします。
これを、人工的に増やしてたくさんの断片を採取すると

GAT
GATC
TCCC
TCCCA
CAG
CAGG
GGA

というのが得られます。これを元に、この断片を重なっている糊しろ部分を繋ぎ合わせて、、、

GAT
（GAT）C
（TC)CC
（TCCC）A
（CA)G
（CAG）G
（GG）A

として、元の配列を再現します。（括弧でくくられたのが、糊しろ部分）

でも、これは、糊しろ部分を繋ぎ合わせるパターンが無数にあるため、すごく効率の悪い問題だったんです。
でも、僕が研究に携わってた10年前は、この方法でやむを得ないと思われてたんですよね。
これを如何に効率化するかをあーだこーだいろんな人が考えていたに違いません。

このブログでは明示的に書いてませんが、そもそも、この新しいアルゴリズムの凄いところは、「従来のDNA配列アルゴリズムは、ハミルトン問題を如何に効率的に解くかを考えているのと同等。ハミルトン問題はNP困難な問題なのだから、従来のDNA配列アルゴリズムだって効率的になんて、とけっこない」ていうことを言い切ったことだと思います。

つまり、数学的な概念化ですよね。

で、こうなると、NP困難ではなく、効率的なアルゴリズムが知られている問題に変換すればいいじゃんという発想をして、「2つずつの配列にぶつ切りにしてオイラー閉路を求める」という、このアルゴリズムが出来たんだと思います。生物学者が考えたら、せっかく断片的にでもわかっている「GATC」「TCCC」などの断片を、更に細かくしちゃえばいいなんて発想になりえますか？絶対、無理だと思います。

ちなみにオイラー閉路は、実は凄く簡単に解けるんです。
ハミルトン閉路は「全ての頂点をとおって元の頂点に戻る道筋」であり、オイラー閉路は「全ての辺を通る道筋」です。頂点と辺の違いなのに、問題の難易度が全く違うんですよ。わかりやすいかどうかはわかりませんが、僕の言葉で説明します。

オイラー閉路は、「頂点から出てる辺の数が全て偶数であれば」、必ず存在することが知られてます。

〜オイラー閉路のアルゴリズム〜
ある連結な離散グラフＧのすべての節点の次数が偶数であるとする。
①Ｇに辺の重複のない１つの閉路Ｌを描く。（その閉路Ｌがすべての辺を含んでいれば、オイラー閉路完成）。
②ＧからＬを除いて得られる残りのグラフも、すべての節点が偶数であるから、残りのグラフも、閉路Ｌ上の節点からＬに含まれていない辺をつないで同じ節点に戻る閉路Ｌ’が必ず構成できる。ＬとＬ’からなる図形は、一つの閉路と見なせ、それを新たに離散グラフＧの閉路Ｌとする。
③②の手順をすべての辺がＬに含まれるまで続ければ、得られた閉路Ｌはオイラー閉路である。

アルゴリズムは、上記の通りなんですが、ようは小さな問題に分解できるってところがミソなんです。以下の問題はLというのを適当に書いてみて、それを除いて、もう一回L’を作るわけです。でそれを続けていけば、いつか解けるという論法ですよね。

ハミルトン閉路との比較のためにすこし具体的に書くと、

辺の集合ABCDEFGHIがあって、辺ABCで図形①を作れたら、それを除いた辺の集合DEFGHGから、辺DEFで図形②を作って、それを除いた辺集合GHIから、さいごに図形③を作ると。で、その①②③をつなぐと、求めたい解になるということですね。

ハミルトン閉路の場合、

辺の集合ABCDEFGHIがあって、辺ABCで図形①を作ったとしても、辺ABCで構成される頂点I,II，IIIが他に通る辺が例えばGHIとあったとすると、図形①を作ってそこに含まれる頂点I，II，IIIに関与する辺を消すと辺集合DEFになっちゃうわけです。

これだと、使ってもいないGHIを消しちゃうことになるので、そもそも図形①を取り出したのが良かったのかどうかわかりませんよね。つまり、小問題に分解できないってことなんです。

たとえていえばあれですかね。

インターネット上の全てのサイトを通る1つのパスを探すのは大変でも、インターネットの経路をプロバイダー毎に分解して更に地域で分解して、、、その中のパスを求めて最後に足し合わせる方が楽っていうイメージですかね。（ちょっと違うけど）