CREMSA: compressed indexing of (ultra) large multiple sequence alignments

Area of Science:

• Bioinformatics
• Genomics
• Computational Biology

Background:

• Viral outbreaks necessitate rapid collection and analysis of pathogenic genomes.
• Large Multiple Sequence Alignments (MSAs) of viral genomes pose storage and analysis challenges due to their size and local variations.
• Existing sequential compression algorithms are inefficient for MSAs.

Purpose of the Study:

• To introduce CREMSA (Column-wise Run-length Encoding for MSAs), an efficient compression method for large MSAs.
• To enable accelerated querying of compressed MSAs without decompression.
• To facilitate comprehensive statistical analyses, including covariation studies, on massive genomic datasets.

Main Methods:

• Developed CREMSA, utilizing sparse bitvector representations for compression.
• Implemented a resorting strategy to improve MSA compressibility.
• Benchmarked CREMSA performance on a large SARS-CoV-2 MSA.

Main Results:

• CREMSA compressed a 65 GB MSA (1.9M SARS-CoV-2 genomes) to 22 MB using <0.5 GB RAM.
• Query access times were reduced to approximately 100 ns.
• The proposed resorting strategy significantly increased compression ratios with minimal computational overhead.

Conclusions:

• CREMSA provides a highly efficient solution for compressing and querying large viral MSAs.
• The method enables faster and more comprehensive genomic data analysis.
• CREMSA is freely accessible, promoting its adoption in pathogen surveillance and research.