BLight: efficient exact associative structure for k-mers

Limasset, Antoine; Marchet, Camille; Kerbiriou, Mael

Document type :

Article dans une revue scientifique

DOI :

10.1093/bioinformatics/btab217

Title :

BLight: efficient exact associative structure for k-mers

Author(s) :

Limasset, Antoine [Auteur]

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

Marchet, Camille [Auteur]
Kerbiriou, Mael [Auteur]

Journal title :

Bioinformatics

Pages :

2858-2865

Publisher :

Oxford University Press (OUP)

Publication date :

2021-01-03

ISSN :

1367-4803

HAL domain(s) :

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

English abstract : [en]

Abstract Motivation A plethora of methods and applications share the fundamental need to associate information to words for high-throughput sequence analysis. Doing so for billions of k-mers is commonly a scalability ...
Show more >Abstract Motivation A plethora of methods and applications share the fundamental need to associate information to words for high-throughput sequence analysis. Doing so for billions of k-mers is commonly a scalability problem, as exact associative indexes can be memory expensive. Recent works take advantage of overlaps between k-mers to leverage this challenge. Yet, existing data structures are either unable to associate information to k-mers or are not lightweight enough. Results We present BLight, a static and exact data structure able to associate unique identifiers to k-mers and determine their membership in a set without false positive that scales to huge k-mer sets with a low memory cost. This index combines an extremely compact representation along with very fast queries. Besides, its construction is efficient and needs no additional memory. Our implementation achieves to index the k-mers from the human genome using 8 GB of RAM (23 bits per k-mer) within 10 min and the k-mers from the large axolotl genome using 63 GB of memory (27 bits per k-mer) within 76 min. Furthermore, while being memory efficient, the index provides a very high throughput: 1.4 million queries per second on a single CPU or 16.1 million using 12 cores. Finally, we also present how BLight can practically represent metagenomic and transcriptomic sequencing data to highlight its wide applicative range. Availability and implementation We wrote the BLight index as an open source C++ library under the AGPL3 license available at github.com/Malfoy/BLight. It is designed as a user-friendly library and comes along with code usage samples.Show less >

Language :

Anglais

Peer reviewed article :

Oui

Audience :

Internationale

Popular science :

Non

Collections :

Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189

Source :

Harvested from HAL

BLight: efficient exact associative structure ... BibTeX CSV Excel RIS

BLight: efficient exact associative structure ...

BibTeX

CSV

Excel

RIS