Pfp-fm: an accelerated FM-index.

Area of Science:

• Bioinformatics
• Computational Biology
• Data Structures

Background:

• FM-indexes are essential for DNA alignment but can be slow due to random access requirements.
• Word-based indexes offer faster searches but require effective parsing of DNA sequences.
• Previous methods like induced suffix sorting improved performance for longer patterns.

Purpose of the Study:

• To introduce and evaluate a novel prefix-free parsing method for word-based FM-indexes.
• To demonstrate significant speedups in DNA sequence searching, particularly for shorter patterns.
• To compare the performance of prefix-free parsing against existing state-of-the-art methods.

Main Methods:

• Implemented a prefix-free parsing strategy to segment DNA sequences into variable-length phrases.
• Integrated this parsing method with FM-indexes to create a word-based index.
• Benchmarked the new word-based FM-index against standard FM-indexes and other parsing techniques.

Main Results:

• Achieved 3x to 18x speedup compared to competing methods on GRCh38.
• Demonstrated consistent performance gains on large SARS-CoV-2 genome datasets.
• Showed that prefix-free parsing accelerates counting queries for patterns of a few hundred characters.

Conclusions:

• Prefix-free parsing offers a significant performance improvement for word-based FM-indexes in DNA alignment.
• The method provides a substantial speedup over current state-of-the-art techniques with a modest memory overhead.
• This approach enhances the efficiency of genomic data analysis, especially for large-scale sequencing projects.