Source-linked AI summary
Multiple Comparative Metagenomics using Multiset k-mer Counting
Gaëtan Benoit, Pierre Peterlongo, Mahendra Mariadassou, Erwan Drezen, Sophie Schbath, Dominique Lavenier, Claire Lemaitre
TL;DR
Large metagenomic comparisons are constrained by incomplete taxonomic assignment and de novo methods that may not scale or provide precise, exhaustive results. Simka uses k-mer counts to compute ecological distances across many datasets; on HMP data, these distances correlate with taxonomic distances and recover the same biological structure.
Problem
Taxonomic assignment covers only a subset of sequences, while de novo comparisons of whole read sets may not scale to large studies or provide precise, exhaustive results.
Source: Introduction · p. 2Method
Simka counts k-mers across multiple metagenomic datasets and substitutes those counts for species counts to compute a collection of ecological distances.
Source: Introduction · p. 3, Overview · p. 4, Discussions · p. 19Results
K-mer-based and taxonomic distances were well correlated (r > 0.8 for k ≥21), and Simka recovered the same biological structure as taxonomic studies.
Source: Discussions · p. 22Takeaways & Limitations
On real datasets, k-mer-based distances capture the same underlying structure and lead to the same conclusions as taxonomic distances.
Source: Introduction · p. 4K-mer-only beta-diversity estimates can be biased downward by shared genomic regions or horizontal transfers and upward by genome-size heterogeneity or variation in k-mer composition along genomes.
Source: Discussions · p. 22
Abstract
from arXiv · showhide
Background. Large scale metagenomic projects aim to extract biodiversity knowledge between different environmental conditions. Current methods for comparing microbial communities face important limitations. Those based on taxonomical or functional assignation rely on a small subset of the sequences that can be associated to known organisms. On the other hand, de novo methods, that compare the whole sets of sequences, either do not scale up on ambitious metagenomic projects or do not provide precise and exhaustive results. Methods. These limitations motivated the development of a new de novo metagenomic comparative method, called Simka. This method computes a large collection of standard ecological distances by replacing species counts by k-mer counts. Simka scales-up today's metagenomic projects thanks to a new parallel k-mer counting strategy on multiple datasets. Results. Experiments on public Human Microbiome Project datasets demonstrate that Simka captures the essential underlying biological structure. Simka was able to compute in a few hours both qualitative and quantitative ecological distances on hundreds of metagenomic samples (690 samples, 32 billions of reads). We also demonstrate that analyzing metagenomes at the k-mer level is highly correlated with extremely precise de novo comparison techniques which rely on all-versus-all sequences alignment strategy or which are based on taxonomic profiling.
Introduction
Taxonomic approaches miss or exclude much metagenomic sequence content, while existing de novo comparisons struggle to scale or preserve precision. Simka compares many datasets using k-mer counts to compute ecological distances, with reported HMP results showing both practical scale and agreement with taxonomic structure.
Introduction
- Taxonomic approaches based on marker genes can miss diversity through amplification and primer bias, lack strain-level discrimination, and omit many reads while requiring costly clustering.Unknown organisms also make precise taxonomic assignment difficult in large metagenomic studies.Source: Introduction · p. 2
- Whole-read-set comparison with BLAST does not scale to studies containing dozens or hundreds of large read sets, while Commet and MetaFast can bottleneck on time or memory.Mash uses fewer resources, but its subsampling yields distances that omit relative abundance and are not computed exactly.Source: Introduction · pp. 2–3
- Earlier k-mer methods include shared-word read comparisons such as Compareads and Commet, and reduced-feature methods such as MetaFast and Mash.MetaFast groups assembly-graph k-mers and uses Bray-Curtis dissimilarity; Mash uses MinHash subsampling and reports a presence-absence Jaccard index. K-mers are motivated as genome-specific, abundance-related features that can aggregate similar organisms without classification; earlier comparisons were limited to k < 11 for computational reasons.Source: Introduction · pp. 2–3
- Simka replaces species counts with k-mer counts to compute a collection of ecological distances across many datasets, including for k-mer sizes up to 30.Its multiple-dataset counting strategy processes data on-the-fly without storing large temporary results.Source: Introduction · pp. 3–4
- Simka processed 690 HMP samples (32 billion reads) in less than 10 hours using no more than 70 GB RAM; Mash was approximately two to five times faster.Simka otherwise outperformed state-of-the-art read-comparison methods in computational needs.Source: Introduction · pp. 3–4
- On real datasets, k-mer-based distances were highly correlated with taxonomic distances, capturing the same underlying biological structure and leading to the same conclusions.Source: Introduction · p. 4
Materials and Methods
Simka computes ecological distances from metagenomic k-mer counts, streaming abundance vectors instead of storing the full count matrix. Its multiset counting strategy supplies those vectors for parallel distance computation across datasets.
Overview
- 260 TB would be required for the k-mer count matrix on 690 HMP datasets, so Simka streams abundance vectors and updates distance contributions without storing the full matrix.Each vector contains a k-mer’s counts across all datasets; independent contributions are aggregated into the final distance matrix.Source: Overview · p. 5
Multiset k-mer Counting
- MKC partitions and sorts canonical k-mers separately across datasets, then merges sorted partitions to generate abundance-vector streams in parallel.Low-abundance k-mers are usually sequencing-error products; filtering them speeds processing but may affect the distance matrix, and the default threshold is 2.Source: Multiset k-mer Counting · pp. 6–7
Ecological distance computation
- Simka derives ecological distances from abundance vectors, computing marginal terms and cross-dataset terms before combining them into the distance matrix.The algorithm computes distance contributions in parallel and aggregates them after processing the streams.Source: Overview · p. 5, Ecological distance computation · pp. 7, 8, 10
- Qualitative distances use shared and sample-specific distinct k-mer counts, while quantitative distances use abundance information; both fit Simka’s one-pass framework.The paper also adapts presence-absence distances with abundance information using simpler estimates because more elaborate estimates require complete sample count vectors, whereas Simka streams only a few counts at a time.Source: Ecological distance computation · pp. 9–10
- The additive distance computation is linear in the number of distinct solid k-mers, but does not handle ecological-similarity or k-mer edit distances requiring all-versus-all comparisons.Simka is parallelized for grid or cloud systems and automatically splits work according to available nodes and cores.Source: Ecological distance computation · p. 11, Implementation · pp. 11–12
Implementation
- Simka is implemented using the GATB C++ library, with support for standard computers and parallel execution on grid or cloud systems.The software is open source under the GNU Affero GPL license.Source: Implementation · pp. 11–12
Results
The HMP evaluations compare Simka’s resource use with other tools and assess its distances against read-based, taxonomic, and known biological structure. Simka scales to 690 samples and its distances correlate with alternative comparisons while recovering reported HMP patterns.
Performance Evaluation
- At N = 40, Simka was 6 times faster than MetaFast and 22 times faster than Commet for Bray-Curtis; Commet alone showed quadratic time growth.For Simka, disk usage was close to half the 11 GB input size at N = 40, while disk usage increased linearly for all four tools.Source: Performance Evaluation · p. 13, Figure 3 · p. 14
- On all 690 HMP samples, Simka completed in about 14 hours; MetaFast ran out of memory, Commet would require years for the full matrix, and Mash took 255 minutes.Simka computed numerous distances, including quantitative ones, over 15 billion distinct k-mers; Mash computed an approximate qualitative distance from a 10,000-k-mer subsample.Source: Performance Evaluation · p. 13, Table 2 · p. 15
- Filtering out singleton k-mers improved Simka’s computation time and disk usage without degrading distance quality on the HMP dataset.The filter removed 5% of the data by base pairs; after merging, solid distinct k-mers represented 15% of all distinct k-mers.Source: Performance Evaluation · p. 13
Evaluation of the distances
- Simka and Commet similarity measures had Spearman correlation r = 0.989 on 50 HMP samples.Figure 4 plots the percentage of matched k-mers from Simka against the percentage of matched reads from Commet, using k = 33.Source: Evaluation of the distances · p. 15, Figure 4 · p. 16
- Simka’s matched-k-mer percentages correlated with BLAT similar-read percentages at r > 0.89; the highest correlation was 0.987 for k = 21 versus BLAT at 95% identity.Larger k-mer sizes correlated better with higher BLAT identity thresholds, and vice versa.Source: Evaluation of the distances · pp. 15–16, Figure 5 · p. 17
- On HMP gut samples, Simka’s Bray-Curtis distances correlated with taxonomic distances at r = 0.89, compared with r = 0.51 for Mash.Simka’s results were robust for k > 15, with optimal correlation at k = 21; at k = 12, correlation fell to r = 0.5.Source: Evaluation of the distances · pp. 17–18, Figure 6 · p. 18
- Simka’s quantitative Ochiai distance separated full-HMP samples by body site, while different distances produced different sample distributions and cluster discrimination.This body-site separation was consistent with prior HMP studies.Source: Evaluation of the distances · p. 19
- Simka’s Jensen-Shannon distances recovered gut-sample gradients associated with Bacteroides, Prevotella, and Ruminococcaceae abundance.These gradients were visible in the PCoA despite Simka not having direct access to those taxonomic features.Source: Evaluation of the distances · p. 19
Discussions
Simka uses streamed multi-dataset k-mer counts to compute ecological distances, which recover biological structure similar to taxonomic comparisons on HMP data. The discussion also notes limits from k-mer-only estimates and dataset-dependent filtering choices.
Discussions
- The Multiple k-mer Count algorithm counts k-mers simultaneously across any number of datasets and streams per-k-mer counts for each dataset.This strategy underlies Simka’s ecological-distance computations across many large metagenomic datasets.Source: Discussions · p. 19
- Distance computation has time complexity O(W × N^2), where W is the number of distinct k-mers considered and N is the number of input samples.W may range into the hundreds of billions, while N is usually limited to dozens or hundreds and cannot be reduced.Source: Discussions · p. 19
- The solid filter sped computation without changing results in HMP tests, but may be undesirable for low-coverage samples or qualitative studies emphasizing rare species.The paper reports that Global Ocean Sampling structure was captured with or without the filter, while noting that threshold and k choices need assessment against dataset features.Source: Discussions · p. 20
- Adding a sample to an existing set requires recomputing the merge and distances, but leaves prior distances unchanged and needs only one matrix line, enabling linear-time addition.Source: Discussions · p. 22
- Different ecological distances capture different data features, and abundance-sensitive Bray-Curtis can reveal lung-disease structure absent with qualitative Jaccard.The paper also notes that community responses to stress or environmental change can be driven by increases in rare taxa.Source: Discussions · p. 22
- K-mer-only beta-diversity can bias distances downward through shared genomic regions or horizontal transfer, and upward through genome-size heterogeneity or within-genome k-mer variation.The authors contrast this with reference-based approaches that may be infeasible for complex ecosystems and say the de novo approach avoids reference-bank inconsistency and incompleteness.Source: Discussions · p. 22
- HMP k-mer-based and taxonomic distances correlate at r > 0.8 for k ≥21, and Simka recovers the same biological structure as taxonomic studies.The paper reports this as a result of numerical experiments on HMP datasets.Source: Discussions · p. 22
- Spaced seeds may improve distances by allowing mismatches between k-mers, especially for viral fractions rich in mutated sequences.The paper presents this as a potential improvement, not a tested result for Simka.Source: Discussions · pp. 22–23