2020 3/15、2021 6/11タイトル修正
第3世代シークエンシング技術は、アセンブリの品質を大幅に向上させた。 しかしながら、効率的なゲノムアセンブリアルゴリズムが欠如していることは、間違いなく第3世代シーケンス技術の普及への最大の障害となっている。高い誤り率は、ロングリードのアセンブリを、第二世代NGSリードのアセンブリと比較して不釣り合いに複雑で高価に感じさせる。 例えば、最初に報告されたロングリードデータを使用したヒトゲノムの全ゲノムアセンブリは、Illuminaシーケンシングデータで約24時間（論文より ref.5）だったのに比べると、50万CPU時間要している（ref.4）。 リソースの不足によってロングリード技術の適用は、バクテリアか小さなゲノムに限定されていた（ref.6） 。 ロングリードアセンブリ用のソフトウェアは、特にカバレッジの高いデータに対して、ref. 2,7,8,9,10,11,12,13,14,15,16,17の重要な改善を行ったが、依然としてソフトウェアは遅く、カバレッジが適度なデータでは理想的な水準には達していない。 もう一つの大きな問題は、ロングリードのシーケンシングコストが時間の経過とともに減少する一方で、この論文執筆時点で一般的なイルミナNGSシーケンシングよりも少なくとも一桁高いことにある。
ゲノムアセンブリソフトウェアの進化は複数の要因の影響を受けているが、最も重要なのはシーケンスの長さである（ref.18）。 シーケンス長が長くなるとアセンブリグラフ（ref.6）が単純化される可能性があるが、シーケンス長はまた、ゲノムアセンブリの計算上の複雑さに重大な影響を及ぼす。 計算生物学者は、歴史的に、ゲノムアセンブリ問題をgraph traversal problem（ref.18,19,20）、 すなわち第1世代シーケンシング技術でのシーケンスリードの overlap graph から最も可能性の高い配列を見つけるように定式化してきた。 string graphとbest overlap graphは、 global overlap graphを単純化することでより効率的にするOverlap-Layout-Consensus (OLC)の特定の形式である。 シーケンシングリードを最も効果的な方法で連鎖させることを目的とするリードベースのアルゴリズムは、オーバーラップグラフを構築するためにシーケンスのペアワイズアライメントが必要であるため、計算コストが高い。 この問題は、低スループットの第1世代シークエンシング技術から生成された比較的少量の配列では許容されたが、ハイスループットのNGSデータによって生成された膨大な量のショートリードではすぐに圧倒された。 より短い重複する k -grams（いわゆるkmer）を作りk-mer間のリンクを構築する戦略が de Bruijn graph（DBG）フレームワークで開発され、NGSアセンブリが単純化された。 アセンブリ結果は、 k -merグラフの線形（非分枝）領域から抽出される。
当初第1世代配列データの組み立てに使用されたオーバーラップグラフモデルのOLCベースのソフトウェアであるCelera Assembler （ref.1） 、AMOS （ref.23）、ARACHNE （ref.24）は、事実上DBGベースのアプローチが導入される前にNGSアセンブリに採用された。 より新しい 第３世代のsingle-molecule, real-time sequencing (SMRT) 、Oxford Nanoporeシーケンシングでは、NGSよりもはるかに長いリードが発生する。 第1世代のゲノムアセンブリでもともと使用されていたOLCアプローチは、リードが長くなる第３世代では妥当な方法になる。 しかし現在の第３世代技術の高いエラー率は、比較的正確なシーケンスのために開発された既存のOLCベースのアセンブラを使用不可能にしてしまう。 同様に、エラーが発生しやすいロングリードは、de brujin graphをブランチでいっぱいにするため、第３世代リードのアセンブルには適していない。 これらの課題に直面して、第３世代技術の開発者は、エラー訂正技術ref.2,7,9,10,13,17を使用してハイクオリティなロングリードを作成し、第1世代シーケンスアセンブリ用に開発された最初のアルゴリズムを再利用することに頼ってきた。 しかしながら、ロングリードに対するエラー訂正は、小さなバクテリアゲノムに対してさえも、広範な計算資源を必要とする。さらに、既存の第３世代リードのゲノムアセンブラで要求される高いカバレッジ（通常50x-100x）は、特に大きなゲノムで配列決定コストを著しく増加させる。
既存のゲノムアセンブリソフトウェア技術を簡単に説明する。 研究者は、AHA (ref.16) 、PBJelly (ref.15) 、SSPACE-LongRead (ref.11)などのスキャフォールディングアプローチを使用してアセンブリ領域間のギャップを修正した。 つまり 、複数のコンティグにまたがるリードを使いscaffoldsを作り、複数のコンティグにまたがるリード情報を使ってscaffolds graphを構築する。 ALLPATHS-LG (ref.14)およびCerulean (ref.12)では、長いリードは大きなコンティグ間のギャップを橋渡しするde Bruijn graph内の最良の経路を見つけるために使用される。 これらのソフトウェアパッケージは実際にロングリードゲノムアセンブリにとって重要な進歩を達成したが、複雑なあいまいさを解決することは本質的に困難であり、構造的なエラーにつながる可能性がある。 さらに、基礎となるグラフ探索アルゴリズムは、通常、探索深度に関して指数関数的な複雑さを有するため、スケーリングが不十分である。 高度に反復する領域（単純配列の長いリピートなど）は、検索深度が大きくなり、解決できない。 さらに、ロングリードに適したより強力なオーバーラップグラフ構造は、これらすべてのアプローチでは完全には探究されていなかった。 多くの場合、これらのアルゴリズムはコンティグの長さなどのヒューリスティックに依存し、繰り返し作業(ref.12,14)を必要とする。ハイブリッドアプローチに関連するこれらの重要な問題を回避するために、NGSショートリードを使用しないHGAP （ref.13）が開発された。 HGAPには、最長のリードのエラーを同じライブラリーのより短いリードを使用して修正するコンセンサスアルゴリズムが含まれている。 この手法はハイブリッド設定の初期に提案され、アセンブリパイプラインref. 2,9,10,17に広く使用されている。 しかしながら、このアセンブリ方法は、満足のいく結果を得るために比較的高いカバレッジ（50x-100x）および実質的なエラー訂正時間を必要とする。 ここで検討したアルゴリズムのほとんどはもともとバクテリアサイズのゲノムのために設計されていた。 エラーのロングリードをアライメントする技術の進歩によって計算時間も短縮されたが、これらのプログラムを大きなゲノム、特に哺乳類サイズのゲノムで実行すると、通常、大きな計算負荷（時には10 5または10 6 CPU時間）になる。これは大規模な計算クラスタには適しているが、一般的なワークステーションの能力をはるかに超えている。
この論文では、これらの問題の多くを効果的に解決するアルゴリズム手法を設計し、哺乳類の大型ゲノムの効率的なアセンブリを可能にしている。長いエラーの多いリードのエラー訂正とそれらのペアワイズアライメントが、既存のパイプラインではかなりの時間を要することを観察しているが、初期のアセンブリ段階ではこれらのどちらも必要ではない。 すべてのシークエンシングリードが構造的に正しい場合（キメラではない）、構造的に正しいドラフトゲノムを生成し、OLCアプローチで行われたように最終段階でベースレベルの精度を向上できる。 この観察結果を利用して、ロングリードでオーバーラップ情報を直接分析して活用することで、ベースレベルの修正不要のアセンブリパイプラインを開発している。 以前のアプローチとは異なり、アセンブリ結果を使用してロングリードシーケンスを整列させる計算負荷を軽減する。 これにより、上で述べた既存のハイブリッド手法に関連する問題を回避しつつ、安価なショートリードを利用できる（以下略）。本手法の実装であるDGB2OLCソフトウェアは、あらかじめ組み立てられたショートリードのコンティグを使用し、de Bruijnグラフからオーバーラップグラフへのアルゴリズム変換を促す。 ショートリードとロングリードデータはお互いを補うことができるため、ハイブリッドアセンブリアプローチは、両方のシーケンシング要件を削減できる。 論文中で、DGB2OLCはシーケンシングコストを約半分節約し、多くのメモリを消費せず、既存の方法よりも数桁高速に哺乳類サイズのゲノムをアセンブルできることを示している。
公式サイト
https://sites.google.com/site/dbg2olc/
マニュアル（論文で使われたデータセットのリンクもある）
https://github.com/yechengxi/DBG2OLC/raw/master/Manual.docx
インストール
cent OSに導入した。
依存
- Sparc
- blasr
- SparseAssebmler
blasrはconda installでも導入できるし、ubuntuならバイナリを直接ダウンロードできる（リンク）。
wget https://github.com/ylipacbio/blasrbinary/raw/master/blasr
本体 Github
Binary（linux）のダウンロード
https://github.com/yechengxi/DBG2OLC/tree/master/compiled
ラン
１、construct short but accurate contigs
de brujin graphのアセンブラを使い、短いが正確なコンティグを作成する。ここではマニュアルに習いSparseAssemblerを使っている。
SparseAssembler LD 0 k 51 g 15 NodeCovTh 1 EdgeCovTh 0 GS 12000000 f input.fq
Contigs.txtができる。他のアセンブリを使うこともできる（メタゲノムならmegahitなど）。
2、Overlap and layout
さきほどのconitg.fasta（ここではContigs.txt）を指定し、DBG2OLCのオーバーラップレイアウトでハイブリッドアセンブルを実行する。
DBG2OLC k 17 AdaptiveTh 0.0001 KmerCovTh 2 MinOverlap 20 RemoveChimera 1 Contigs Contigs.txt f long.fa
- M matched k-mers between a contig and a long read.
- AdaptiveTh adaptive k-mer matching threshold. If M < AdaptiveTh* Contig_Length, this contig cannot be used as an anchor to the long read.
- KmerCovTh fixed k-mer matching threshold. If M < KmerCovTh, this contig cannot be used as an anchor to the long read.
- MinOverlap minimum overlap score between a pair of long reads. For each pair of long reads, an overlap score is calculated by aligning the compressed reads and score with the matching k-mers.
大量のファイルが出力される。
$ ls -alth
-rwxr-xr-x 1 uesaka user 37K Mar 19 16:25 backbone_raw.fasta
-rwxr-xr-x 1 uesaka user 300 Mar 19 16:25 full_layout_coords.txt
-rwxr-xr-x 1 uesaka user 55K Mar 19 16:25 full_layout.fasta
-rwxr-xr-x 1 uesaka user 0 Mar 19 16:25 extension_log.txt
-rwxr-xr-x 1 uesaka user 0 Mar 19 16:25 extension_warning.txt
-rwxr-xr-x 1 uesaka user 19 Mar 19 16:25 DBG2OLC_CompressedOverlapGraph.dot
-rwxr-xr-x 1 uesaka user 227K Mar 19 16:25 DBG2OLC_Consensus_info.txt
-rwxr-xr-x 1 uesaka user 240 Mar 19 16:25 DBG2OLC_ContigPaths.txt
-rwxr-xr-x 1 uesaka user 304 Mar 19 16:25 DBG2OLC_Nodes_info.txt
-rwxr-xr-x 1 uesaka user 5 Mar 19 16:25 DBG2OLC_NodeSizeEst.txt
-rwxr-xr-x 1 uesaka user 154 Mar 19 16:25 DBG2OLC_Nodes.txt
-rwxr-xr-x 1 uesaka user 1.1K Mar 19 16:25 layout_compressed_reads.txt
-rwxr-xr-x 1 uesaka user 55K Mar 19 16:25 layout_reads.txt
-rwxr-xr-x 1 uesaka user 0 Mar 19 16:25 DBG2OLC_CompressedOverlapGraph.txt
-rwxr-xr-x 1 uesaka user 51 Mar 19 16:25 FinalBiDirectedBestOverlapGraph.dot
-rwxr-xr-x 1 uesaka user 82 Mar 19 16:25 CleanedBestOverlapGraph.dot
-rwxr-xr-x 1 uesaka user 35 Mar 19 16:25 CleanedBestOverlapGraph.txt
-rwxr-xr-x 1 uesaka user 46 Mar 19 16:25 CleanedBestOverlapGraphWithTies.dot
-rwxr-xr-x 1 uesaka user 87 Mar 19 16:25 StrongCleanedBestOverlapGraph.dot
-rwxr-xr-x 1 uesaka user 25 Mar 19 16:25 CleanedBestOverlapGraphWithTies.txt
-rwxr-xr-x 1 uesaka user 46 Mar 19 16:25 CleanedGraph.dot.dot
-rwxr-xr-x 1 uesaka user 38 Mar 19 16:25 CleanedGraph.dot.txt
-rwxr-xr-x 1 uesaka user 51 Mar 19 16:25 BiDirectedBestOverlapGraph.dot
-rwxr-xr-x 1 uesaka user 417K Mar 19 16:25 ChimeraIdx.txt
-rwxr-xr-x 1 uesaka user 418K Mar 19 16:25 ContainedIdx.txt
-rwxr-xr-x 1 uesaka user 58 Mar 19 16:25 RawBestOverlapGraph.dot
-rwxr-xr-x 1 uesaka user 35 Mar 19 16:25 RawBestOverlapGraph.txt
-rwxr-xr-x 1 uesaka user 46 Mar 19 16:25 RawBestOverlapGraphWithTies.dot
-rwxr-xr-x 1 uesaka user 63 Mar 19 16:25 StrongRawBestOverlapGraph.dot
-rwxr-xr-x 1 uesaka user 25 Mar 19 16:25 RawBestOverlapGraphWithTies.txt
-rwxr-xr-x 1 uesaka user 46 Mar 19 16:25 RawOverlapGraph.dot
-rwxr-xr-x 1 uesaka user 38 Mar 19 16:25 RawOverlapGraph.txt
-rwxr-xr-x 1 uesaka user 2.1M Mar 19 16:25 CompressedNonContainedReads.txt
-rwxr-xr-x 1 uesaka user 20M Mar 19 16:25 Chimeras.txt
-rwxr-xr-x 1 uesaka user 15M Mar 19 16:25 selected_reads.txt
-rwxr-xr-x 1 uesaka user 38M Mar 19 16:25 CleanedLongReads.txt
-rwxr-xr-x 1 uesaka user 278 Mar 19 16:25 LongReadContigIndex_Histogram.txt
-rwxr-xr-x 1 uesaka user 55 Mar 19 16:25 LongReadContigIndex_log.txt
-rwxr-xr-x 1 uesaka user 54M Mar 19 16:25 ReadsInfoFrom_long.fa
-rwxr-xr-x 1 uesaka user 275M Mar 19 16:13 ContigKmerIndex_HT_content
-rwxr-xr-x 1 uesaka user 28M Mar 19 16:13 ContigKmerIndex_HT_idx.txt
-rwxr-xr-x 1 uesaka user 1.5G Mar 18 22:23 ctg_pb.fasta
非モデル生物ゲノムのde novo assembly（その2）：DBG2OLCを使用する(2): 解析の流れ - NGSデータ解析まとめ
に習い、Sparcの
compiled/Sparc
utility/RunSparcConsensus.txt
utility/SeqIO.py
utility/split_and_run_sparc.sh
utility/split_reads_by_backbone.py
をカレントにコピーするか、リンクを貼っておく。
この時点でパラメータを考慮するようマニュアルには記載されている。
３、ショートリードのアセンブルファイル（step1出力のContigs.txt ）とロングリードのfastaを合体しておく。
cat Contig.txt ../PacBio.fasta > ctg_pb.fasta
４、Call consensus
ユーティリティツールを使ってコンセンサス配列を出力する。
sh split_and_run_sparc.sh backbone_raw.fasta DBG2OLC_Consensus_info.txt ctg_pb.fasta results2
引用
DBG2OLC: Efficient Assembly of Large Genomes Using Long Erroneous Reads of the Third Generation Sequencing Technologies
Chengxi Ye,a, Christopher M. Hill, Shigang Wu, Jue Ruan, Zhanshan (Sam) Ma
Sci Rep. 2016 Aug 30;6:31900.
参考ページ
関連ツール ( contiguity改善)
