An Efficient Parallel Sketch-Based Algorithmic Workflow for Mapping Long Reads.

Area of Science:

• Genomics
• Bioinformatics
• Computational Biology

Background:

• Long read sequencing technologies are rapidly advancing, producing high-accuracy reads over 10 Kbp.
• Genomic assembly and scaffolding rely heavily on mapping long reads, a computationally intensive step.
• Current mapping tools often use overlap computations, which can be slow for large datasets; alignment-free methods are needed.

Purpose of the Study:

• To develop a fast and accurate alignment-free method for mapping long reads to reference sequences.
• To address the computational bottleneck in long read mapping for genomic assembly and scaffolding.
• To present JEM-mapper, an efficient parallel algorithmic workflow for long read mapping.

Main Methods:

• Developed JEM-mapper, utilizing a novel minimizer-based Jaccard estimator (JEM) sketch for alignment-free mapping.
• Implemented a parallel version of JEM-mapper using MPI+OpenMP for distributed- and shared-memory parallelism.
• Evaluated JEM-mapper in two settings: hybrid scaffolding (long reads to contigs) and classical long read assembly (long reads to long reads).

Main Results:

• JEM-mapper achieves high-quality mapping with demonstrated precision and recall rates.
• In a hybrid scaffolding scenario with a large genome, JEM-mapper achieved 99.41% precision and 97.91% recall.
• JEM-mapper demonstrated a 6.9x speedup over state-of-the-art mappers in the hybrid setting, significantly improving time to solution.

Conclusions:

• JEM-mapper provides an efficient and accurate solution for the long read mapping bottleneck in genomics.
• The parallel implementation enables scalability for large-scale genomic analyses.
• JEM-mapper advances the field of long read sequencing analysis, facilitating faster and more comprehensive genome assembly and scaffolding.