EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

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

Mikaël Salson iD, Arthur Boddaert, Awa Bousso Gueye, Laurent Bulteau, Yohan Hernandez-Courbevoie, Camille Marchet, Nan Pan, Sebastian Will iD, Yann Ponty iD

Bioinformatics · 2025

DOI: 10.1093/bioinformatics/btaf211 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Bioinformatics, 2025. Verfasst von Mikaël Salson und 8 weiteren Autor:innen. Beteiligte Einrichtung: Univ. Lille, CNRS, Centrale Lille, UMR 9189 CRIStAL, F-59000 Lille, France. Hauptthemen laut MEDLINE: SARS-CoV-2, Sequence Alignment, Genome, Viral, Software. Die Arbeit nennt 18 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: French Agence Nationale de la Recherche, INSSANE, Institut Français de Bioinformatique.

AbstractSchlagwörterBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Motivation Recent viral outbreaks motivate the systematic collection of pathogenic genomes in order to accelerate their study and monitor the apparition/spread of variants. Due to their limited length and temporal proximity of their sequencing, viral genomes are usually organized, and analyzed as oversized Multiple Sequence Alignments (MSAs). Such MSAs are largely ungapped, and mostly homogeneous on a column-wise level but not at a sequential level due to local variations, hindering the performances of sequential compression algorithms. Results In order to enable an efficient handling of MSAs, including subsequent statistical analyses, we introduce CREMSA (Column-wise Run-length Encoding for MSAs), a new index that builds on sparse bitvector representations to compress an existing or streamed MSA, all the while allowing for an expressive set of accelerated requests to query the alignment without prior decompression. Using CREMSA, a 65 GB MSA consisting of 1.9M SARS-CoV 2 genomes could be compressed into 22 MB using less than half a gigabyte of main memory, while executing access requests in the order of 100 ns. Such a speed up enables a comprehensive analysis of covariation over this very large MSA. We further assess the impact of the sequence ordering on the compressibility of MSAs and propose a resorting strategy that, despite the proven NP-hardness of an optimal sort, induces greatly increased compression ratios at a marginal computational cost. Availability and implementation CREMSA is freely accessible at https://gitlab.univ-lille.fr/cremsa/cremsa. The Snakemake workflow for the benchmarks is available at: https://gitlab.univ-lille.fr/cremsa/bench. The data used in the paper is on Zenodo at https://zenodo.org/records/14698859 and https://zenodo.org/records/15100011.

Schlagwörter

MeSH-Schlagwörter (MEDLINE)

SARS-CoV-2Sequence AlignmentGenome, ViralSoftwareData CompressionAlgorithmsCOVID-19Humans

Autor:innen und Institutionen

  • Univ. Lille, CNRS, Centrale Lille, UMR 9189 CRIStAL, F-59000 Lille, France.
  • Département d'Informatique, Lille University, F-59000 Lille, France.
  • CNRS UMR 8049 LIGM, Gustave Eiffel University, F-77420 Marne-la-Vallée, France.
  • CNRS UMR 7161 LIX, Ecole Polytechnique, Institut Polytechnique de Paris, F-91120 Palaiseau, France.

ORCID-Profile: Mikaël Salson, Sebastian Will, Yann Ponty

Förderung

  • French Agence Nationale de la Recherche
  • INSSANE
  • Institut Français de Bioinformatique
  • Programme d'Investissements d'Avenir
  • Programme d’Investissements d’Avenir

Zitieren

APA

Salson, M., Boddaert, A., Gueye, A. B., Bulteau, L., Hernandez-Courbevoie, Y., Marchet, C., Pan, N., Will, S., & Ponty, Y. (2025). CREMSA : compressed indexing of (ultra) large multiple sequence alignments. Bioinformatics. https://doi.org/10.1093/bioinformatics/btaf211

Vancouver

Salson M, Boddaert A, Gueye AB, Bulteau L, Hernandez-Courbevoie Y, Marchet C, et al. CREMSA : compressed indexing of (ultra) large multiple sequence alignments. Bioinformatics. 2025. doi:10.1093/bioinformatics/btaf211

BibTeX
@article{Salson2025,
  author = {Salson, Mikaël and Boddaert, Arthur and Gueye, Awa Bousso and Bulteau, Laurent and Hernandez-Courbevoie, Yohan and Marchet, Camille and Pan, Nan and Will, Sebastian and Ponty, Yann},
  title = {CREMSA : compressed indexing of (ultra) large multiple sequence alignments},
  journal = {Bioinformatics},
  year = {2025},
  doi = {10.1093/bioinformatics/btaf211}
}
Kostenlos starten →