2020 12/14 間違いを修正
2022/03/01 論文引用
de Bruijnグラフは多くのゲノムアセンブラの基礎となっているが、大規模なゲノムや大きなk-merサイズに対してどのようにしてこれらのグラフを構築するかは不明なままである。このアルゴリズムの課題は、最近、代替ストリンググラフアセンブリアプローチを使用して、ヒトゲノムのテロメアからテロメアへの半手動アセンブリを生成するために利用された、長くて正確なハイファイ（HiFi）リードの出現に伴い、特に重要になってきている。様々なゲノムの高品質なHiFiアセンブリを完全自動化するために、本著者らは、大規模なゲノムと大きなk-merサイズのためのde Bruijnグラフを構築するための効率的なjumboDBアルゴリズムと、HiFiリードをエラー訂正し、エラー訂正されたリード上にjumboDBを使用してde Bruijnグラフを構築するLJAゲノムアセンブラを開発した。固定のkmerサイズで構築されたde Bruijnグラフは一般的に絡みすぎたり、断片化しすぎたりするので、LJAではkmerサイズを変化させた多重de Bruijnグラフという新しい概念を使用している。LJAが反復性の高いヒトのセントロメアの自動アセンブリを含む様々なアセンブリの連続性を大幅に改善することを実証した。
既存のゲノムアセンブラは、k-mer サイズが大きくなるとメモリ/時間の要件が法外なものになるため、大きな k-mer サイズの de Bruijn グラフを構築するために設計されていない。例えば、300 bp 未満のリード長の Illumina リードをアセンブルするために設計された SPAdes アセンブラ (Bankevich et al., 2012) は、通常、k-mer サイズが 100 以下で使用される。より長いリードにSPAdesを適用し、k=500を超えてk-merサイズを大幅に増加させると、時間/メモリのボトルネックが発生する。メモリフットプリントを削減するために、いくつかのアセンブリアルゴリズムは、すべてのk-merを明示的に格納することを避けている：例えば、SPAdes（Bankevichら、2012）は、リード中のすべてのk-merの完全ハッシュマップ（Fredmanら、1984）を構築し、MegaHit（Liら、2015）は、すべてのリードのBurrows-Wheeler変換（BurrowsとWheeler、1984）を構築している。しかし、これらの改良を行っても、メモリフットプリントは依然として大きく、実行時間はk値サイズに比例したままであることは言うまでもない。
2つのアプローチは、より小さい時間/メモリ要件で de Bruijn graphの粗いバージョンを構築するものである：リピートグラフアプローチ(Pevzner et al., 2004)とsparse de Bruijn graph アプローチ(Ye et al., 2012)である。最近では、Kolmogorovら、2020年は、HiFiリードのリピートグラフを構築するためのFlyeアセンブラを修正した（メタゲノムのコンテキスト）。一方、RautiainenとMarschallらは、2020年、HiFiリードをスパースde BruijnグラフにアセンブルするためのMBGツールを開発した。しかし、これらのグラフは、繰り返し構造を表現する点でde Bruijn graphよりも精度が低く、したがって、セントロメアのような最も繰り返しの多い領域をアセンブルする能力を制限している。大きなk-merサイズのためのde Bruijnグラフを構築するためのこのjumboDBアルゴリズムは、4つのアルゴリズムのアイデアを組み合わせたものである：Bloomフィルタ（Bloom, 1970）、ローリングハッシュ（Karp and Rabin, 1987）、sparse de Bruijn graph（Yeら, 2012）、およびdisjointig生成（Kolmogorovら, 2019）である。これらのアイデアはそれぞれ以前のゲノムアセンブリー研究で使われていたが（例えばMBGはローリングハッシュを使ってsparse de Bruijn graphを構築している）、jumboDBはそれらをすべて組み合わせてde Bruijnグラフを構築する初めてのアプローチである。LJAはjumboDBを起動してHiFiリードのde Bruijn graphを構築し、このグラフを使ってHiFiリードのエラーを修正し、エラー修正されたHiFiリードのはるかに単純なグラフを生成し、HiFiリードの全長を利用するためにk-merサイズを変化させた多重de Bruijnグラフに変換する。
Check out the latest development of Pevzner lab, LJA — the de Bruijn genome assembler for HiFi reads! Includes jumboDB — an algorithm for construction of the de Bruijn graph for k>=5000 on the human genome in matter of hours! Can increase k further! https://t.co/GeIZrDH9XO
— Andrey Bzikadze (@AndreyBzikadze) 2020年12月12日
インストール
ubuntu18.04LTSでビルドした。
依存
git clone https://github.com/AntonBankevich/jumboDB.git
cd jumboDB/
cmake .
make -j 8
cd bin/
> ./jumboDB -h
# ./jumboDB -h
JumboDB version 1.0
Usage dbg [options] -o <output-dir> -k <int>
Basic options:
-o <file_name> (or --output-dir <file_name>) Name of output folder. Resulting graph will be stored there.
-k <int> Value of k (vertex size) to be used for de Bruijn graph construction. k should be odd (otherwise k + 1 is used instead).
--reads <file_name> Name of file that contains reads in fasta or fastq format. This option can be used any number of times in the same command line resulting in collecting reads from multiple files.
-h (or --help) Print this help message.
Advanced options:
-t <int> (or --threads <int>) Number of threads. The default value is 16.
-w <int> (or --window <int>`) The window size to be used for sparse de Bruijn graph construction. The default value is 2000. Note that all reads of length less than k + w are ignored during graph construction.
--compress Compress all homolopymers in reads.
--coverage Calculate edge coverage of edges in the constructed de Bruijn graph.
実行方法
Hi-Fiロングリード（またはそれ相当のクオリティのロングリード）とk mer値を指定する。ここでは1001とした。
jumboDB --reads long-reads.fq -k 1001 -t 20 -o outdir
- -o <file_name> (or --output-dir <file_name>) Name of output folder. Resulting graph will be stored there.
- -k <int> Value of k (vertex size) to be used for de Bruijn graph construction. k should be odd (otherwise k + 1 is used instead).
- --reads <file_name> Name of file that contains reads in fasta or fastq format. This option can be used any number of times in the same command line resulting in collecting reads from multiple files.
k値とランタイムやメモリ消費量の関係はプレプリントのSection 5の表にまとまっています。
引用
Assembling Long Accurate Reads Using de Bruijn Graphs
Anton Bankevich, Andrey Bzikadze, Mikhail Kolmogorov, Pavel A. Pevzner
bioRxiv, Posted December 11, 2020
2022/03/01
Multiplex de Bruijn graphs enable genome assembly from long, high-fidelity reads
Anton Bankevich, Andrey V. Bzikadze, Mikhail Kolmogorov, Dmitry Antipov & Pavel A. Pevzner
Nature Biotechnology, Published: 28 February 2022
2022 1/22
LJA
