ほくそ笑む

R言語と統計解析について

de Bruijn Graph を使った de novo アセンブリの発想がすごい件

VelvetABySS などの代表的な de novo アセンブリツールでは、アルゴリズムに de Bruijn Graph というのを使っているそうです。どうやってアセンブルしているんだろう?と興味を持っていたので、元ネタの An Eulerian path approach to DNA fragment assembly を読んでみたんですが、その発想のすごさに度肝を抜かれました。せっかくなので、ここで簡単に説明してみたいと思います。

ケーニヒスベルクの橋

まずはグラフ理論の説明から。グラフ理論は、18世紀にオイラーという数学者が「ケーニヒスベルクの橋」という問題を解くために考え出したといわれています。
ケーニヒスベルクの橋」は、次のような問題です。

18世紀の初めごろにプロイセン王国の首都であるケーニヒスベルクという大きな町があった。この町の中央には、プレーゲル川という大きな川が流れており、七つの橋が架けられていた。あるとき町の人が、次のように言った。
「このプレーゲル川に架かっている7つの橋を2度通らずに、全て渡って、元の所に帰ってくることができるか。ただし、どこから出発してもよい。」
町の人が言ったことはできるだろうか。

一筆書き - Wikipedia

この問題に対し、オイラーは陸の部分を頂点、橋を辺とするグラフに地図を抽象化して考えました。

一筆書き - Wikipedia

このグラフが一筆書き可能ならば、ケーニヒスベルクの橋をすべてわたる道が存在するということです。
このように、問題を「グラフ」という頂点と辺でできた図形に抽象化して考える理論をグラフ理論といいます。
ちなみにこの一筆書きの問題は「オイラーパス問題」と呼ばれ、任意のグラフが与えられたとき、すべての辺をわたる道(オイラーパス)を求める非常に効率的なアルゴリズムが存在することが知られています。

de novo アセンブリのふつうの考え方

さて、de novo アセンブリをやろうとなったときにどうやるのか、まずはふつうの考え方を紹介します。
アセンブリは、read(DNAの断片) がたくさん与えられたときに、どうやって元の配列を組み立てるかという問題です。これをグラフ理論で抽象化してみましょう。
各 read を頂点とし、read どうしが共通の部分配列を持っていて、くっつけることができるときに辺で結びます。

上の図では5つの read を 2-mer で結んでいます。2-mer というのは、共通する塩基(赤文字)の個数が 2 以上のときに結合できるという意味です(一般的には k-mer といって、k には数字が入ります)。
このようにしてできたグラフで考えると、アセンブリの問題は次のように言い換えることができます。
「このグラフのすべての頂点を通る道を見つけよ」
グラフの頂点を全部通る道がわかれば、通った順に read を結合していけば、元の DNA 配列を組み立てることができるというのは、わかると思います。

さて、この問題、さきほどの「ケーニヒスベルクの橋」の問題とよく似ていますね。違うところは、「ケーニヒスベルクの橋」は「すべての辺をわたる道」を見つける問題でしたが、この問題は「すべての頂点を通る道」を見つけるというところです。
この問題は「ハミルトンパス問題」と呼ばれ、実は、すごく難しいことがわかっています。
頂点の数が少ないときはまだいいのですが、頂点数(つまり、read の数)が多くなると、爆発的に難しさが上がっていきます。
ハミルトンパス問題は、1974年に「NP困難問題」に認定されました。NP困難問題というのは、簡単にいうと、コンピュータで効率的に解く方法が見つかっていないし、今後も見つけることは非常に困難であろうとされる問題です。
したがって、この問題をコンピュータで解こうとすると、すべての可能性をしらみつぶしに調べるという単純な方法しかなく、非常に長い時間をかけて計算しなければなりません。

de Bruijn Graph を使った de novo アセンブリ

さて、それでは本題の de Bruijn Graph を使ったアセンブリ手法の話に行きましょう。
この手法が出てくるまでは、アセンブリの研究は「いかにしてハミルトンパス問題を効率よく解くか」ということに集中していました。しかし、ハミルトンパス問題は NP困難なので、なかなか効率よく解けません。
しかし、この手法ではそもそもの発想が違います。
まず、read を k-mer の k で分割します。2-mer だと、read の 1〜2, 2〜3, 3〜4, ... というように、2塩基づつに分割します。それぞれの分割されたものを頂点とし、隣り合う頂点どうしを辺で結び、グラフを作ります。

次に、それぞれの read からできたグラフを、同じ配列を持つ頂点を融合させることによって合体させます。

こうしてできたのが、de Bruijn Graph と呼ばれるグラフです*1
頂点の数も増えて、なんだか複雑なグラフになった印象を持ちますね。しかし、このグラフはとても良い性質を持ちます。
この de Bruijn Graph で考えると、アセンブリの問題は次のように言い換えることができるのです。
「このグラフのすべての辺をわたる道を見つけよ」
もうおわかりですね。この問題は、オイラーパス問題です。
上に述べたように、オイラーパス問題には、非常に効率的なアルゴリズムが存在します。
したがって、この問題はコンピュータで非常に効率よく解くことができるのです。
ふつうに考えるとハミルトンパス問題という難しい問題になるアセンブリの問題を、一見複雑な de Bruijn Graph を作ることによって、オイラーパス問題という簡単な問題に変えてしまったのです。魔法のようですね。

おわりに

このように、みんながハミルトンパス問題にうんうん悩んでいるときに、de Bruijn Graph という抜け道を見つけ、オイラーパス問題に変換してしまうという発想は、かなりすごいと思います。
また、見方を少し変えただけで、難しい問題が簡単な問題に変わってしまうというのは、グラフ理論の面白いところです。
この手法を de novo アセンブリに適応するには、シーケンサーのエラー訂正やリピートの問題など、解決しなければならないことがまだあります。それはまた別の機会にということで。
それでは。

*1:正確には、k-de Bruijn Graph の部分グラフ