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

Citation

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.
Bioinformatics, btac845, https://doi.org/10.1093/bioinformatics/btac845

Documents

https://bioinf.shenwei.me/kmcp

What can we do?

1. Accurate metagenomic profiling

KMCP utilizes genome coverage information by splitting the reference genomes into chunks and stores k-mers in a modified and optimized COBS index for fast alignment-free sequence searching. KMCP combines k-mer similarity and genome coverage information to reduce the false positive rate of k-mer-based taxonomic classification and profiling methods.

The read mapping process in KMCP is referred to as pseudo-mapping, which is similar to but different from the lightweight algorithm in Sailfish (Patro et al., 2014), pseudoalignment in Kallisto (Bray et al., 2016), quasi-mapping in RapMap (Srivastava et al., 2016), and lightweight mapping in Salmon (Patro et al., 2017). All of these methods seek to elide the computation of base-to-base alignment using distinct strategies (Srivastava et al., 2016). In KMCP, each reference genome is pre-split into chunks of equal size, and the k-mers of a query, as a whole, are compared to each genome chunk to find all possible ones sharing a predefined proportion of k-mers with the query. Like quasi-mapping in RapMap, KMCP tracks the target and position for each query. However, the read position in KMCP is approximate and in a predefined resolution (the number of genome chunks).

Benchmarking results based on simulated and real data demonstrate that KMCP, despite a longer running time than some other methods, not only allows the accurate taxonomic profiling of prokaryotic and viral populations but also provides more confident pathogen detection in 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. You can even merge the GTDB taxonomy (for prokaryotic genomes from GTDB) and NCBI taxonomy (for genomes from NCBI).

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

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
- Supporting shell autocompletion.
- Detailed usage, database, tutorials, and FAQs.
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 (for sequence/genome search)
- The index structure is modified from COBS, while KMCP is 2x-10x faster in sequence searching.
- 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.
- The searching step can be parallelized with a computer cluster in which each computation node searches against a small database.
- Computers with limited main memory can also utilize an extensive collection of reference genomes by building and searching against 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.
Flexible support of taxonomy database
- Taxonomy data, in the format of NCBI taxdump files, are only needed in the profiling step. Therefore, it is easy to utilize an updated version of taxonomy data.
- GTDB, ICTV and custom taxonomy database are supported by creating taxdump files with taxonkit create-taxdump.
- You can even merge the GTDB taxonomy (for prokaryotic genomes from GTDB) and NCBI taxonomy (for genomes from NCBI).
- Profiling without taxonomy data is also supported by setting --level strain in kmcp profile.

Installation

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.

ARM architecture is supported, but kmcp search would be slower.

Commands

Subcommand	Function
compute	Generate k-mers (sketch) from FASTA/Q sequences
index	Construct a database from k-mer files
search	Search sequences against a database
merge	Merge search results from multiple databases
profile	Generate the taxonomic profile from search results
utils split-genomes	Split genomes into chunks
utils unik-info	Print information of .unik files
utils index-info	Print information of index files
utils index-density	Plot the element density of bloom filters for an 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-file         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

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.

The differences between KMCP and COBS

Category	Item	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 as 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	Concatenated	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.