Skip to content

KMCP: accurate metagenomic profiling of both prokaryotic and viral populations by pseudo-mapping

The preprint

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

Documents

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.

Genome collections with custom taxonomy, e.g., GTDB uses its own taxonomy and MGV uses ICTV taxonomy, are also supported by generating NCBI-style taxdump files with taxonkit create-taxdump.

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).

Features



Installation

Latest Version Github Releases Cross-platform Anaconda Cloud

Download executable binaries, or install using conda:

conda install -c bioconda kmcp

SIMD extensions including AVX512, AVX2, 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.

Commands

Subcommand Function
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

Quickstart

# 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 search.kmcp@db1.kmcp.tsv.gz

# 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

Next:

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.

Category Iterm COBS KMCP Comment
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 files Concatentated Independent
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.

Support

Please open an issue to report bugs, propose new functions, or ask for help.

License

MIT License

Acknowledgments

  • 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.