Conway–Bromage–Lyndon (CBL): an exact, dynamic representation of k -mer sets
Bioinformatics · 28.06.2024 · 40 (Supplement_1) · i48-i57
DOI: 10.1093/bioinformatics/btae217 ↗Kurz gefasst
Fachartikel in der Zeitschrift Bioinformatics, online erschienen am 28.06.2024. Verfasst von Igor Martayan und 3 weiteren Autor:innen. Beteiligte Einrichtung: Univ. Lille, CNRS, Centrale Lille, UMR 9189 CRIStAL, Lille, F-59000, France. Hauptthemen laut MEDLINE: Software. Die Arbeit wurde bisher 14-mal zitiert (Crossref) und nennt 46 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: French ANR, ENS Rennes.
Abstract (Originalsprache)
Summary In this article, we introduce the Conway–Bromage–Lyndon (CBL) structure, a compressed, dynamic and exact method for representing k-mer sets. Originating from Conway and Bromage’s concept, CBL innovatively employs the smallest cyclic rotations of k-mers, akin to Lyndon words, to leverage lexicographic redundancies. In order to support dynamic operations and set operations, we propose a dynamic bit vector structure that draws a parallel with Elias-Fano’s scheme. This structure is encapsulated in a Rust library, demonstrating a balanced blend of construction efficiency, cache locality, and compression. Our findings suggest that CBL outperforms existing dynamic k-mer set methods. Unique to this work, CBL stands out as the only known exact k-mer structure offering in-place set operations. Its different combined abilities position it as a flexible Swiss knife structure for k-mer set management. Availability and implementation https://github.com/imartayan/CBL.
Schlagwörter
MeSH-Schlagwörter (MEDLINE)
Autor:innen und Institutionen
- Univ. Lille, CNRS, Centrale Lille, UMR 9189 CRIStAL, Lille, F-59000, France.
ORCID-Profile: Igor Martayan, Bastien Cazaux, Antoine Limasset, Camille Marchet
Förderung
- French ANR
- ENS Rennes
Zitieren
APA
Martayan, I., Cazaux, B., Limasset, A., & Marchet, C. (2024). Conway–Bromage–Lyndon (CBL): an exact, dynamic representation of k -mer sets. Bioinformatics, 40(Supplement_1), i48-i57. https://doi.org/10.1093/bioinformatics/btae217
Vancouver
Martayan I, Cazaux B, Limasset A, Marchet C. Conway–Bromage–Lyndon (CBL): an exact, dynamic representation of k -mer sets. Bioinformatics. 2024;40(Supplement_1):i48-i57. doi:10.1093/bioinformatics/btae217
BibTeX
@article{Martayan2024,
author = {Martayan, Igor and Cazaux, Bastien and Limasset, Antoine and Marchet, Camille},
title = {Conway–Bromage–Lyndon (CBL): an exact, dynamic representation of k -mer sets},
journal = {Bioinformatics},
year = {2024},
volume = {40},
number = {Supplement_1},
pages = {i48--i57},
doi = {10.1093/bioinformatics/btae217}
}
EUVIMED