真核生物ゲノムにも対応したReference-assisted assemblyツール　MEDUSA

　ショートリードシーケンシングデータのデノボアセンブリでは、通常、断片化された配列セット（コンティグ）が生じる。このようなコンティグの順序および方向の決定は、ゲノムのFinishingに向けた最初の些細ではないステップを表しており、手動編集を必要とする（論文より　Barton and Barton、2012）。現在の好ましいアプローチは、シーケンシングされたリードをコンティグに組み立て、ペアワイズ情報を足場に結合することに基づいている。このようなアプローチに基づくソフトウェアの大部分は、いくつかの準備段階を有しており、リードおよびコンティグライブラリを最初に特定のフォーマットに変換し、次に外部アライナー（例えば、 BWA、（Li and Durbin、2009）またはBOWTIE（Langmead et al、2009）]を使用して、コンティグを一緒に結合する。パイプラインの終わりにスキャフォールディングのgraphが構築され、graphを分析し、足場構造を生成する。現在利用可能な方法/ソフトウェアには、SOPRA（Dayarian et al、2010）、SCARPA（Donmez and Brudno、2013）、MIP（Salmelaら、2011）、Opera（Gaoら、2011）、GRASS（Gritsenkoら、2012）およびSSPACE（Boetzer et a、2011）がある（論文執筆時点）。最近の比較研究（Hunt et al、2014）ではスキャフォールディングソフトウェアのほとんどを分析し、ベンチマークしている。著者らは、一般的にユーザビリティやソリューションの面で満足できるものはなく、この分野の改善の余地がまだあると結論づけた。

　ゲノムを足場にする別のアプローチは、完全な（クローズド）リファレンスゲノムを用いてコンティグの順序および方向を誘導する。生成されたドラフトコンティグのマッピング（およびスケーティング）のための多くの利用可能な方法が存在する（Galardiniら、2011; Darlingら、2010; Silvaら、2013; van Hijumら、2005; Kolmogorovら、 2014; Kim et al、2013; Husemann and Stoye、2010）。このアプローチは、情報が入手可能でも信頼できるものでもない古代DNA断片再構成（Rajaraman et al。、2013）などの特定の状況でも使用されている。

　これらのソフトウェアは実装が大きく異なるが、一般に、（i）単一の参照ゲノムしか許容しない（Galardini et al、2011）、（ii）複数のゲノムが許可されている場合、一般にこれらをクローズしなければならない、（iii）選択された分類群間の進化的関係を説明する基準系統をマルチリファレンスゲノムベースの足場を誘導するために提供すべきである（Kolmogorov et al 、2014）。前述のアプローチのどれも、実用上の制限を表すこれらの制約をすべて無視することは出来ない。実際、モデル生物を除き、信頼性の高いクローズドリファレンスゲノムが常に利用可能なわけではない。さらに、特にバクテリアの場合、密接に関連する生物の間のゲノム再編成は、重要な構造的相違をもたらし、参照として単一のゲノムに基づくscaffoldingを妨げる可能性がある。最後に、同じ種の内部でも大きな遺伝的変異が起きている場合はどの遺伝子マーカーを使うかで異なる系統的関係を導いてしまうため、信頼できるリファレンスを選択すること自体がチャレンジングである。

　著者らは新規取得したコンティグのセットを順序付けして配向させ、ドラフトゲノムを構築するためのアルゴリズムMEDUSA（Multi-Draft based Scaffolder）を開発した。他のソフトウェアとは異なり、（i）グラフ上の組み合わせ最適化定式化によって足場の問題を定式化し、それを解決するための効率的な定数因子近似アルゴリズムを実装する。（ii）スキャフォールディング中に複数の参照ゲノムを使用することを可能にする。（iii）生物の参照セット間の進化的関係（すなわち、系統樹）に関する事前知識を必要とせず、（iv）ドラフトおよび完全参照ゲノムの両方を扱うことができる。現在の公的データベースではドラフトゲノムの数が完全にFinishされたゲノムの数を大幅に上回っているため（Reddy et al、2014）、後者の点は非常に有益である。 MEDUSAの戦略は、標的に関連するゲノムのセットを各コンティグに相対的な位置を割り当てるために用いることができ、この種の情報は実際に容易に利用できるという直感に基づいている。具体的には、これらの他のゲノムにおける隣接領域にマッピングするコンティグは、得られた足場において隣接すると考えられる。 MEDUSAは、このようなスキャフォールディング問題をグラフの経路被覆問題として定式化し、臨時最適化技術で解決する。基本となるアルゴリズムは、コマンドラインソフトウェアとWebサーバーの両方で実装されている。MEDUSAをバクテリアおよび真核生物のデータセット（Saccharomyces cerevisiae S288c、Drosophila melanogaster）で試験することにより、本ソフトウェアは、現在利用可能な他のものと比較して非常によく機能し、Huntらによって指摘された暗黙の要求の一部に答えることが明らかになった。