A Fast Approximate Algorithm for Mapping Long Reads to Large Reference Databases.

Area of Science:

• Genomics
• Bioinformatics
• Computational Biology

Background:

• Single-molecule sequencing technologies (e.g., PacBio, Oxford Nanopore) necessitate advanced long-read mapping algorithms.
• Existing methods face a trade-off between accuracy (alignment-based) and scalability (alignment-free).
• Limited scalability and precision hinder the analysis of large genomic datasets generated by new sequencing platforms.

Purpose of the Study:

• To develop a scalable and precise long-read mapping algorithm for single-molecule sequencing data.
• To establish a mathematical framework for defining mapping targets and estimating statistical significance.
• To create an algorithm that adapts to varying mapping requirements and provides detailed positional and identity estimates.

Main Methods:

• Combined a fast approximate read mapping algorithm using minimizers with a MinHash identity estimation technique.
• Developed a mathematical framework for p-value and sensitivity estimation, defining mapping target types.
• Demonstrated tolerance for alignment error rates up to 20%.

Main Results:

• Achieved both scalability and precision, outperforming existing methods.
• For human PacBio reads mapped to hg38, the method was 290x faster than BWA-MEM with 96% recall and lower memory usage.
• Demonstrated scalability by mapping large, noisy PacBio reads to the complete NCBI RefSeq database (838 Gbp).

Conclusions:

• The novel algorithm offers a significant advancement in long-read mapping, balancing speed and accuracy.
• The developed mathematical framework provides robust statistical estimates for mapping results.
• The method is highly scalable and suitable for analyzing large datasets from emerging sequencing technologies.