KMCP: accurate metagenomic profiling of both prokaryotic and viral populations by pseudo-mapping
KMCP: accurate metagenomic profiling of both prokaryotic and viral populations by pseudo-mapping.
Wei Shen, Hongyan Xiang, Tianquan Huang, Hui Tang, Mingli Peng, Dachuan Cai, Peng Hu, Hong Ren.
bioRxiv 2022.03.07.482835; doi: https://doi.org/10.1101/2022.03.07.482835
Table of contents
- What can we do?
- KMCP vs COBS
What can we do?
1. Accurate metagenomic profiling
KMCP adopts a novel metagenomic profiling strategy by splitting reference genomes into 10 chunks and mappings reads to these chunks via fast k-mer matching, denoted as pseudo-mapping.
Benchmarking results on both simulated and real data indicate that KMCP not only allows for accurate taxonomic profiling of archaea, bacteria, and viral populations from metagenomic shotgun sequence data, but also provides confident pathogen detection in infectious clinical samples of low depth.
2. Fast sequence search against large scales of genomic datasets
KMCP can be used for fast sequence search against large scales of genomic datasets as BIGSI and COBS do. We reimplemented and modified the Compact Bit-Sliced Signature index (COBS) algorithm, bringing a smaller index size and much faster searching speed (2x for genome search and 10x for short reads) faster than COBS (check the tutorial and benchmark). Also check the algorithm and data structure differences between KMCP and COBS.
3. Fast genome similarity estimation
KMCP can also be used for fast similarity estimation of assemblies/genomes against known reference genomes.
Genome sketching is a method of utilizing small and approximate summaries of genomic data for fast searching and comparison. Mash and Sourmash provide fast genome distance estimation using MinHash (Mash) or FracMinHash (Sourmash). KMCP supports multiple k-mer sketches (Minimizer, FracMinHash (previously named Scaled MinHash), and Closed Syncmers) for genome similarity estimation. And KMCP is 5x-7x faster than Mash/Sourmash (check the tutorial and benchmark).
- Easy to install
- Statically linked executable binaries for multiple platforms (Linux/Windows/macOS, AMD64/ARM64).
- No dependencies, no configurations.
conda install -c bioconda kmcp
- Easy to use
- Building database is easy and fast
- ~25 min for 47894 genomes from GTDB-r202 on a sever with 40 CPU threads and solid disk drive.
- Fast searching speed
- The index structure is modified from COBS, while KMCP is 2x-10x faster.
- Automatically scales to exploit all available CPU cores.
- Searching time is linearly related to the number of reference genomes (chunks).
- Scalable searching. Searching results against multiple databases can be fast merged.
This brings many benefits:
- There's no need to re-built the database with newly added reference genomes.
- HPC cluster could linearly accelerate searching with each computation node hosting a database built with a part of reference genomes.
- Computers with limited main memory would also support searching by building small databases.
- Accurate taxonomic profiling
- Some k-mer based taxonomic profilers suffer from high false positive rates, while KMCP adopts multiple strategies to improve specificity and keeps high sensitivity at the same time.
- In addition to archaea and bacteria, KMCP performed well on viruses/phages.
- KMCP also provides confident infectious pathogen detection.
- Preset six modes for multiple scenarios.
- Supports CAMI and MetaPhlAn profiling format.
Download executable binaries, or install using conda:
conda install -c bioconda kmcp
SIMD extensions including
SSE2 are sequentially detected and used
in two packages for better searching performance.
- pand, for accelerating searching on databases constructed with multiple hash functions.
- pospop, for batch counting matched k-mers in bloom filters.
|compute||Generate k-mers (sketch) from FASTA/Q sequences|
|index||Construct database from k-mer files|
|search||Search sequences against a database|
|merge||Merge search results from multiple databases|
|profile||Generate taxonomic profile from search results|
|utils split-genomes||Split genomes into chunks|
|utils unik-info||Print information of .unik file|
|utils index-info||Print information of index file|
|utils ref-info||Print information of reference chunks in a database|
|utils cov2simi||Convert k-mer coverage to sequence similarity|
|utils query-fpr||Compute the false positive rate of a query|
|utils filter||Filter search results and find species/assembly-specific queries|
|utils merge-regions||Merge species/assembly-specific regions|
# compute k-mers kmcp compute -k 21 --split-number 10 --split-overlap 150 \ --in-dir genomes/ --out-dir genomes-k21-n10 # index k-mers kmcp index --false-positive-rate 0.1 --num-hash 1 \ --in-dir genomes-k21-n10/ --out-dir genomes.kmcp # delete temporary files # rm -rf genomes-k21-n10/ # search kmcp search --db-dir genomes.kmcp/ test.fa.gz --out-file email@example.com # merge search results against multiple databases kmcp merge -o search.kmcp.tsv.gz search.kmcp@*.kmcp.tsv.gz # profile and binning kmcp profile search.kmcp.tsv.gz \ --taxid-map taxid.map \ --taxdump taxdump/ \ --out-prefix search.tsv.gz.k.profile \ --metaphlan-report search.tsv.gz.m.profile \ --cami-report search.tsv.gz.c.profile \ --binning-result search.tsv.gz.binning.gz
KMCP vs COBS
We reimplemented and modified the Compact Bit-Sliced Signature index (COBS) algorithm, bringing a smaller index size and much faster searching speed (2x for genome search and 10x for short reads) faster than COBS.
|Algorithm||K-mer hashing||xxhash||ntHash1||xxHash is a general-purpose hashing function while ntHash is a recursive hash function for DNA/RNA|
|Bloom filter hashing||xxhash||Using k-mer hash values||Avoid hash computation|
|Multiple-hash functions||xxhash with different seeds||Generating multiple values from a single one||Avoid hash computation|
|Single-hash function||Same to multiple-hash functions||Separated workflow||Reducing loops|
|AND step||Serial bitwise AND||Vectorised bitwise AND||Bitwise AND for >1 hash functions|
|PLUS step||Serial bit-unpacking||Vectorised positional popcount with pospop||Counting from bit-packed data|
|Index structure||Size of blocks||/||Using extra thresholds to split the last block with the most k-mers||Uneven genome size distribution would make bloom filters of the last block extremely huge|
|Index loading||mmap, loading complete index into RAM||mmap, loading complete index into RAM, seek||Index loading modes|
|Input/output||Input files||FASTA/Q, McCortex, text||FASTA/Q|
|Output||Target and matched k-mers||Target, matched k-mers, query FPR, etc.|
Please open an issue to report bugs, propose new functions, or ask for help.
- Zhi-Luo Deng (Helmholtz Centre for Infection Research, Germany) gave a lot of valuable advice on metagenomic profiling and benchmarking.
- Robert Clausecker (Zuse Institute Berlin, Germany) wrote the high-performance vectorized positional popcount package (pospop) during my development of KMCP, which greatly accelerated the bit-matrix searching.