000101111001010011
000011100010011
111
110001011

Hash-based data-structures for querying
large k-mer (collections of) sets

CiE 2023
Camille Marchet
CNRS, CRIStAL Lille, France
camille.marchet@univ-lille.fr@CamilleMrcht

Hash-based data-structures for querying large k-mer (collections of) sets

Marchet C

1 / 33

Introduction - indexing genomic data
Read datasets, contig sets, pangenomes
Queries: genes, mutations + genomic context, splicing events, exons, . . .
Single species projects

Multi species projects

Multi projects banks

150,000 sequencingsof human genomes
with 600,000 millions of SNPs
[Halldorson et al. 22]

28 Tera bases
from 771 meta-transcriptomes
Tara Ocean

47 Peta basesof reads
Sequence Read Archive

data-structure wise, we're around here

Huge limitation: extract information from these collections at a reasonable cost
Hash-based data-structures for querying large k-mer (collections of) sets

Marchet C

2 / 33

Introduction - When it comes to k-mersgenomeshuman(#31-mers)

3.2Gb

Pinus
taeda
10.5GbAmbystoma Neoceratodus
mexicanum
forsteri
18.5Gb
43Gb

In practice :k sizes : 15-19 (long reads), 21-51 (short reads)
Billions (of distinct k-mers) easily reached in experiments
The notion of cost becomes central

Hash-based data-structures for querying large k-mer (collections of) sets

Marchet C

3 / 33

Introduction - Themes of this talk

AAAATTAGGACAAAGAACTACCAAGAATTACCTCCTACAGATCACTAAACACGTG...
...

k-mers sets
eﬃcient
eﬃcient+ hash-based
representation
methods
Hash-based data-structures for querying large k-mer (collections of) sets

...
...

index
collections ofk-mer sets
Marchet C

4 / 33

Indexing k-mer sets:
k-mers sets representations

Hash-based data-structures for querying large k-mer (collections of) sets

Marchet C

5 / 33k-mer sets - representation in Conway & Bromage1
A 00 C 01 G 10 T 11
ACAT
CATT
ATTG

....
....
TAGT

1 00010011
0....
1 00111110...
1 01001111...

...
111001011

1 Conway & Bromage 2011
Hash-based data-structures for querying large k-mer (collections of) sets

Marchet C

6 / 33k-mer sets - representation in Conway & Bromagen = ~3.109 31-mersin human genome
uniformely distributedACAT
CATT
ATTG

....
....
TAGT

Conway &Bromage
1 00010011
0....
1 00111110...
1 01001111...

worst case lower bound:
4k bits = 35 bits per 31-mern()~13 GB for distinct 31-mers of
the whole genome...
111001011

Hash-based data-structures for querying large k-mer (collections of) sets

Marchet C

7 / 33k-mer sets - representation in Conway & Bromage
A 00 C 01 G 10 T 11ACAT
CATT
ATTG

....
....
TAGT

1 00010011
0....
1 00111110...
1 01001111...

...
111001011

In practice k-mers overlap and later structures take advantage of this property

Hash-based data-structures for querying large k-mer (collections of) sets

Marchet C

8 / 33k-mer sets - "beat" the lower bound with Minia2a k-mer set can be seen as a de Bruijn graphk-mer set: {ATAA, TAAC, AACA, AAAC, ACAA, CAAT,AATT, ATTG, CCAT, CATT, ACAC, CACA}
de Bruijn graph CCAT CATTACAA CAAT AATT ATTG
ATAA TAAC AACA
AAAC

ACAC CACA

AATG
GGGG

2 Chikhi & Rizk 2012
Hash-based data-structures for querying large k-mer (collections of) sets

Marchet C

9 / 33k-mer sets - "beat" the lower bound with Minia

a k-mer set can be seen as a de Bruijn graph encoded in a probabilistic data structure
ATAA CACA AATG GGGG TTTT
0 0 1 0 0de Bruijn graph CCAT CATTACAA CAAT AATT ATTG

critical false positives

ATAA TAAC AACA
1 1 0 0 1 0 0 1 1 0 1 0 0 0

AAAC

ACAC CACA

AATG
GGGG

probabilistic k-mer set

Hash-based data-structures for querying large k-mer (collections of) sets

Marchet C10 / 33

k-mer sets - encoding with Bloom filters

Hash-based data-structures for querying large k-mer (collections of) sets

Marchet C

11 / 33

k-mer sets - playing with the de Bruijn graph: SPSS
Spectrum preserving string sets (SPSS, first described in [Rahman & Medvedev 2020])
intuition
k-mer set: {ATAA, TAAC, AACA, AAAC, ACAA, CAAT, AATT, ATTG, CCAT, CATT,ACAC, CACA} (48 nucleotides)

unitig graph/compacted de Bruijn graphde Bruijn graph
CCAT CATTCCATT

ACAA CAAT AATT ATTG
ATAA TAAC AACAAAAC

ACAATT ATTG
ATAAC AACA

ACAC CACA

AAAC

ACACA

unitig set: {ATAAC, AAAC, AACA, ACACA, ACAATT, CCATT, ATTG} (33 nucleotides)

Hash-based data-structures for querying large k-mer (collections of) sets

Marchet C

12 / 33

k-mer sets - playing with the de Bruijn graph: SPSS
Heuristics close to the lower bound: UST, simplitigs [Brinda et al. 2020, Rahman &Medvedev. 2020]
k-mer set: (48 bases){ATAA, TAAC, AACA, AAAC, ACAA, CAAT, AATT, ATTG, CCAT,CATT, ACAC, CACA}

de Bruijn graph

CCAT CATT

unitigs
simplitigs/USTACAA CAAT AATT ATTG
ATAA TAAC AACA
AAAC

ACAC CACA

unitig set: (33 bases) {ATAAC, AAAC, AACA, ACACA, ACAATT, CCATT, ATTG}
UST/simplitig set: (24 bases) {ATAACAATTG, AAAC, ACACA, CCATT}

Hash-based data-structures for querying large k-mer (collections of) sets

Marchet C

13 / 33

k-mer sets - playing with the de Bruijn graph: SPSS
Optimal solution [Schmidt and Alanko 2022] shortest superstring in an eulerian graphk-mer set: {ATAA, TAAC, AACA, AAAC, ACAA, CAAT, AATT, ATTG, CCAT, CATT, ACAC, CACA}
distinct path cover (simplitigs.UST)

A
ACA

ATAA

TAA

TAACAACA
AAC
ACA

AA

CACA

CAC

output string set (24 nucleotides):{AAAC, ACACA, ATAACAATTG, CCATT}

AAA

CAA

CCAT
CAAT

CAT CAT
AAT

T
ATT
TTG
AATT
ATTG

CC

AAA

ATA

AA
AC

A

TAAC
AACA
AAC
ACA

CCA

T
CAA
AAT
ATT
TTG
CAAT
AATT
ATTG

ACA

TAA

AC

ATAA

minimal distinct path cover (guaranteed in Eulertigs)

CAT CAT

ACA

ATA

CCA
ACA

edge-centric de Bruijn graph

CCAT

CACA

CAC

output string set (21 nucleotides):{ATAACACAATTG,CCATT,AAAC}

In theory, the three approaches (2 heuristics, 1 optimal) are linear. Moreformalization in [Sladky et al. 2023].
Hash-based data-structures for querying large k-mer (collections of) sets

Marchet C

14 / 33

k-mer sets - encoding with an example of SPSS
Using simplitigs/UST:

Hash-based data-structures for querying large k-mer (collections of) sets

Marchet C

15 / 33

Indexing k-mer sets:hash functions and hash tables

Hash-based data-structures for querying large k-mer (collections of) sets

Marchet C

16 / 33

Associative indexes - Minimal perfect hash functions (MPHF)

The hash function itself has a cost. Theoretical bound: 1.44 bits per key
Practical implementations used in bioinformatics (fast construction/query, around4 bits/key)• BBHASH [Limasset et al. 2014]• PTHash [Pibiri et al. 2021]

Hash-based data-structures for querying large k-mer (collections of) sets

Marchet C17 / 33

Associative indexes - Minimal perfect hash functions (MPHF)
BBHash [Limasset et al. 17]{k1, k2, k3, k4, k5 ... kn}
f1

f2{k2, k4, k5,kn}

f3{k2, k5}

Hash-based data-structures for querying large k-mer (collections of) sets

+rank on the ﬁnal bitvector

Marchet C

18 / 33

Associative indexes - Minimal perfect hash functions (MPHF)
PTHash [Pibiri 2021]{k1, k2, k3, k4, k5 ... kn}
f{k4,...}

bucket 1

h1{k1, k2, kn} {k3,k5,...}
h2
bucket 2+remember hx/bucket x association

bucket m

BBHash and PTHash’s construction times are linear, PTHash generates less cache
misses during queries.
Hash-based data-structures for querying large k-mer (collections of) sets

Marchet C

19 / 33

Associative indexes - "2nd generation" of MPHFs inbioinformatics
Specialized for k-mer sets
LPHash [Pibiri et al. 2023]
k-mers(k=6, m=3)
CTGAATTGAATC...
ATCAAC

compute minimizer:
access to bucket

MPHF#0 (AAA)super-k-mers

MPHF#1 (AAC)

0ATCAAC...

MPHF#2 (AAG)
MPHF#3 (AAT)...
Hash-based data-structures for querying large k-mer (collections of) sets

CTGAATCAA
0 1
hash k-mer toposition in stored
super-k-mers
Marchet C

20 / 33

Associative indexes - "Beat" another lower boundbits/keyin this region, the input is
too fragmented tobeneﬁt from the LP-MPHF
theoretical lower boundfor general purpose
MPHFs

1.440

probability of cache-locality
1 (bounded by input fragmentation)

for not too fragmented SPSS,
the LP-MPHF can "beat" the 1.44 bits/key

Hash-based data-structures for querying large k-mer (collections of) sets

Marchet C

21 / 33

Associative indexes - Minimal perfect hash functions (MPHF)"MPHFs are static"MPHFs are only hash functions, in order to build a hash table we need arepresentation of the keys to deal with alien keys
MPHFs are combined with a key representation scheme (typically a SPSS) to buildhash tables

Hash-based data-structures for querying large k-mer (collections of) sets

Marchet C22 / 33

Associative indexes - Hash tables for k-mers
Efficient k-mer hash tables:
SRC [Marchet et al. 2016]: MPHF + k-mers fingerprints
Counting quotient filters [Pandey et al. 2017]: another hashing strategy
Pufferfish: MPHF+unitigs [Almodaresi et al. 2018]
BLight: MPHF+partitioning+SPSS [Marchet et al. 2021]
SSHash: MPHF+SPSS+ optimizations based on sparse and skew distribution ofk-mers [Pibiri 2022]
Applications:
Example of achievement:
index the 31-mers of the human genome in RAM in <8GB (BLight)
Counting k-mers [Pandey et al. 2018]
Large scale quantification [Marchet et al. 2020]
Read alignment [Almodaresi et al. 2021]
Hash-based data-structures for querying large k-mer (collections of) sets

Marchet C

23 / 33

Indexing collections of k-mer sets

Hash-based data-structures for querying large k-mer (collections of) sets

Marchet C

24 / 33

Collections of k-mer setsa set of datasets {d1, d2, ... dn}(reads multisets)query sequence...ATTACGTAGTA...

d1d2

d3

...

...
return all di's where the query occurs

Each dataset (and the query) are seen as sets of k-mers
The query is "present" in a dataset if enough of its k-mers are foundHash-based data-structures for querying large k-mer (collections of) sets

Marchet C

25 / 33

Collections of k-mer sets - State of the art
2013

2016

2017

Rainbowﬁsh
VARI
CortexBFT
exact methods for collectionsof samples/genomes
SRC

2018

2019

2020

2021

2022

GazellePuﬀerﬁsh2
SSHash GGCAT
B-S Mantis
Metagraphcounting

Puﬀerﬁsh
MantisMetannot

VARI-Merge
Mantis+MST
Multi-BRWTBLightBiFrost

Metagraph
REINDEER

count methods

inexact methods for collections of samples/genomes
SBT

AllSomeSBT
SSBT

SeqOthello

HowDeSBT
BIGSI
COBS

acgt compacted colored de Bruijn graphs
acgt general purpose k-mer hash tables with possible color/feature coding

2023

RaptorNeedlehIBF
PAC
metaProFi
kmIndexsome level of relatedness, either from shared data-structures or inherited ideas,

Hash-based data-structures for querying large k-mer (collections of) sets

Marchet C

26 / 33

Collections of k-mer sets - State of the art

Exact methods: for precise, short queries or when colored de Bruijn graphs areneeded
Probabilistic methods: better scalability if false positives are acceptableHash-based data-structures for querying large k-mer (collections of) sets

Marchet C

27 / 33

Collections of k-mer sets - probabilistic methods: querying
Bloom filters

Matrix/interleaved bit structures
Find a k-mer’s information in a single access
Adapt size/compress filters according to the dataset content
Bradley et al. 19, Bingman et al. 19. Close concept: Mehringer et al. 22
Hash-based data-structures for querying large k-mer (collections of) sets

Marchet C

28 / 33

Collections of k-mer sets - querying Bloom filters

Sequence Bloom trees (binary trees) structures
Query speed can be better than matrices in theory
Works well with queries for k-mers in restrained regions of the tree (leaf order isimportant)∼ 2n filters to store + compression strategies

Solomon &Kingsford 16&18, Sun et al. 18, Harris & Medvedev 20
Hash-based data-structures for querying large k-mer (collections of) sets

Marchet C

29 / 33

Collections of k-mer sets - Combine trees and matrices
111001same information111001

1010010010010010000000011110011010010010011100000010000000011010011100000 1 10 0 1
in practice: [214003] + 0 1 00 0 00 0 0
1 1 0

PAC [Marchet & Limasset 2023]
Other approach not presented: SeqOthello [Yu et al. 18] (different hash-based strategy)
Hash-based data-structures for querying large k-mer (collections of) sets

Marchet C

30 / 33

Collections of k-mer sets - Usage
Examples on ∼ 2,500 human RNA-seq (50TB uncompressed)

inexact structures

exact structures

construction time2-10h∼ 20h

index size∼15 GB

30 GB or more

Hash-based data-structures for querying large k-mer (collections of) sets

Marchet C

31 / 33

Collections of k-mer sets - Open questions and problems

Open questions:
Combine SPSS and Bloom filter structures
Can we do better than O (n) for the query worst case? (e.g. Rambo, [Gupta et al.
2021])
Query expressivity with these structures (k-mer abundances, localisation?)
Works on correlations between color classes [Almodaresi et al. 2019], and k-mer
locality [Marchet et al. 2021]

Hash-based data-structures for querying large k-mer (collections of) sets

Marchet C

32 / 33

Conclusion - large scale k-mer data structures
Currently two visions:• With huge computing resources, build very large indexes on servers + APIs• "Lightweight" methods for more frugal usages

Surveys on these data-structures: Marchet C, et al 2020. Data structures basedon k-mers for querying large collections of sequencing data sets. and Chikhi R,
Holub J, Medvedev P. 2019. Data structures to represent a set of k-long DNA
sequences. ACM Computing Surveys
Acknowledgments:
CiE organizers, Alexandru & Giovanna
Team Bio2M Montpellier: Chloé Bessières,Anthony Boureux, Benoit Guibert, Thérèse
CommesGautheret’s lab Orsay: Haoliang Xue, Mélina
Galopin, Daniel Gautheret
Hash-based data-structures for querying large k-mer (collections of) sets

Team SeqBio Pasteur: Rayan Chikhi,
Yoann Dufresnes
Team Bonsai Lille: Mikaël Salson,
Antoine Limasset
Elsewhere on Earth: Paul Medvedev,
Zamin Iqbal, Christina Boucher
Marchet C33 / 33