配列アセンブリング
アセンブルの計算量は、断片数とその長さに左右される。断片の長さが長ければ長いほど、断片数が多ければ多いほど正しいオーバーラップを得ることができるが、それは裏を返すとよりたくさんの数のアライメントをしなければならず、より長いアライメントをしなければならなくなることから二次、あるいは指数関数的に計算量は増大してしまう。一方で短い断片であればアライメントは高速にできるが、アセンブリの位置を決める段階で反復配列などが含まれていると短いリードの場合には正しいアセンブリの位置を得ることが難しいという問題がある。
DNAシークエンシングの初期の頃は研究者が得られる塩基配列は、数週間をかけてもせいぜい数十残基の配列を2,3本得られる程度だったので、その頃は研究者が手作業でも数分でアライメントをすることができた。
1975年にはダイデオキシ法(サンガー法)が開発されると、その後改良が加えられながら2000年代の前半頃までには全自動化され並列に大量の配列が読めるようになっていった。世界中のゲノムセンターではこのようなシークエンサーの導入が進み、そこでは今度は全ゲノムショットガン法に適したアセンブラが必要となってきた。
全ゲノムショットガンのリードには以下のような特徴がある。
リードの長さは800-900残基
クローニングベクターなどの実験で使用された不要な配列が含まれている
エラーが0.5%から10%含まれる
サンガー法を使ってバクテリアのゲノムを解読するプロジェクトでは、2万から20万リードのアセンブルとなり、コンピューターが1台あればアセンブルできる規模となっている。