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

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

Type de document :

Compte-rendu et recension critique d'ouvrage

DOI :

10.1101/2024.01.29.577700

URL permanente :

http://hdl.handle.net/20.500.12210/118345

Titre :

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

Auteur(s) :

Martayan, Igor [Auteur]
Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 [CRIStAL]
Cazaux, Bastien [Auteur]

Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 [CRIStAL]
Limasset, Antoine [Auteur]

Centre National de la Recherche Scientifique [CNRS]
Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 [CRIStAL]
Marchet, Camille [Auteur]
Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 [CRIStAL]
Centre National de la Recherche Scientifique [CNRS]

Titre de la revue :

Bioinformatics

Pagination :

i48-i57

Éditeur :

Oxford University Press (OUP)

Date de publication :

2024-07-28

ISSN :

1367-4803

Discipline(s) HAL :

Informatique [cs]
Informatique [cs]/Bio-informatique [q-bio.QM]

Résumé en anglais : [en]

Abstract 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 ...
Lire la suite >Abstract 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.Lire moins >

Langue :

Anglais

Vulgarisation :

Non

Projet ANR :

Analyse en pleine longueur et en profondeur des ARNs
Structures de graphe adaptées pour l'exploration de données de séquençage de troisième génération

Collections :