EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Conway–Bromage–Lyndon (CBL): an exact, dynamic representation of k -mer sets

Igor Martayan iD, Bastien Cazaux iD, Antoine Limasset iD, Camille Marchet iD

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.

AbstractSchlagwörterBibliografische AngabenZitierenVerwandte Studien

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)

SoftwareAlgorithmsComputational Biology

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}
}
Kostenlos starten →