PFP-FM: An Accelerated FM-index.

Area of Science:

• Bioinformatics
• Computational Biology
• Genomic Data Analysis

Background:

• FM-indexes are vital for DNA alignment but often require numerous random accesses per query character.
• Word-based FM-indexes offer faster searches but necessitate effective DNA parsing due to the absence of natural word boundaries.

Approach:

• This study introduces prefix-free parsing as an alternative to induced suffix sorting for creating word-based FM-indexes.
• The prefix-free parsing method allows parameter tuning to control average phrase length, optimizing index performance.

Key Points:

• Prefix-free parsing significantly accelerates FM-index searches for shorter patterns (a few hundred characters) compared to induced suffix sorting.
• The proposed method demonstrates 3x to 18x speedup on GRCh38 queries and consistent performance gains on large SARS-CoV-2 genome datasets.
• This approach enhances counting query performance across state-of-the-art methods with only a marginal increase in memory usage.

Conclusions:

• Prefix-free parsing offers a substantial performance improvement for FM-index-based DNA sequence searching.
• The method is efficient for various genomic datasets, including large-scale viral genome analyses.
• The PFP-FM source code is publicly available, facilitating further research and application.