生物ゲノムの解読は、その生物を詳しく理解する上で欠かせない。ゲノムは、実質 DNA を指す。生物の DNA は複数の染色体に分けられて保存されている。1 本の染色体に含まれる DNA の長さは、生物種や染色体番号にもよるが、10⁸ オーダーの塩基配列からなる。これだけ長い DNA の塩基配列をシーケンシングできる技術は、まだ開発されていない。そのため、現在では、長い DNA の塩基配列を、100 塩基前後の短い断片に切断してからシーケンシングし、次にシーケンシングされた短い断片配列を、コンピューター上で繋げていき、元の DNA 塩基配列を復元させるアプローチを取っている。このように、複数の短い塩基配列から、元の長い塩基配列を復元させることをアセンブリーという。

近縁種のリファレンス配列を利用してアセンブリーすることを reference-guided assembly という。これに対して、何もない状態からリファレンス配列をアセンブリーすることを de novo assembly という。DNA-Seq または RNA-Seq リードから de novo アセンブリーを行うには、de Bruijin グラフを利用されている。de Bruijin グラフを利用してゲノムをアセンブリするプログラムには Velvet、ABySS や SOAPdenovo などが知られている。

アセンブリーアルゴリズム

ハミルトン閉路問題

de Bruijin グラフを利用した de novo assembly について説明する。ある DNA の塩基配列が ATGATCCTAGACCCTGAT であったとする。この塩基配列を増幅させて、複数のコピーを作成する。続いて、この塩基配列をランダムに切断して、高速シーケンサーでシーケンシングすると、CCTAGA、ATGATCC、CCTGAT、GACCC の 4 リードが出力されたとする。この 4 リードから元の塩基配列を復元するには、各リードの先頭と後尾の文字列に着目し、あるリードの先頭が他のリードの後尾と重なるように並べ替えて次々とつなげていけばよい。つまり、次の図のように、各頂点（リード）を 1 回だけ通るパスを探し出せれば、元の塩基配列を復元できるようになる。

各頂点を 1 回だけ通るパスを探す問題は、ハミルトン閉路問題として知られる。ハミルトン閉路問題は、NP 困難であることが知られている。頂点（リード）の数が増えることで、問題を解くの膨大な計算リソースを必要とする。一般的に、シークエンサーでは数十万から数百万のリードを出力するために、この問題を解くのがますます困難となる。そこで、このハミルトン閉路問題をオイラーパスに置き換えて解いていく（Pevzner et al., 2001, Compeau et al., 2011）。

オイラーパス

de novo アセンブリーは、すべての頂点（リード）を 1 回だけ通るパスを見つけるというハミルトン閉路問題である。これを、各経路を 1 回だけ通るパスを見つける問題、すなわちオイラーパスを見つける問題に置き換えて解いていく。このためには、リードを長さ k 塩基の短い部分配列（k-mer）に切断して、その k-mer 配列を頂点として de Bruijin グラフを構築する。例えば、CCTAGA、ATGATCC、CCTGAT、GACCC の 4 リードの 2-mer で de Bruijin グラフを構築すると次の図のようになる。

アセンブリー

de Bruijin グラフを構築してから、グラフの各頂点に着目し、頂点と頂点の間を結ぶパスが 1 通りしかない場合、これらの頂点をマージする。

続けて、シークエンシングエラーとなるような箇所を取り除いて、グラフの各パスを通るようなパスのうち、一筆書きで描けるような長いパスを探し、これらを contig とみなして出力する。

アセンブリーの評価

ロングリードを使用してアセンブリを行うと、比較的に長めの contig が得られる。さらに、リードが paired-end である場合、ペア情報を利用して複数の contig をつなげることができる。この場合、contig と contig の間にはリードがないため、N で埋めることが多い。

アセンブリーされたゲノムの品質を評価するために、N50 や L50 などの指標が用いられる。例えば、contig の N50 を計算する場合、アセンブリーにより得られた contig を長い順に並べて、その累計長がゲノムサイズの 50% を初めて超えたときの contig のサイズを contig の N50 としている。また、そのときの contig が前から数えて何番目の contig であったのかを示すのが L50 である。基本的に N50 および L50 の値が大きければよいが、比較対象がない場合は、良し悪しを評価できない。新しいゲノムをアセンブリーしたのであれば、過去に発表されたアセンブリー評価指標と比較したり、あるいはその近縁種の最近のアセンブリー評価指標と比較したりするとディスカッションしやい。