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 of HTSRs inducing an expected coverage depth of at most εκ across the genome (where ε>1 is a small 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. 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. Developed in C++, ROCK enables to observe fast running times using only a unique thread. To improve the digital normalization procedure, ROCK also implements two novel strategies: (i) downsampling the HTSRs based on their Phred scores, and (ii) implementing a final step that filters out low-covering HTSRs. Thanks to these improvements, ROCK can be used as a preprocessing step prior to performing fast genome de novo assembly. The source code is available under GNU Affero General Public License v3.0 at https://gitlab.pasteur.fr/vlegrand/ROCK.
[ In: Lemaitre C, Becker E, Derrien T (eds), Proceedings of JOBIM 2022, Posters & Demos, Rennes, France, 5-8 July, p. 21]