Source-linked AI summary
Informed and Automated k-Mer Size Selection for Genome Assembly
Rayan Chikhi, Paul Medvedev
TL;DR
Genome assembly lacks a systematic way to choose k, despite k’s competing effects and the high cost of evaluating alternatives. KmerGenie samples k-mers to build approximate abundance histograms, fits models to estimate distinct genomic k-mers, and selects k accordingly. Its choices produced the best assemblies for two datasets and a good compromise for human chromosome 14, while the approach has limitations on uneven-coverage and multi-genome data.
Problem
De Bruijn-graph assembly lacks tools that quickly generate k-mer abundance histograms or automatically estimate the best k despite difficult trade-offs.
Method
KmerGenie samples k-mers for candidate k values, fits generative abundance models, and selects the k with the most estimated distinct genomic k-mers.
Results
KmerGenie’s selected k led to the best S. aureus and B. impatiens assemblies and a good chr14 assembly balancing contiguity with errors.
Takeaways & Limitations
Approximate histograms and automatic k selection provide a practical way to inform or automate assembly parameter choice across diverse datasets.
Takeaways & Limitations
KmerGenie may fail to identify a best k for uneven-coverage single-cell data or data from metagenomic and RNA-seq experiments.
Abstract
from arXiv · showhide
Genome assembly tools based on the de Bruijn graph framework rely on a parameter k, which represents a trade-off between several competing effects that are difficult to quantify. There is currently a lack of tools that would automatically estimate the best k to use and/or quickly generate histograms of k-mer abundances that would allow the user to make an informed decision. We develop a fast and accurate sampling method that constructs approximate abundance histograms with a several orders of magnitude performance improvement over traditional methods. We then present a fast heuristic that uses the generated abundance histograms for putative k values to estimate the best possible value of k. We test the effectiveness of our tool using diverse sequencing datasets and find that its choice of k leads to some of the best assemblies. Our tool KmerGenie is freely available at: http://kmergenie.bx.psu.edu/
1 INTRODUCTION
De Bruijn-graph assemblers depend critically on k, yet choosing it requires balancing competing effects and often relies on expert intervention. KmerGenie accelerates abundance-histogram analysis and heuristically selects k, producing strong assemblies across diverse datasets.
- 1 INTRODUCTION: Assembler performance depends on k, but current methods lack robust, systematic parameter-selection approaches.Assemblathon competitions showed that assembling a dataset still requires significant expert intervention.
- 1 INTRODUCTION: k balances repeat resolution, sequencing-error exposure, and overlap-induced coverage gaps.Larger k can span repeats but increases erroneous k-mers and can prevent overlapping reads from sharing graph vertices.
- 1 INTRODUCTION: Choosing k is difficult because existing bounds omit genome repetitiveness, heterozygosity, and read-error effects, while assembly comparisons are time-consuming.Histogram construction itself can take up to a day for one k value.
- 1 INTRODUCTION: KmerGenie samples k-mers to construct approximate abundance histograms and uses a heuristic selecting the k with the most distinct non-erroneous genomic k-mers.The tool can generate histograms for many k values and integrate automatic selection into assembly pipelines.
- 1 INTRODUCTION: KmerGenie’s selected k produced the best S. aureus and B. impatiens assemblies by NG50, and a chr14 assembly balancing contiguity and errors.The tool was tested on S. aureus, human chromosome 14, and B. impatiens.
2 METHODS
The method samples k-mers to build approximate abundance histograms, fits generative models separating genomic from erroneous k-mers, and selects the k maximizing distinct genomic k-mers. This objective reflects a trade-off between k-mer presence in reads and repetition in the reference.
- 2 METHODS: KmerGenie generates abundance histograms for many candidate k values, fits a model to each, and selects the k maximizing estimated genomic k-mers.The selected value is based on the estimated number of distinct genomic k-mers.
- 2 METHODS: An abundance histogram reports the number of distinct k-mers observed at each abundance value.For abundance i, it counts distinct k-mers appearing i times in the read multiset.
- 2 METHODS: Sampling uses a hash function to retain a controlled proportion of k-mers, then scales the sampled histogram to approximate the full histogram.The sampling parameter ε determines the proportion of distinct k-mers sampled.
- 2 METHODS: The sampling algorithm runs in O(|R|(ℓ−k)) time and uses expected O(m/ε) memory, reducing hash-table overhead and memory by a factor of ε.Here, ℓ is read length and m is the number of distinct k-mers.
- 2 METHODS: The abundance model mixes genomic and erroneous k-mer distributions, with genomic k-mers represented by copy-number-specific Gaussian components.The model includes haploid and diploid formulations, including homozygous and heterozygous components.
- 2 METHODS: Maximum-likelihood fitting estimates model parameters, after which the genomic-k-mer mixture weight estimates the number of distinct genomic k-mers.If d is the number of distinct observed k-mers and p̂e is the estimated erroneous-mixture weight, (1−p̂e)d estimates genomic k-mers.
- 2 METHODS: The method selects k by maximizing distinct genomic k-mers because larger k can resolve repeats, whereas smaller k is more likely to appear in reads but repeat more often.The optimum reflects imperfect coverage and sequencing errors rather than the ideal error-free, perfectly covered case.
3 RESULTS
KMERGENIE was evaluated on three sequencing datasets by comparing its predicted k values with assemblies, sampling accuracy, resource use, and related k-selection methods. Its predictions generally produced strong assemblies, while the sampling approach closely matched exact histograms and was substantially faster than exact counting.
- Assembly evaluation: KMERGENIE predicted k values of 31 for S. aureus, 71 for chr14, and 51 for B. impatiens, then evaluated assemblies across several k values.The tested candidates were 21, 31, 41, 51, 61, 71, and 81, using sampling frequency ϵ = 1000.
- Assembly evaluation: KMERGENIE’s chosen k produced the best NG50 and size for S. aureus but more errors, while chr14 showed a near-best assembly with significantly fewer errors.For B. impatiens, the chosen k produced the best NG50 and second-best size, but errors could not be measured because no reference was available.
- Assembly evaluation: Overall, KMERGENIE selected k values yielding the best assemblies for S. aureus and B. impatiens by NG50 and assembly size, and a compromise assembly for chr14.The chr14 choice traded off NG50 and assembly size against the number of errors.
- Runtime and resources: 6-10 times faster than DSK, KMERGENIE’s approximate histogram generation confirmed that sampling provides substantial speed-ups over exact k-mer counting.For B. impatiens, evaluating seven k values with seven threads required 3 hours, whereas one SOAPdenovo2 assembly at one k required approximately 30 CPU hours.
- Comparison with alternative methods: VelvetOptimizer required 30 assemblies and was infeasible for chr14 and B. impatiens, whereas Velvet Advisor’s recommendations produced very poor assemblies for S. aureus and B. impatiens.On S. aureus, VelvetOptimizer required about 20 hours and produced lower NG50 and more errors than KMERGENIE’s choice.
- Sampling and model fit: The sampled histogram closely followed the exact histogram and discriminated nearby k values when exact counts allowed that distinction.The comparison used k = 51 against exact distributions for k = 41 and k = 61 across S. aureus, chr14, and B. impatiens.
- Sampling and model fit: As k increased for chr14, the genomic abundance distribution shifted left and narrowed, increasing its overlap with the erroneous-k-mer distribution.The histogram combined distributions for erroneous and genomic k-mers; the figure’s logarithmic y-axis amplified differences at low abundances.
- K-mer prediction and assembly quality: Across all three organisms, NG50 rose and fell with the predicted number of distinct genomic k-mers, although the prediction overestimated reference k-mer counts.The overestimation may reflect heterozygosity not captured by the haploid reference or limitations in the statistical model or optimization.
4 DISCUSSION
KMERGENIE’s applicability is constrained by model fit, assembler type, and benchmark scope. The authors identify non-uniform coverage, non-de Bruijn assemblers, and broader assembly optimization as directions requiring further work.
- Limitations: KMERGENIE may fail to report a best k when its generative model cannot fit the abundance histograms.This can reflect model or optimization limits, or data that violate model assumptions.
- Limitations: Single-cell, metagenomic, and RNA-seq datasets can violate model assumptions or lack a single best k, although their histograms may still inform assembly choices.The authors note that combining assemblies from different k values can benefit some such datasets.
- Future work: The approach has been demonstrated for de Bruijn assemblers, while selecting the analogous overlap parameter for string overlap graph assemblers remains future work.The formal relation between the two parameters has not been established.
- Benchmark scope: The benchmark reflects typical single-assembler workflows rather than the best possible assembly for each organism.It did not optimize the Cartesian product of assemblers, error-correction methods, and k-mer values.
- Future work: Future work includes adapting the method to non-uniform coverage and improving the statistical model’s estimates of distinct genomic k-mers.The authors specifically identify metagenome and transcriptome applications and model accuracy as open directions.