macでインフォマティクス

macでインフォマティクス

NGS関連のインフォマティクス情報についてまとめています。

高速なラージゲノムのハイブリッドアセンブルツール DGB2OLC

 

 第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アセンブリに採用された。 より新しい 第3世代のsingle-molecule, real-time sequencing (SMRT) 、Oxford Nanoporeシーケンシングでは、NGSよりもはるかに長いリードが発生する。 第1世代のゲノムアセンブリでもともと使用されていたOLCアプローチは、リードが長くなる第3世代では妥当な方法になる。 しかし現在の第3世代技術の高いエラー率は、比較的正確なシーケンスのために開発された既存のOLCベースのアセンブラを使用不可能にしてしまう。 同様に、エラーが発生しやすいロングリードは、de brujin graphをブランチでいっぱいにするため、第3世代リードのアセンブルには適していない。 これらの課題に直面して、第3世代技術の開発者は、エラー訂正技術ref.2,7,9,10,13,17を使用してハイクオリティなロングリードを作成し、第1世代シーケンスアセンブリ用に開発された最初のアルゴリズムを再利用することに頼ってきた。 しかしながら、ロングリードに対するエラー訂正は、小さなバクテリアゲノムに対してさえも、広範な計算資源を必要とする。さらに、既存の第3世代リードのゲノムアセンブラで要求される高いカバレッジ(通常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

https://github.com/yechengxi/DBG2OLC

 Binary(linux)のダウンロード

https://github.com/yechengxi/DBG2OLC/tree/master/compiled

 

ラン

1、de brujin graphのアセンブラを使い、短いが正確なコンティグを作成する。ここではマニュアルに習いSparseAssemblerを使っている。

SparseAssembler LD 0 k 51 g 15 NodeCovTh 1 EdgeCovTh 0 GS 12000000 f input.fq

 Contigs.txtができる。

 

 2、さきほどの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

]$ 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

をカレントにコピーするか、リンクを貼っておく。

この時点でパラメータを考慮するようマニュアルには記載されている。

 

3、ショートリードのアセンブルファイル(step1出力のContigs.txt )とロングリードのfastaを合体しておく。

cat Contig.txt ../PacBio.fasta > ctg_pb.fasta

 

4、DBG2OLCのユーティリティツールを使いコンセンサス配列を出力する。

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

Published online 2016 Aug 30.

 

参考ページ