E-MEM: efficient computation of maximal exact matches for very large genomes

Area of Science:

• Bioinformatics
• Computational Biology
• Genomics

Background:

• Genome alignment relies on maximal exact matches (MEMs) for identifying homologous regions.
• Current MEM computation algorithms face challenges with large genomes due to high memory usage and inefficient parallelization.
• Existing methods often utilize full-text indexes, limiting scalability.

Purpose of the Study:

• To develop a novel, efficient algorithm for computing MEMs in large genomes.
• To overcome the memory and parallelization limitations of existing MEM computation methods.
• To provide a scalable solution for whole-genome alignment.

Main Methods:

• Introduced the efficient computation of MEMs (E-MEM) algorithm.
• E-MEM avoids the use of full-text indexes.
• The algorithm is designed for high parallelization and reduced memory footprint.

Main Results:

• E-MEM computes MEMs between human and mouse genomes in 10 minutes using only 2 GB of memory on a 12-core machine.
• Memory requirements can be as low as 600 MB.
• The algorithm demonstrates efficient performance on genomes of any size.

Conclusions:

• E-MEM offers a significant improvement over existing MEM computation algorithms.
• The algorithm is suitable for analyzing large-scale genomic datasets.
• E-MEM provides a scalable and memory-efficient solution for genome alignment.