KmerStream

KmerStream estimates the number of distinct k-mers in high-throughput sequencing data to support genome assembly, error correction, and inference of genome size and sequencing error rates.

Key Features:

• Efficiency: Operates with time complexity linear in the input size and space complexity logarithmic in the input size, enabling scalable analysis of large high-throughput sequencing datasets.
• Streaming algorithm: Processes sequencing reads sequentially as a stream and counts k-mers (substrings of length k) without requiring storage of the entire dataset.
• Statistical insight: Constructs histograms of k-mer frequencies to reveal distribution characteristics of the sequenced data relevant to error rates and genome size.
• Error rate estimation: Employs a simple model using aggregate k-mer statistics to estimate sequencing error rates independently of reported quality values.
• Genome size estimation: Infers genome size from k-mer frequency data.

Scientific Applications:

• Genome assembly: Provides k-mer frequency distributions that inform assembly-related analyses.
• Error correction: Supports identification and correction of sequencing errors through error-rate estimates and k-mer frequency information.
• Sequencing quality assessment: Enables comparison of estimated error rates with reported quality values to assess run-to-run variability in sequencing experiments.
• Empirical application: Applied to a dataset of 2656 whole-genome sequenced individuals to compare KmerStream-estimated error rates with sequencing-reported quality values, revealing significant variability across sequencing runs.

Methodology:

Processes input sequentially as a streaming algorithm, constructs k-mer frequency histograms from the stream, and applies statistical models to aggregate k-mer statistics to derive estimates of sequencing error rates and genome size; reported computational complexities are linear time and logarithmic space relative to input size.