LROD: An Overlap Detection Algorithm for Long Reads Based on k-mer Distribution

Area of Science:

• Genomics
• Bioinformatics
• Computational Biology

Background:

• Third-generation sequencing technologies generate long DNA reads crucial for genome assembly.
• High error rates in these long reads pose significant challenges for accurate overlap detection.
• Existing methods struggle to reliably identify overlaps in noisy long-read data.

Purpose of the Study:

• To develop and validate a novel algorithm, Long-Read Overlap Detection (LROD), for accurate overlap detection in third-generation sequencing data.
• To improve the precision and recall of genome assembly by enhancing the accuracy of long-read overlap identification.
• To provide a robust solution for the challenging task of detecting overlaps in high-error long reads.

Main Methods:

• LROD filters common k-mers between long reads to simplify overlap detection.
• A two-stage strategy is employed to evaluate the consistency of common k-mers.
• A novel method refines candidate overlaps to determine true overlaps and correct errors.

Main Results:

• Experiments on simulated and real datasets demonstrate LROD's superior performance.
• LROD achieves higher F1-scores, precision, and recall compared to established methods like MHAP and Minimap2.
• The algorithm effectively handles the high error rates inherent in third-generation sequencing reads.

Conclusions:

• LROD significantly improves the accuracy of long-read overlap detection.
• The algorithm offers a more reliable approach for genome assembly using third-generation sequencing data.
• LROD represents a valuable advancement in bioinformatics tools for genomic research.