de novo Whole-Genomeアセンブリの現在と未来

次世代シーケンス（NGS）テクノロジーの出現として、染色体レベルのシーケンスを構築するために、de bruijnグラフに基づくさまざまなde novoアセンブリアルゴリズムが開発されました。ただし、De Novoアセンブリにおける多くの技術的または計算上の課題はまだ残っていますが、多くの明るいアイデアとヒューリスティックは、実験的設定と計算環境の両方で課題に取り組むために提案されています。このレビューでは、de bruijnグラフの種類（ハミルトニアンとオイレリアン）の種類に基づいてde novoアセンブラーを分類し、計算の複雑さとアセンブリのあいまいさに関する短いNGS読み取りのde novoアセンブリの課題について説明します。次に、最大数キロベースの長い読み取りを生成する単一分子シーケンスプラットフォームを使用することにより、短い読み取りの制限を克服する方法について説明します。実際、長い読み取りアセンブリは、アルゴリズムとサポートステップの観点から、全ゲノムアセンブリのパラダイムシフトを引き起こしました。また、（i）短い読み取りと長い読み取りと（ii）長い読み物のオーバーラップベースのアセンブリの両方を使用して、ハイブリッドアセンブリを要約し、それらの課題と将来の見通しについて議論します。このレビューは、特定の入力データ型、計算予算、またはゲノムの最適なアプローチを決定するためのガイドラインを提供します。

As the advent of next-generation sequencing (NGS) technology, various de novo assembly algorithms based on the de Bruijn graph have been developed to construct chromosome-level sequences. However, numerous technical or computational challenges in de novo assembly still remain, although many bright ideas and heuristics have been suggested to tackle the challenges in both experimental and computational settings. In this review, we categorize de novo assemblers on the basis of the type of de Bruijn graphs (Hamiltonian and Eulerian) and discuss the challenges of de novo assembly for short NGS reads regarding computational complexity and assembly ambiguity. Then, we discuss how the limitations of the short reads can be overcome by using a single-molecule sequencing platform that generates long reads of up to several kilobases. In fact, the long read assembly has caused a paradigm shift in whole-genome assembly in terms of algorithms and supporting steps. We also summarize (i) hybrid assemblies using both short and long reads and (ii) overlap-based assemblies for long reads and discuss their challenges and future prospects. This review provides guidelines to determine the optimal approach for a given input data type, computational budget or genome.