Link to DOI – 10.21105/joss.03790
JOSS 2022 May;7(73):3790
Due to advances in high-throughput sequencing technologies, generating whole genome sequencing (WGS) data with high coverage depth (e.g. ≥ 500×) is now becoming common, especially when dealing with non-eukaryotic genomes. Such high coverage WGS data often fulfills the expectation that most nucleotide positions of the genome are sequenced a sufficient number of times without error. However, performing bioinformatic analyses (e.g. sequencing error correction, whole genome de novo assembly) on such highly redundant data requires substantial running times and memory footprint.
To reduce redundancy within a WGS dataset, randomly downsampling high-throughput sequencing reads (HTSR) is trivial. Nevertheless, this first-in-mind strategy is not efficient as it does not minimize variation in sequencing depth, thereby eroding the coverage depth of genome regions that are under-covered (if any). To cope with this problem, a simple greedy algorithm, named digital normalization, was designed to efficiently downsample HTSRs over genome regions that are over-covered. Given an upper-bound threshold κ > 1, it returns a subset Sκ such that the coverage depth induced by the HTSRs in Sκ is expected to be at most εκ across genome (where ε > 1 is a constant). By discarding highly redundant HTSRs while retaining sufficient and homogeneous coverage depth (≈ εκ), this algorithm strongly decreases both running times and memory required to subsequently analyze WGS data, with often little impact on the expected results.
Interestingly, the digital normalization algorithm can be easily enhanced in several ways, so that the final subset contains fewer but more qualitative HTSRs. Unfortunately, these different improvements are scattered in distinct program tools. ROCK (Reducing Over-Covering K-mers) was therefore developed with the key purpose of implementing a fast, accurate and easy-to-use digital normalization procedure. It was designed to be used as a preprocessing step prior to performing fast genome de novo assembly. The C++ source code is available under GNU Affero General Public License v3.0 at https://gitlab.pasteur.fr/vlegrand/ROCK.