Source-linked AI summary
A Reference-Free Algorithm for Computational Normalization of Shotgun Sequencing Data
C. Titus Brown, Adina Howe, Qingpeng Zhang, Alexis B. Pyrkosz, Timothy H. Brom
TL;DR
Deep shotgun sequencing faces sampling variation, high error rates, and computational demands that grow with sequencing throughput. The paper introduces reference-free digital normalization, a single-pass method that systematizes coverage while removing redundant reads and errors. It reports substantially reduced data size and de novo assembly memory and time requirements without significantly affecting contig content, across several genomic and transcriptomic data sets.
Problem
Sampling variation, high sequencing error rates, and rapidly growing shotgun data sets create computational challenges for short-read analysis and assembly.
Method
Digital normalization is a reference-free, single-pass algorithm that progressively removes high-coverage reads to normalize coverage and reduce redundant data and errors.
Results
Digital normalization substantially reduces shotgun data size and de novo assembly memory and time requirements without significantly affecting assembly results.
Takeaways & Limitations
The method supports lower-cost de novo assembly while retaining nearly all real k-mers and applying across genomic, single-cell, and transcriptomic data.
Takeaways & Limitations
Digital normalization can remove real transcriptomic k-mers when coverage is insufficient, and Trinity may fragment long transcripts after normalization.
Abstract
from arXiv · showhide
Deep shotgun sequencing and analysis of genomes, transcriptomes, amplified single-cell genomes, and metagenomes has enabled investigation of a wide range of organisms and ecosystems. However, sampling variation in short-read data sets and high sequencing error rates of modern sequencers present many new computational challenges in data interpretation. These challenges have led to the development of new classes of mapping tools and {\em de novo} assemblers. These algorithms are challenged by the continued improvement in sequencing throughput. We here describe digital normalization, a single-pass computational algorithm that systematizes coverage in shotgun sequencing data sets, thereby decreasing sampling variation, discarding redundant data, and removing the majority of errors. Digital normalization substantially reduces the size of shotgun data sets and decreases the memory and time requirements for {\em de novo} sequence assembly, all without significantly impacting content of the generated contigs. We apply digital normalization to the assembly of microbial genomic data, amplified single-cell genomic data, and transcriptomic data. Our implementation is freely available for use and modification.
Introduction
Short-read shotgun analysis is challenged by sampling variation, high sequencing error rates, and data volumes that can exceed computational capacity. Digital normalization addresses these challenges with a reference-free, single-pass approach that reduces data and errors while supporting de novo assembly across multiple data types.
- Research challenges: Deep shotgun sequencing is needed for complete sampling, producing data sets that can reach 300 GB or more for human genomes.Rare molecules in transcriptomes and metagenomes can similarly determine the required sequencing depth.
- Research challenges: Sequencing errors accumulate with data volume, create computationally expensive novelty, and complicate short-read analysis.The Illumina GAII, for example, had a reported 1–2% error rate.
- Research challenges: Large data sets and high error rates can make generated sequencing data difficult to analyze as sequencing capacity outpaces computational capacity.The paper identifies new algorithmic approaches as necessary alongside emerging hardware-based scaling.
- Existing approaches: Existing tools include ultra-fast reference-alignment methods and de novo assemblers designed to store and assemble large amounts of short-read data.Examples of assemblers include ABySS, Velvet, SOAPdenovo, ALLPATHS, SGA, and Cortex.
- Proposed approach: Digital normalization is a reference-free, single-pass algorithm that removes high-coverage reads, normalizes coverage, and eliminates many errors after sequencing.The authors report reduced de novo assembly requirements while retaining recoverable abundance information from unnormalized reads.
- Evaluation: A fixed-memory implementation runs in time linear with input size and is evaluated on genomic, single-cell, and transcriptomic data sets.The evaluation includes E. coli, two single-cell MD-amplified microbial genomes, and yeast and mouse mRNAseq.
Results
Digital normalization estimates coverage from k-mer abundance, reduces redundant and erroneous data, and generally preserves assembly sequence content while lowering computational demands. Its effects vary by sample and assembler, with transcriptome edge effects and long-transcript fragmentation defining important boundaries.
- Coverage and reference-free estimation: 100x sampling may be required for at least 90% human-genome recovery in contigs over 1 kb, making redundant reads a major assembly burden.Traditional coverage estimation requires mapping reads to an assembly.
- Coverage and reference-free estimation: Median k-mer abundance correlates with mapping-based coverage across simulated and real genomic and transcriptomic data.Reported r2 values range from 0.79 to 0.93 across the four tested settings.
- Coverage normalization: After normalization to k-mer coverage 20, high-coverage loci shifted to average mapping coverage 26 while lower-coverage loci retained their coverage.This smoothed the overall coverage distribution in E. coli and two amplified single-cell data sets.
- Coverage normalization: At 5 million E. coli reads, fewer than 30% of new reads were retained when normalizing at C=20 and k=20.Retention declined as more reads were examined, indicating saturation of newly observed information or errors.
- Error reduction: At 200x simulated genomic coverage, 1% errors produced approximately 20 new k-mers per error, while normalization discarded 80% of reads containing 62% of errors.The procedure retained nearly all real k-mers while discarding most erroneous k-mers.
- Genome and transcriptome assembly: Transcriptome effects included 0.7% real-k-mer loss near sequence ends in simulation and possible fragmentation of long transcripts by Trinity.The authors suggest k-mer-size mismatch or greater sensitivity to coverage changes as possible explanations for Trinity’s behavior.
- Genome and transcriptome assembly: The Deltaproteobacteria normalized assembly had 98.8% sequence overlap with the prior assembly, with additional contigs likely representing real sequence.For transcriptomes, normalized assemblies retained 98.5% and 97% overlap for Oases and Trinity, respectively, but Oases lost 5–10% of transcripts and bases.
- Genome and transcriptome assembly: Normalization reduced assembly resources, but Trinity’s mouse runtime fell threefold without a significant memory reduction.The authors associate this difference with transcriptome size and lower overall coverage.
Discussion
Digital normalization reduces redundant and erroneous sequencing data while preserving most real k-mer content, lowering assembly costs and enabling scalable reference-free analysis. Its benefits come with scope limits involving repeats, polymorphism, low-abundance transcripts, terminal k-mers, and assembler-specific behavior.
- Computational benefits: Digital normalization substantially lowers de novo assembly time and memory without substantially affecting assembly results.It removes most reads while preserving true k-mer content and eliminating errors that would otherwise increase memory use.
- Information retention: Digital normalization retains nearly all real k-mers while discarding most erroneous k-mers, reducing data without substantially reducing information.Discarding redundant reads also removes sequencing errors contained in those reads.
- Core strategy: Per-locus downsampling systematizes coverage without requiring prior knowledge of reference loci.The single-pass procedure progressively filters reads using a partial data sketch rather than considering the entire data set at once.
- Broader uses: The approach supports streaming and reference-free coverage or diversity analysis for data sets too large to store or lacking reference sequences.Fixed-memory sketches and reference-free per-read coverage estimates extend its use beyond preprocessing for assembly.
- Broader uses: Digital normalization may enable more computationally expensive assembly approaches by reducing data-set size, memory requirements, and contig-assembly time.The discussion specifically identifies overlap-layout-consensus assembly as a possible beneficiary for short-read data.
- Limitations: The method can discard terminal k-mers and low-abundance isoforms and may perform worse on highly polymorphic or highly repetitive data.It also aggressively removes abundance information and has not been adapted to paired-end data sets.
- Limitations: With sufficiently deep sequencing, erroneous sequences may accumulate and become difficult for k-mer methods to distinguish from error-free sequences.The authors identify local-alignment-based coverage estimation as a possible future direction.
Methods
The implementation uses fixed-memory and streaming components to process sequencing data, with datasets and assemblies drawn from published, simulated, and computationally generated sources. Coverage, k-mer counts, assembly overlap, runtime, and memory were measured using specified mapping, counting, alignment, and monitoring procedures.
- Data sets: Published E. coli, S. aureus, Deltaproteobacteria, mouse, and yeast data sets were used without modification.Complete pre- and post-normalization assemblies were made available electronically.
- Data sets: Simulated genome and transcriptome data used 100-base reads, with the genome at estimated 200x coverage and a random 1% per-base error rate.The simulated genome was 400,000 bases; the transcriptome contained 100 transcripts of length 500.
- Implementation: Digital normalization and k-mer analyses were implemented with khmer, while analysis summaries and simulated data were generated by Python scripts.The software and scripts were made available through the cited project repositories.
- Assembly and analysis: Assemblies used Velvet for genomes and Oases or Trinity for transcriptomes, with figures and correlations generated using matplotlib, numpy, and IPython.The listed software versions were fixed for the reported analyses.
- Implementation: The khmer implementation counted k-mers with a fixed-memory CountMin Sketch and used k=20 by default.Memory was set so the calculated false positive rate remained below 0.01.
- Measurements: Coverage was estimated by Bowtie mapping and per-base averaging, while median k-mer counts were computed with khmer.Reads mapped to multiple locations were assigned a random reference location for coverage computation.
- Measurements: Assembly overlap was measured with filtered NCBI BLASTN alignments and normalized against self-by-self BLASTN overlap identity.Deltaproteobacteria SAR324 sequences were additionally compared with TBLASTX.
- Measurements: Execution time used Linux bash real time, while peak memory was estimated with memusg or the Torque monitor.Normalized and unnormalized comparisons were always run on the same machine.
Figure Legends
Figure 1 compares rank-abundance distributions of 20-mers from error-free reads with reads containing single or multiple substitution errors.
- The distributions contrast 20-mer abundance patterns for 100-base reads with no errors, one substitution error, or multiple substitution errors.
Tables
The figures and tables assess k-mer coverage estimation, normalization effects on coverage and errors, and computational requirements for genomic and transcriptomic assembly.
- Error reduction: Digital normalization to C=20 removes many erroneous k-mers while tracking true k-mers lost at each processing step.
- Coverage estimation: Mapping-based and k-mer coverage measures correlate for simulated genomes and real E. coli data, with r2 = 0.79 and r2 = 0.80.
- Error reduction: Three-pass digital normalization removes most erroneous k-mers, with true-k-mer losses quantified against known references.
- Coverage estimation: Mapping-based and k-mer coverage measures correlate for simulated transcriptomes and real mouse transcriptomes, with r2 = 0.93 and r2 = 0.90.
- Assembly requirements: Three-pass digital normalization reduces computational requirements for genomic contig assembly.
- Coverage normalization: Before-and-after coverage distributions show normalization of three microbial genome samples at k=20 and C=20.
- Assembly requirements: Single-pass normalization to C=20 reduces computational requirements for transcriptome assembly.