Sketching and sampling approaches for fast and accurate long read classification

Area of Science:

• Bioinformatics
• Computational Biology
• Genomics

Background:

• Accurate read source identification is critical in sequencing, particularly for metagenomics and distinguishing contaminants.
• Long reads present challenges due to high error rates, complicating origin determination.
• Existing alignment-based tools often suffer from significant time and space overheads.

Purpose of the Study:

• To investigate the effectiveness of sampling and sketching approaches for read classification.
• To provide an efficient and accurate method for identifying the source of sequencing reads, especially long reads.
• To compare these novel methods against existing read classification tools.

Main Methods:

• Exploration of various sampling and sketching algorithms, including uniform sampling, MinHash variants, and a novel clustering-based approach.
• Generation of a reduced representation (screen) of potential source genomes for query readsets.
• Classification of reads based on their similarity to the generated screen.

Main Results:

• Sampling and sketching methods demonstrate high accuracy in identifying microbial genomes from metagenomic data.
• These techniques effectively distinguish between reads from target organisms and contaminants.
• The investigated approaches offer a viable alternative to traditional alignment and index-based methods.

Conclusions:

• Sampling and sketching techniques provide an effective and efficient solution for read classification.
• These methods are suitable for both metagenomic analysis and contaminant detection in sequencing data.
• A reference implementation is available, facilitating the adoption of these approaches.