SPRISS: Approximating Frequent K-mers by Sampling Reads, and Applications

Overview

Journal Bioinformatics

Publisher Oxford University Press

Specialty Biology

Date 2022 May 18

PMID 35583271

Authors

Diego Santoro

Leonardo Pellegrina

Matteo Comin

Fabio Vandin

Affiliations

Soon will be listed here.

Abstract

Motivation: The extraction of k-mers is a fundamental component in many complex analyses of large next-generation sequencing datasets, including reads classification in genomics and the characterization of RNA-seq datasets. The extraction of all k-mers and their frequencies is extremely demanding in terms of running time and memory, owing to the size of the data and to the exponential number of k-mers to be considered. However, in several applications, only frequent k-mers, which are k-mers appearing in a relatively high proportion of the data, are required by the analysis.

Results: In this work, we present SPRISS, a new efficient algorithm to approximate frequent k-mers and their frequencies in next-generation sequencing data. SPRISS uses a simple yet powerful reads sampling scheme, which allows to extract a representative subset of the dataset that can be used, in combination with any k-mer counting algorithm, to perform downstream analyses in a fraction of the time required by the analysis of the whole data, while obtaining comparable answers. Our extensive experimental evaluation demonstrates the efficiency and accuracy of SPRISS in approximating frequent k-mers, and shows that it can be used in various scenarios, such as the comparison of metagenomic datasets, the identification of discriminative k-mers, and SNP (single nucleotide polymorphism) genotyping, to extract insights in a fraction of the time required by the analysis of the whole dataset.

Availability And Implementation: SPRISS [a preliminary version (Santoro et al., 2021) of this work was presented at RECOMB 2021] is available at https://github.com/VandinLab/SPRISS.

Supplementary Information: Supplementary data are available at Bioinformatics online.

Citing Articles

SPRISS: approximating frequent k-mers by sampling reads, and applications.

Santoro D, Pellegrina L, Comin M, Vandin F Bioinformatics. 2022; 38(13):3343-3350.

PMID: 35583271 PMC: 9237683. DOI: 10.1093/bioinformatics/btac180.

References

Li H, Durbin R . Fast and accurate short read alignment with Burrows-Wheeler transform. Bioinformatics. 2009; 25(14):1754-60. PMC: 2705234. DOI: 10.1093/bioinformatics/btp324. View

Zhang Z, Wang W . RNA-Skim: a rapid method for RNA-Seq quantification at transcript level. Bioinformatics. 2014; 30(12):i283-i292. PMC: 4058932. DOI: 10.1093/bioinformatics/btu288. View

Wedemeyer A, Kliemann L, Srivastav A, Schielke C, Reusch T, Rosenstiel P . An improved filtering algorithm for big read datasets and its application to single-cell assembly. BMC Bioinformatics. 2017; 18(1):324. PMC: 5496428. DOI: 10.1186/s12859-017-1724-7. View

Danovaro R, Canals M, Tangherlini M, DellAnno A, Gambi C, Lastras G . A submarine volcanic eruption leads to a novel microbial habitat. Nat Ecol Evol. 2017; 1(6):144. DOI: 10.1038/s41559-017-0144. View

Roy R, Bhattacharya D, Schliep A . Turtle: identifying frequent k-mers with cache-efficient algorithms. Bioinformatics. 2014; 30(14):1950-7. DOI: 10.1093/bioinformatics/btu132. View

Harris R, Medvedev P . Improved representation of sequence bloom trees. Bioinformatics. 2019; 36(3):721-727. PMC: 8215923. DOI: 10.1093/bioinformatics/btz662. View

Elworth R, Wang Q, Kota P, Barberan C, Coleman B, Balaji A . To Petabytes and beyond: recent advances in probabilistic and signal processing algorithms and their application to metagenomics. Nucleic Acids Res. 2020; 48(10):5217-5234. PMC: 7261164. DOI: 10.1093/nar/gkaa265. View

Li H . A statistical framework for SNP calling, mutation discovery, association mapping and population genetical parameter estimation from sequencing data. Bioinformatics. 2011; 27(21):2987-93. PMC: 3198575. DOI: 10.1093/bioinformatics/btr509. View

Marchet C, Boucher C, Puglisi S, Medvedev P, Salson M, Chikhi R . Data structures based on -mers for querying large collections of sequencing data sets. Genome Res. 2020; 31(1):1-12. PMC: 7849385. DOI: 10.1101/gr.260604.119. View

10.

Numanagic I, Bonfield J, Hach F, Voges J, Ostermann J, Alberti C . Comparison of high-throughput sequencing data compression tools. Nat Methods. 2016; 13(12):1005-1008. DOI: 10.1038/nmeth.4037. View

11.

Kelley D, Schatz M, Salzberg S . Quake: quality-aware detection and correction of sequencing errors. Genome Biol. 2010; 11(11):R116. PMC: 3156955. DOI: 10.1186/gb-2010-11-11-r116. View

12.

Sun C, Medvedev P . Toward fast and accurate SNP genotyping from whole genome sequencing data for bedside diagnostics. Bioinformatics. 2018; 35(3):415-420. DOI: 10.1093/bioinformatics/bty641. View

13.

Pellegrina L, Pizzi C, Vandin F . Fast Approximation of Frequent -Mers and Applications to Metagenomics. J Comput Biol. 2020; 27(4):534-549. DOI: 10.1089/cmb.2019.0314. View

14.

Kokot M, Dlugosz M, Deorowicz S . KMC 3: counting and manipulating k-mer statistics. Bioinformatics. 2017; 33(17):2759-2761. DOI: 10.1093/bioinformatics/btx304. View

15.

Salmela L, Walve R, Rivals E, Ukkonen E . Accurate self-correction of errors in long reads using de Bruijn graphs. Bioinformatics. 2016; 33(6):799-806. PMC: 5351550. DOI: 10.1093/bioinformatics/btw321. View

16.

Dickson L, Jiolle D, Minard G, Moltini-Conclois I, Volant S, Ghozlane A . Carryover effects of larval exposure to different environmental bacteria drive adult trait variation in a mosquito vector. Sci Adv. 2017; 3(8):e1700585. PMC: 5559213. DOI: 10.1126/sciadv.1700585. View

17.

Yu Y, Liu J, Liu X, Zhang Y, Magner E, Lehnert E . SeqOthello: querying RNA-seq experiments at scale. Genome Biol. 2018; 19(1):167. PMC: 6194578. DOI: 10.1186/s13059-018-1535-9. View

18.

Pandey P, Bender M, Johnson R, Patro R, Berger B . Squeakr: an exact and approximate k-mer counting system. Bioinformatics. 2018; 34(4):568-575. DOI: 10.1093/bioinformatics/btx636. View

19.

Zhang Q, Pell J, Canino-Koning R, Howe A, Brown C . These are not the k-mers you are looking for: efficient online k-mer counting using a probabilistic data structure. PLoS One. 2014; 9(7):e101271. PMC: 4111482. DOI: 10.1371/journal.pone.0101271. View

20.

Sherry S, Ward M, Kholodov M, Baker J, Phan L, Smigielski E . dbSNP: the NCBI database of genetic variation. Nucleic Acids Res. 2000; 29(1):308-11. PMC: 29783. DOI: 10.1093/nar/29.1.308. View