Source-linked AI summary
MEGAHIT: An ultra-fast single-node solution for large and complex metagenomics assembly via succinct de Bruijn graph
Dinghua Li, Chi-Man Liu, Ruibang Luo, Kunihiko Sadakane, Tak-Wah Lam
TL;DR
Large, complex metagenomics datasets demand substantial computational resources for de novo assembly. MEGAHIT uses succinct de Bruijn graphs to assemble such data efficiently, producing assemblies at least three times larger with better contiguity and more reads mapped than other methods.
Problem
De novo assembly of large, complex metagenomics datasets is constrained by heavy computational-resource requirements.
Method
MEGAHIT uses succinct de Bruijn graphs and a fast parallel construction algorithm, with CPU-only and GPU-accelerated implementations.
Results
At least 3 times larger assemblies achieved better N50, average length, and long-contig counts, while over 4 times more reads mapped to MEGAHIT contigs.
Takeaways & Limitations
MEGAHIT enables efficient assembly of large, complex metagenomics data on a single server while improving assembly completeness and contiguity.
Abstract
from arXiv · showhide
MEGAHIT is a NGS de novo assembler for assembling large and complex metagenomics data in a time- and cost-efficient manner. It finished assembling a soil metagenomics dataset with 252Gbps in 44.1 hours and 99.6 hours on a single computing node with and without a GPU, respectively. MEGAHIT assembles the data as a whole, i.e., it avoids pre-processing like partitioning and normalization, which might compromise on result integrity. MEGAHIT generates 3 times larger assembly, with longer contig N50 and average contig length than the previous assembly. 55.8% of the reads were aligned to the assembly, which is 4 times higher than the previous. The source code of MEGAHIT is freely available at https://github.com/voutcn/megahit under GPLv3 license.
1 INTRODUCTION
Next-generation sequencing has enabled metagenomic studies of diverse microbial communities, but the lack of reference genomes makes de novo assembly of short reads nearly inevitable. This analysis step is constrained by heavy computational-resource requirements, particularly for large and complex datasets.
- Next-generation sequencing enables metagenomic studies of microbial communities such as human guts, rumen, and soil.
- The lack of reference genomes makes de novo assembly of metagenomic short reads a beneficial and almost inevitable analysis step.
- De novo assembly is constrained by heavy computational-resource requirements, especially for large and complex datasets.
2 METHODS
MEGAHIT uses succinct de Bruijn graphs to represent assembly graphs compactly while supporting constant-time traversal. Its implementation adds edge-validity tracking and zero-indegree vertex storage to enable efficient dynamic removal and lossless graph representation.
- MEGAHIT uses succinct de Bruijn graphs, which provide compressed representations of de Bruijn graphs.
- O(m) bits encode a graph with m edges, while traversal from a vertex to its neighbors takes O(1) time.
- A bit-vector of length m marks edge validity to support efficient dynamic edge removal.
- An auxiliary vector of 2kt bits stores zero-indegree vertex sequences to ensure the graph remains lossless.Here, k is the k-mer size and t is the number of zero-indegree vertices.
3 RESULTS
MEGAHIT outperformed SPAdes on E. coli datasets, including low coverage, and was substantially faster. On large-scale soil metagenomics data, it produced larger and more contiguous assemblies with higher read-mapping performance than other methods.
- 6 times faster than SPAdes, MEGAHIT’s CPU version performed well even on the low-coverage E. coli subset.The comparison covered 100-fold, 20-fold, and 10-fold subsets evaluated with QUAST.
- 3 times larger total contig size was achieved by MEGAHIT than by other methods for contigs ≥300 bp.MEGAHIT also achieved better N50, average length, and number of long contigs (length ≥1000bp).
- Better assembly contiguity was indicated by improved N50, average length, and number of long contigs (length ≥1000bp).The analysis considered only contigs ≥300 bp.
- >4 times more reads mapped to MEGAHIT’s assembled contigs than to assemblies from other methods.Raw reads were aligned back to assembled contigs using Bowtie2.
4 CONCLUSIONS
MEGAHIT enables efficient assembly of large and complex metagenomic datasets on a single server while improving completeness and contiguity. It offers CPU-only and GPU-accelerated versions, with GPU reducing soil-dataset assembly time from 4 days to less than 2 days.
- MEGAHIT efficiently assembles large and complex metagenomic data on a single server.
- MEGAHIT provides better assembly completeness and contiguity.
- GPU acceleration shortens soil-dataset assembly time from 4 days to less than 2 days.MEGAHIT is available in both CPU-only and GPU-accelerated versions.