Overlap detection on long, error-prone sequencing reads via smooth q-gram

Area of Science:

• Genomics
• Bioinformatics
• Computational Biology

Background:

• Third-generation sequencing (PacBio, Nanopore) produces long, error-prone reads.
• Accurate overlap detection is crucial for de novo fragment assembly.
• Current methods struggle with high error rates and short overlaps.

Purpose of the Study:

• To address limitations in overlap detection for error-prone sequencing reads.
• To develop a novel algorithm for improved overlap detection accuracy.

Main Methods:

• Proposed 'smooth q-gram', a q-gram variant capturing pairs within small edit distances.
• Designed a novel algorithm utilizing smooth q-gram-based seeds for overlap detection.
• Implemented and tested the algorithm on PacBio and Nanopore datasets.

Main Results:

• The smooth q-gram algorithm outperforms existing q-gram-based methods.
• Significant improvements observed particularly for reads with short overlapping lengths.
• Demonstrated enhanced precision and recall in overlap detection.

Conclusions:

• The novel smooth q-gram approach offers superior performance for overlap detection.
• This method is particularly beneficial for analyzing challenging, error-prone sequencing data.
• The developed algorithm advances fragment assembly for third-generation sequencing.