Multiplex de Bruijn graphs enable genome assembly from long, high-fidelity reads
Multiplex de Bruijn graphs enable genome assembly from long, high-fidelity reads
复制标题
DOI：
10.1038/s41587-022-01220-6
复制
发表时间：
2022-02-28
影响因子：
46.9
通讯作者：
Pevzner, Pavel A.
中科院分区：
文献类型：
--
作者：
Bankevich, Anton;Bzikadze, Andrey V.;Pevzner, Pavel A.
多重de Bruijn图算法允许从长的、高保真的reads.Although大多数现有的基因组组装器是基于de Bruijn图的，但是对于大基因组和大k-mer大小的这些图的构建仍然是难以捉摸的。随着最近用于生成人类基因组的半手动端粒到端粒组装的长高保真（HiFi）读取的出现，这种算法挑战变得特别紧迫。为了实现自动组装的长，高保真读取，我们提出了拉霍亚汇编程序（LJA），一个快速算法，使用布隆过滤器，稀疏de Bruijn图和disjointig生成。LJA将HiFi读取中的错误率降低了三个数量级，构建了大基因组和大k-mer大小的de Bruijn图，并将其转换为具有不同k-mer大小的多重de Bruijn图。与最先进的汇编器相比，我们的算法不仅实现了少五倍的错误汇编，而且还生成了更多的连续汇编。我们证明了LJA的效用，通过自动组装的人类基因组，完全组装六条染色体。
A multiplex de Bruijn graph algorithm allows high-accuracy genome assembly from long, high-fidelity reads.Although most existing genome assemblers are based on de Bruijn graphs, the construction of these graphs for large genomes and large k-mer sizes has remained elusive. This algorithmic challenge has become particularly pressing with the emergence of long, high-fidelity (HiFi) reads that have been recently used to generate a semi-manual telomere-to-telomere assembly of the human genome. To enable automated assemblies of long, HiFi reads, we present the La Jolla Assembler (LJA), a fast algorithm using the Bloom filter, sparse de Bruijn graphs and disjointig generation. LJA reduces the error rate in HiFi reads by three orders of magnitude, constructs the de Bruijn graph for large genomes and large k-mer sizes and transforms it into a multiplex de Bruijn graph with varying k-mer sizes. Compared to state-of-the-art assemblers, our algorithm not only achieves five-fold fewer misassemblies but also generates more contiguous assemblies. We demonstrate the utility of LJA via the automated assembly of a human genome that completely assembled six chromosomes.