FMtree: a fast locating algorithm of FM-indexes for genomic data

Area of Science:

• Bioinformatics
• Computational Biology
• Genomics

Background:

• Compressed full-text indexes, such as FM-indexes, accelerate pattern searching in large texts like genomic data.
• FM-indexes offer space efficiency but have limitations in locating all occurrences of patterns, especially those with many matches.

Purpose of the Study:

• To introduce FMtree, a novel locating algorithm designed to improve the efficiency of retrieving all occurrence positions of patterns using FM-indexes.
• To address the performance bottleneck in locating operations for FM-indexes, particularly for patterns with numerous occurrences.

Main Methods:

• FMtree organizes the search space into a conceptual multiway tree for locating pattern occurrences.
• The algorithm enables simultaneous retrieval of multiple occurrence positions by traversing this tree structure.
• This approach reduces redundant computations and enhances data locality compared to existing methods.

Main Results:

• FMtree demonstrates significantly faster performance in locating pattern occurrences, often achieving an order of magnitude improvement over state-of-the-art algorithms.
• The algorithm maintains memory efficiency while delivering substantial speedups.
• Experimental results validate the effectiveness and efficiency of the FMtree algorithm.

Conclusions:

• FMtree provides an efficient solution for the locating operation in FM-indexes, overcoming previous performance limitations.
• The tree-based approach offers a practical and memory-efficient method for pattern searching in large-scale biological sequence data.
• FMtree represents a valuable advancement for bioinformatics tools used in genomic data analysis.