An efficient error correction algorithm using FM-index.

Area of Science:

• Genomics
• Bioinformatics
• Computational Biology

Background:

• High-throughput sequencing generates vast amounts of genomic data at lower costs.
• Sequencing errors, such as mismatches and indels, can compromise the accuracy of de novo genome assembly.
• Existing error correction methods often involve trade-offs between correction efficiency, accuracy, and computational speed.

Purpose of the Study:

• To develop a novel and efficient algorithm for correcting sequencing errors prior to genome assembly.
• To address the limitations of existing error correction methods by improving correction power, accuracy, and speed.

Main Methods:

• Developed a novel overlap-based error correction algorithm named FMOE, utilizing the FM-index data structure.
• FMOE identifies overlapping reads by aligning a query read against multiple compressed reads simultaneously.
• Error correction is performed using k-mer voting exclusively on identified overlapping reads.

Main Results:

• FMOE achieved the highest correction power among tested methods, with comparable accuracy and speed.
• The algorithm demonstrated superior performance on long-read sequencing datasets compared to short-read datasets.
• Genome assembly results indicated FMOE's effectiveness, especially for long or high-quality reads, highlighting its strengths in specific scenarios.

Conclusions:

• FMOE offers a powerful and efficient solution for sequencing error correction in genomics.
• The algorithm is particularly well-suited for long-read sequencing data, enhancing downstream genome assembly.
• The FMOE algorithm is publicly available for research use.