配列アセンブリング

ESTアセンブラはいくつかの点でゲノムアセンブラとは異なる。まず採用されているアルゴリズムがゲノム用とEST用では異なり、例えばゲノム用では大量の反復配列に対応している必要があるのに対し、EST用では対象が転写されたmRNAであることからその必要がない。一方でESTの場合には、細胞内ではいくつかの遺伝子は常に大量に発現していることが知られており（ハウスキーピング遺伝子）、そういったものがアセンブル対象の中に大量に重複して含まれる。

さらに、ゲノム中では遺伝子はオーバーラップを起こしていることがある（センス鎖方向とアンチセンス鎖方向など）。このような遺伝子は理想的には別々にアセンブルされなければならない。ESTのアセンブルではこの他にも、選択的スプライシングやトランススプライシング、SNPs（一塩基多型）、転写後修飾などを考慮しなければならないため、複雑な計算となっている。

配列のアセンブルには大きく分けて2種類の方法がある。

1. de-novo（デ・ノボ、新規）: 読み取った断片（リードと呼ばれる）をアセンブルして、それまでに未知のゲノム配列の再構築する
2. マッピング: 既存のゲノム配列を背骨に見立てて、それにリードをマッピングしていくやり方。

デ・ノボのアセンブルはマッピングに比べて計算量が大きく、大量のメモリを必要とし計算時間もかかる。これはデ・ノボのアセンブルを行うには全てのリード同士の組み合わせを網羅的に比較する必要があるためであり、その計算量はO(n^2)か、工夫によってO(log(n))になる程度である。

アセンブルの計算量は、断片数とその長さに左右される。断片の長さが長ければ長いほど、断片数が多ければ多いほど正しいオーバーラップを得ることができるが、それは裏を返すとよりたくさんの数のアライメントをしなければならず、より長いアライメントをしなければならなくなることから二次、あるいは指数関数的に計算量は増大してしまう。一方で短い断片であればアライメントは高速にできるが、アセンブリの位置を決める段階で反復配列などが含まれていると短いリードの場合には正しいアセンブリの位置を得ることが難しいという問題がある。

DNAシークエンシングの初期の頃は研究者が得られる塩基配列は、数週間をかけてもせいぜい数十残基の配列を2,3本得られる程度だったので、その頃は研究者が手作業でも数分でアライメントをすることができた。

1975年にはダイデオキシ法（サンガー法）が開発されると、その後改良が加えられながら2000年代の前半頃までには全自動化され並列に大量の配列が読めるようになっていった。世界中のゲノムセンターではこのようなシークエンサーの導入が進み、そこでは今度は全ゲノムショットガン法に適したアセンブラが必要となってきた。

全ゲノムショットガンのリードには以下のような特徴がある。

• リードの長さは800-900残基
• クローニングベクターなどの実験で使用された不要な配列が含まれている
• エラーが0.5%から10%含まれる

サンガー法を使ってバクテリアのゲノムを解読するプロジェクトでは、2万から20万リードのアセンブルとなり、コンピューターが1台あればアセンブルできる規模となっている。ヒトのゲノムの場合では約3千5百万リードのアセンブルとなり、それらのアセンブルには大量にコンピュータを集中的に設置したり、分散コンピューティングなどを行う必要がある。

2005年頃にはパイロシークエンシグが454ライフサイエンス社から販売されるようになった。この新しい手法ではサンガー法に比べて得られるリードの長さは短く、初期の頃は100残基程度で既に250残基は読めるようになっており、2008年末には450残基まで伸びるとされている。しかし、パイロシークエンシングはサンガー法と比べてスループットが高く低コストであることから各ゲノムセンターでの採用が相次ぎ、この新しい手法によって生産された配列を利用できるようにするべくアセンブラの開発が進められている。しかし、大量のデータを相手にしなければならないこととリード中に含まれるこの手法特有のエラーのパターンに悩まされ、2004年初頭の時点では454から提供されたNewblerアセンブラが存在していただけだった。2007年半ばにはハイブリッド版のMIRAアセンブラがChevreuxらから発表され、これが最初の無料で利用できる454向けのアセンブラとなった。このハイブリッド版というのは454のリードとサンガー法のリードを混合したものをアセンブルできるという意味で、その後このような複数のシークエンシング技術による配列を処理するものはハイブリッドアセンブリと呼ばれるようになった。