A practical algorithm for finding maximal exact matches in large sequence datasets using sparse suffix arrays.

Area of Science:

• Bioinformatics
• Computational Biology
• Genomics

Background:

• High-throughput sequencing generates vast amounts of data, increasing demands on sequence analysis algorithms.
• Maximal exact matches (MEMs) are crucial for genome assembly and comparative genomics.
• Existing MEM algorithms struggle with the scale of modern sequencing data.

Purpose of the Study:

• To develop a novel algorithm for efficiently computing MEMs.
• To address the memory limitations of current MEM algorithms for large-scale sequence analysis.

Main Methods:

• Introduced a new MEM algorithm utilizing a sparse suffix array (SA).
• A sparse SA stores every K-th position, significantly reducing memory footprint compared to full text indexes.
• The algorithm compensates for the sparse index by incorporating partial matches and additional text scanning.

Main Results:

• The sparse SA-based algorithm achieves the same output as full text index algorithms under specific conditions.
• The algorithm demonstrates reduced memory usage, enabling MEM computation for significantly longer sequences.
• This method effectively trades increased computation for decreased memory consumption.

Conclusions:

• The novel sparse SA algorithm offers a memory-efficient solution for MEM computation.
• This advancement supports the analysis of larger datasets in high-throughput sequencing applications.
• The algorithm is available as open-source software and can replace existing MEM algorithms in tools like MUMmer 3.