Source-linked AI summary
BayesHammer: Bayesian clustering for error correction in single-cell sequencing
Sergey I. Nikolenko, Anton I. Korobeynikov, Max A. Alekseyev
TL;DR
Single-cell sequencing creates difficult error-correction conditions because coverage is extremely non-uniform and conventional tools often underperform. BayesHammer combines Hamming-graph algorithms with Bayesian subclustering, and the paper reports improved assembly results, especially for single-cell E. coli, alongside faster processing and smaller resulting k-mer sets. The authors also identify scope boundaries and propose further general approaches.
Problem
Single-cell sequencing has highly non-uniform coverage, while standard multi-cell error-correction tools usually come up short and single-cell methods have been simplistic.
Method
BayesHammer combines Hamming-graph processing and Bayesian subclustering in an error-correction pipeline based on the ideas of Hammer.
Results
BayesHammer improves assembly results, especially for single-cell E. coli, while producing fewer resulting k-mers that reduce de Bruijn graph size and assembly running time.
Takeaways & Limitations
The tool improves on existing error-correction tools for multi-cell data and is significantly faster than other tools in the reported experiments, except Hammer.
Takeaways & Limitations
The authors note that a new general approach remains to be tried beyond the current approach.
Abstract
from arXiv · showhide
Error correction of sequenced reads remains a difficult task, especially in single-cell sequencing projects with extremely non-uniform coverage. While existing error correction tools designed for standard (multi-cell) sequencing data usually come up short in single-cell sequencing projects, algorithms actually used for single-cell error correction have been so far very simplistic. We introduce several novel algorithms based on Hamming graphs and Bayesian subclustering in our new error correction tool BayesHammer. While BayesHammer was designed for single-cell sequencing, we demonstrate that it also improves on existing error correction tools for multi-cell sequencing data while working much faster on real-life datasets. We benchmark BayesHammer on both $k$-mer counts and actual assembly results with the SPAdes genome assembler.
Methods Notation and outline
BayesHammer processes k-mer statistics through Hamming-graph component construction, Bayesian subclustering, solid-k-mer selection and expansion, then read correction by majority vote. Its graph processing uses partial lexicographic orderings and adaptive block handling to identify nearby k-mers efficiently.
- Workflow: BayesHammer records each k-mer’s count, sequencing-error quality, and per-position error-probability vector before graph processing.The statistics are computed from all k-mer occurrences without storing every instance in memory, using hash-based auxiliary files and lexicographic sorting.
- Bayesian subclustering: Connected components are Bayesian-subclustered by Hamming distance, using low-error k-mers as initial centers and stopping when the penalized objective no longer increases.The selected clustering maximizes a likelihood-based score penalized by model complexity and cluster count.
- Solid k-mers and correction: Cluster centers whose total quality exceeds a strict threshold become solid k-mers, which are iteratively expanded by mapping them to reads.Reads fully covered by solid k-mers cause all their k-mers to be marked solid; corrected reads use majority votes from solid k-mers and may undergo another iteration if changes are substantial.
- Hamming graph construction: Hamming-graph vertices are k-mers, with edges joining pairs whose Hamming distance is at most τ.The construction partitions k-mer positions into τ + 1 parts, guaranteeing a shared subsequence in one part for sufficiently similar k-mers.
- Hamming graph construction: Partial lexicographic orderings group k-mers sharing subsequences, allowing small equivalence blocks to be checked directly and large blocks to be recursively repartitioned.BayesHammer uses contiguous and strided index partitions and maintains connected components with a disjoint-set data structure.
Results and discussion
Across three datasets, BayesHammer was evaluated with k = 21 using k-mer statistics, read-error reduction, and SPAdes assemblies. It was faster than other correction tools and improved assembly results, including in multi-cell data where Quake had better k-mer statistics.
- Datasets and setup: Three datasets comprised single-cell E. coli, single-cell S. aureus, and multi-cell E. coli reads, with both E. coli datasets averaging ≈600× coverage.Coverage was highly non-uniform in the single-cell E. coli dataset.
- Datasets and setup: BayesHammer used k = 21 throughout, while higher k values produced no improvements in the experiments.The same k value was used for the correction experiments and the position-specific error analysis.
- Runtime and correction statistics: BayesHammer was significantly faster than other error correction tools, except Hammer, which was a strict subset of its processing.In the single-cell case, it also produced fewer resulting k-mers, leading to smaller de Bruijn graphs and shorter total assembly time.
- Assembly results: BayesHammer’s correction improved assembly results significantly, especially for single-cell E. coli.All assemblies were performed with SPAdes, and the evaluation included assembly metrics such as N50, NG50, and NA50.
- Assembly results: In multi-cell data, BayesHammer improved assembly over Quake-corrected reads despite losing to Quake by k-mer statistics.The assembly improvements included genome coverage and the number of genes.
- Error reduction: Error-rate graphs compared reduction by read position across the three datasets, but error counting was available only for the multi-cell E. coli dataset.The graphs were biased toward reads that actually aligned to the genome.
Conclusions
The paper develops BayesHammer from Hammer’s ideas through Bayesian clustering to address single-cell k-mer multiplicity and error-correction challenges. It reports improvements over existing error-correction tools while identifying model realism, contamination, and future algorithmic enhancements as remaining concerns.
- Single-cell datasets lack a simple k-mer multiplicity distribution, requiring k-mers to be analyzed individually and clusters separately.
- BayesHammer extends Hammer through Bayesian clustering and makes the approach practical for error correction.
- BayesHammer yields significant improvements over existing error-correction tools.
- The underlying models remain imperfect because future work could learn a non-uniform single-nucleotide error distribution for the likelihood formulas.
- The authors observed significant human DNA contamination in a single-cell dataset and identify removing such contamination as a natural improvement.
- Further work includes minimizers for potentially reducing memory requirements and addressing paired information.