it consists of random bits set to *true*, a Bloom filter is likely to be hardly compressible. However, merging them in a COBS-like fashion introduces a pattern in the data structure: if a *k*-mer is present in multiple datasets, then the region of the data structure holding this information will have multiple (possibly contiguous) bits set to *true*. Compressing a filter implies the need to decompress (parts of) it at query time. As such, compression may slow down the query of *s*-mers. To mitigate this issue, the compression scheme should allow fast random access, like the LZ-End [67] scheme.

### 4.10.2 Reducing the size of the datastructure

Using the currently available datastructures, indexing the sheer number of datasets publicly available would lead to petabytes-scale indexes. To mitigate this issue, some methods subsamples *k*-mers, like Mash [68] (e.g. indexing *k*-mers whose hash value is lower than a threshold, says *t*). This allows computing the distance between two datasets, but due to the sampling of *k*-mers, information for a single *k*-mer cannot be retrieved.

Inspired by Mash, I propose to use a deterministic algorithm to subsamples *s*-mers (e.g. using their hash values). At indexation time, multiple thresholds could be used, partitioning indexed *s*-mers into multiple buckets according to their hash value. *s*-mers having a high hash value (higher than the highest threshold) would be quickly queryable, while the others would not. For instance, the first bucket (associated with the highest threshold) would not be compressed, the second compressed with fast random access, the third highly compressed, the fourth highly compressed on external memory, etc.

At query time, one could query the *s*-mers belonging to the first partition. Absent *s*-mers from this partition would indicate the absence of some *k*-mers in the query. *s*-mers appearing only in absent *k*-mers would not be marked as "unnecessary". The query would continue by querying *s*-mers belonging to the second bucket (except for the "unnecessary" *s*-mers). This process would continue until all the *k*-mers have been answered.

This would allow space gain by compressing some filters and would lower the need for RAM, as some filters could be placed on disk. The impact on query time would depend on the number of *s*-mers in the first partitions (quickly queryable).

### 4.10.3 Replacing *k*-mers

Recall that the reason we use *k*-mers is to compare sequences without alignment. However, using spaced seed yields better similarity estimations in the context of metagenomic [69].
In a nutshell, spaced seeds are “*k*-mers with mismatch allowed”. However, unlike *k*-mers, they cannot be trivially split into *s*-mers. The same goes for strobemers [70], an alternative to *k*-mers allowing matching similar sequences, even when their similar regions contain insertion or deletion of bases compared to one another. In a nutshell, strobemers consist of *n* shorter *l*-mers, called strobes. Strobes are subsamples of a sequence, and the space between two strobes in that sequence is variable.

Splitting strobemers into *s*-mers may allow a better similarity estimation when using our indexes. However, it is probably going to be non-trivial, as two consecutive strobemers do not overlap. A direction I am interested in is: instead of splitting strobemers into *s*-mers, I would rather consider strobemers as *s*-mers and coin a new concept consisting of *z* + 1 strobemers. A window of *z* + 1 consecutive strobemers would be considered as present if and only if the *z* + 1 strobemers in this window are present.

## 4.11 Environmental impact of bioinformatics

As stated in the introduction of this manuscript, “the ability to sequence DNA is currently having a transformative impact on many scientific fields”. Research also has impacts on our society. However, I could not find many manuscripts actually discussing these impacts. I propose to quickly address this lack here, by discussing one negative impact of computer science on our environment.

A study [71] analyzed the production of CO₂ by bioinformatics tools. A metagenomic assembler, metaSPAdes [72], was run on 100 samples from forest soil. This emitted 186 kgCO₂eq in 29 hours, which is equivalent to what is emitted when driving 1 065 km by a car in Europe. A tree would require 203 months to absorb this much CO₂.

Because some countries rely on low-carbon power (e.g. nuclear energy in France) while the USA relies on coil and gas to produce electricity, the environmental cost of an algorithm depends on where it is run.

A researcher once said during a workshop that their indexation methods emitted as much CO₂ as a trip by plane from France to the USA. If true, this means that if your biological dataset is stored in a US cluster, then taking a plane to get the hard drive that contains your data, going back to Europe, and performing your computation at home could emit less CO₂ than running the computation in the cluster.

Nowadays, people are increasingly aware that taking planes emits CO₂. However, it seems to me that very few people think about CO₂ emissions when they press “enter” in
their terminal. Personally, I have no idea how much CO₂ my Ph.D. emitted (e.g. through my CI pipeline or my computer components).

Not understanding what emits CO₂ limits our ability to reduce those emissions. As such, a French research group proposes to measure the CO₂ emission of research labs (https://labos1point5.org/). Doing the same with the emission of computational resources would allow understanding how to reduce them. For instance, approaches like *findere* and *fimpera* could reduce the carbon footprint of queries, as they require less query time and less disk space.
BIBLIOGRAPHY

1. Sanger, F. & Coulson, A. R., A rapid method for determining sequences in DNA by primed synthesis with DNA polymerase, *Journal of molecular biology* **94**, 441–448 (1975).

2. Margulies, M. et al., Genome sequencing in microfabricated high-density picolitre reactors, *Nature* **437**, 376–380 (2005).

3. Integrative, H. et al., The integrative human microbiome project, *Nature* **569**, 641–648 (2019).

4. Lemane, T., Medvedev, P., Chikhi, R. & Peterlongo, P., Kmtricks: efficient and flexible construction of bloom filters for large sequencing data collections, *Bioinformatics Advances* **2**, vbac029 (2022).

5. Sunagawa, S. et al., Tara Oceans: towards global ocean ecosystems biology, *Nature Reviews Microbiology* **18**, 428–445 (2020).

6. Lemane, T. et al., kmindex and ORA: indexing and real-time user-friendly queries in terabytes-sized complex genomic datasets, *bioRxiv*, 2023-05 (2023).

7. Fogarty, H. E., Burrows, M. T., Pecl, G. T., Robinson, L. M. & Poloczanska, E. S., Are fish outside their usual ranges early indicators of climate-driven range shifts?, *Global Change Biology* **23**, 2047–2057 (2017).

8. Masters, P. S., The molecular biology of coronaviruses, *Advances in virus research* **66**, 193–292 (2006).

9. Khan, S. et al., Coronavirus diseases 2019: current biological situation and potential therapeutic perspective, *European Journal of Pharmacology* **886**, 173447 (2020).

10. https://www.genome.gov/genetics-glossary/Deoxyribonucleic-Acid.

11. Palomaki, G. E. et al., DNA sequencing of maternal plasma to detect Down syndrome: an international clinical validation study, *Genetics in medicine* **13**, 913–920 (2011).

12. https://www.legifrance.gouv.fr/jorf/id/JORFTEXT000037856379.

13. de-Dios, T. et al., Metagenomic analysis of a blood stain from the French revolutionary Jean-Paul Marat (1743–1793), *Infection, Genetics and Evolution* **80**, 104209, ISSN: 1567-1348, https://www.sciencedirect.com/science/article/pii/S1567134820300411 (2020).
14. Břinda, K. et al., Rapid inference of antibiotic resistance and susceptibility by genomic neighbour typing, *Nature microbiology* **5**, 455–464 (2020).

15. Børsting, C. & Morling, N., Next generation sequencing and its applications in forensic genetics, *Forensic Science International: Genetics* **18**, 78–89 (2015).

16. Yano, K. et al., Genome-wide association study using whole-genome sequencing rapidly identifies new genes influencing agronomic traits in rice, *Nature genetics* **48**, 927–934 (2016).

17. Pierella Karlusich, J. J., Ibarbalz, F. M. & Bowler, C., Phytoplankton in the Tara ocean, *Annual Review of Marine Science* **12**, 233–265 (2020).

18. Wu, R., Nucleotide sequence analysis of DNA: I. Partial sequence of the cohesive ends of bacteriophage λ and 186 DNA, *Journal of molecular biology* **51**, 501–521 (1970).

19. Maxam, A. M. & Gilbert, W., A new method for sequencing DNA. *Proceedings of the National Academy of Sciences* **74**, 560–564 (1977).

20. Shendure, J. & Ji, H., Next-generation DNA sequencing, *Nature biotechnology* **26**, 1135–1145 (2008).

21. Eid, J. et al., Real-time DNA sequencing from single polymerase molecules, *Science* **323**, 133–138 (2009).

22. Haque, F., Li, J., Wu, H.-C., Liang, X.-J. & Guo, P., Solid-state and biological nanopore for real-time sensing of single chemical and sequencing of DNA, *Nano today* **8**, 56–74 (2013).

23. Sereika, M. et al., Oxford Nanopore R10. 4 long-read sequencing enables the generation of near-finished bacterial genomes from pure cultures and metagenomes without short-read or reference polishing, *Nature methods* **19**, 823–826 (2022).

24. Amid, C. et al., The European Nucleotide Archive in 2019, *Nucleic Acids Research* **48**, D70–D76, ISSN: 0305-1048, https://doi.org/10.1093/nar/gkz1063 (2021) (Jan. 2020).

25. Bloom, B. H., Space/time trade-offs in hash coding with allowable errors, *Communications of the ACM* **13**, 422–426 (1970).

26. Fan, L., Cao, P., Almeida, J. & Broder, A. Z., Summary cache: a scalable wide-area web cache sharing protocol, *IEEE/ACM transactions on networking* **8**, 281–293 (2000).

27. Robidou, L. & Peterlongo, P., *findere: fast and precise approximate membership query in String Processing and Information Retrieval: 28th International Symposium, SPIRE 2021*, Lille, France, October 4–6, 2021, *Proceedings* **28** (2021), 151–163.

28. Robidou, L. & Peterlongo, P., fimpera: drastic improvement of Approximate Membership Query data-structures with counts, *Bioinformatics* **39**, btad305 (2023).
29. Pellow, D., Filippova, D. & Kingsford, C., Improving Bloom Filter Performance on Sequence Data Using k-mer Bloom Filters, en, *Journal of Computational Biology* **24**, 547-557, ISSN: 1557-8666, http://www.liebertpub.com/doi/10.1089/cmb.2016.0155 (June 2017).

30. Roberts, M., Hayes, W., Hunt, B. R., Mount, S. M. & Yorke, J. A., Reducing storage requirements for biological sequence comparison, *Bioinformatics* **20**, 3363-3369 (2004).

31. Li, Y. et al., MSPKmerCounter: a fast and memory efficient approach for k-mer counting, *arXiv preprint arXiv:1505.06550* (2015).

32. Limasset, A., Rizk, G., Chikhi, R. & Peterlongo, P., Fast and scalable minimal perfect hashing for massive key sets, *arXiv preprint arXiv:1702.03154* (2017).

33. Pibiri, G. E. & Trani, R., PTHash: Revisiting FCH minimal perfect hashing in Proceedings of the 44th International ACM SIGIR Conference on Research and Development in Information Retrieval (2021), 1339-1348.

34. Pibiri, G. E., Shibuya, Y. & Limasset, A., Locality-preserving minimal perfect hashing of k-mers, *Bioinformatics* **39**, i534-i543 (2023).

35. Rahman, A. & Medevedev, P., Representation of k-mer sets using spectrum-preserving string sets, *Journal of Computational Biology* **28**, 381-394 (2021).

36. De Bruijn, N. G., A combinatorial problem, *Proceedings of the Section of Sciences of the Koninklijke Nederlandse Akademie van Wetenschappen te Amsterdam* **49**, 758-764 (1946).

37. Břinda, K., Baym, M. & Kucherov, G., Simplitigs as an efficient and scalable representation of de Bruijn graphs, *Genome biology* **22**, 1-24 (2021).

38. Schmidt, S. & Alanko, J. N., Eulertigs: minimum plain text representation of k-mer sets without repetitions in linear time, *bioRxiv*, 2022-05-05 (2022).

39. Marchet, C., Iqbal, Z., Gautheret, D., Salson, M. & Chikhi, R., REINDEER: efficient indexing of k-mer presence and abundance in sequencing datasets, *Bioinformatics* **36**, i177-i185 (2020).

40. Marchet, C. et al., Data structures based on k-mers for querying large collections of sequencing data sets, *Genome Research* **31**, 1-12 (2021).

41. Chikhi, R., Holub, J. & Medvedev, P., Data structures to represent a set of k-long DNA sequences, *ACM Computing Surveys (CSUR)* **54**, 1-22 (2021).

42. Almodaresi, F., Sarkar, H., Srivastava, A. & Patro, R., A space and time-efficient index for the compacted colored de Bruijn graph, *Bioinformatics* **34**, i169-i177 (2018).
43. Marchet, C., Kerbiriou, M. & Limasset, A., BLight: efficient exact associative structure for k-mers, *Bioinformatics* **37**, 2858-2865 (2021).

44. Holley, G. & Melsted, P., Bifrost: highly parallel construction and indexing of colored and compacted de Bruijn graphs, *Genome biology* **21**, 1-20 (2020).

45. Pibiri, G. E., Sparse and skew hashing of k-mers, *Bioinformatics* **38**, i185-i194 (2022).

46. Karasikov, M. et al., Metagraph: Indexing and analysing nucleotide archives at petabase-scale, *BioRxiv*, 2020-10 (2020).

47. Almeida, A. et al., A unified catalog of 204,938 reference genomes from the human gut microbiome, *Nature biotechnology* **39**, 105-114 (2021).

48. O'Leary, N. A. et al., Reference sequence (RefSeq) database at NCBI: current status, taxonomic expansion, and functional annotation, *Nucleic acids research* **44**, D733-D745 (2016).

49. Zhang, X., Yu, Y., Mok, C. H., MacLeod, J. N. & Liu, J., Gazelle: transcript abundance query against large-scale RNA-seq experiments in Proceedings of the 12th ACM Conference on Bioinformatics, Computational Biology, and Health Informatics (2021), 1-8.

50. Carter, L., Floyd, R., Gill, J., Markowsky, G. & Wegman, M., *Exact and approximate membership testers in Proceedings of the tenth annual ACM symposium on Theory of computing* (1978), 59-65.

51. Cormode, G. & Muthukrishnan, S., An improved data stream summary: the count-min sketch and its applications, *Journal of Algorithms* **55**, 58-75 (2005).

52. Bender, M. A. et al., *Don't thrash: how to cache your hash on flash in 3rd Workshop on Hot Topics in Storage and File Systems (HotStorage 11)* (2011).

53. Pandey, P., Bender, M. A., Johnson, R. & Patro, R., *A general-purpose counting filter: Making every bit count in Proceedings of the 2017 ACM international conference on Management of Data* (2017), 775-787.

54. Fan, B., Andersen, D. G., Kaminsky, M. & Mitzenmacher, M. D., *Cuckoo filter: Practically better than bloom in Proceedings of the 10th ACM International on Conference on emerging Networking Experiments and Technologies* (2014), 75-88.

55. Graf, T. M. & Lemire, D., *Xor filters: Faster and smaller than bloom and cuckoo filters*, *Journal of Experimental Algorithmics (JEA)* **25**, 1-16 (2020).

56. Graf, T. M. & Lemire, D., *Binary fuse filters: Fast and smaller than xor filters*, *Journal of Experimental Algorithmics (JEA)* **27**, 1-15 (2022).
57. Bradley, P., Den Bakker, H. C., Rocha, E. P., McVean, G. & Iqbal, Z., Ultrafast search of all deposited bacterial and viral genomic data, *Nature biotechnology* **37**, 152–159 (2019).

58. Wong, H. K., Bit transposed files (1985).

59. Bingmann, T., Bradley, P., Gauger, F. & Iqbal, Z., COBS: a compact bit-sliced signature index in String Processing and Information Retrieval: 26th International Symposium, SPIRE 2019, Segovia, Spain, October 7–9, 2019, Proceedings 26 (2019), 285–303.

60. Solomon, B. & Kingsford, C., Fast search of thousands of short-read sequencing experiments, *Nature biotechnology* **34**, 300–302 (2016).

61. Harris, R. S. & Medvedev, P., Improved representation of sequence bloom trees, *Bioinformatics* **36**, 721–727 (2020).

62. Marchet, C. & Limasset, A., Scalable sequence database search using Partitioned Aggregated Bloom Comb-Trees, *bioRxiv*, 2022–02 (2022).

63. Darvish, M., Seiler, E., Mehringer, S., Rahn, R. & Reinert, K., Needle: a fast and space-efficient prefilter for estimating the quantification of very large collections of expression experiments, *Bioinformatics* **38**, 4100–4108 (2022).

64. Lee, H., Shuaibi, A., Bell, J. M., Pavlichin, D. S. & Ji, H. P., Unique k-mer sequences for validating cancer-related substitution, insertion and deletion mutations, *NAR cancer 2*, zcaa034 (2020).

65. Kokot, M., Dlugosz, M. & Deorowicz, S., KMC 3: counting and manipulating k-mer statistics, *Bioinformatics* **33**, 2759–2761 (2017).

66. Durocher, S. & Singh, R., A simple linear-space data structure for constant-time range minimum query, *Theoretical Computer Science* **770**, 51–61 (2019).

67. Kreft, S. & Navarro, G., LZ77-like compression with fast random access in 2010 *Data Compression Conference* (2010), 239–248.

68. Ondov, B. D. et al., Mash: fast genome and metagenome distance estimation using Min-Hash, *Genome biology* **17**, 1–14 (2016).

69. Břinda, K., Sykulski, M. & Kucherov, G., Spaced seeds improve k-mer-based metagenomic classification, *Bioinformatics* **31**, 3584–3592 (2015).

70. Sahlin, K., Effective sequence similarity detection with strobemers, *Genome research* **31**, 2080–2094 (2021).

71. Grealey, J. et al., The carbon footprint of bioinformatics, *Molecular biology and evolution* **39**, msac034 (2022).
72. Nurk, S., Meleshko, D., Korobeynikov, A. & Pevzner, P. A., metaSPAdes: a new versatile metagenomic assembler, *Genome research* **27**, 824–834 (2017).

73. Holley, R. W., Madison, J. T. & Zamir, A., A new method for sequence determination of large oligonucleotides, *Biochemical and Biophysical Research Communications* **17**, 389–394 (1964).

74. Twiss, P., Hill, M., Daley, R. & Chitty, L. S., *Non-invasive prenatal testing for Down syndrome in Seminars in Fetal and Neonatal Medicine* **19** (2014), 9–14.

75. Bray, N. L., Pimentel, H., Melsted, P. & Pachter, L., Near-optimal probabilistic RNA-seq quantification, *Nature biotechnology* **34**, 525–527 (2016).

76. Almodaresi, F., Sarkar, H., Srivastava, A. & Patro, R., A space and time-efficient index for the compacted colored de Bruijn graph, *Bioinformatics* **34**, i169–i177, ISSN: 1367-4803, eprint: https://academic.oup.com/bioinformatics/article-pdf/34/13/i169/50316242/bioinformatics\_34\_13\_i169.pdf, https://doi.org/10.1093/bioinformatics/bty292 (June 2018).

77. Chikhi, R., Limasset, A. & Medvedev, P., Compacting de Bruijn graphs from sequencing data quickly and in low memory, *Bioinformatics* **32**, i201–i208 (2016).

78. Italiano, G. F., Prezza, N., Sinaimeri, B. & Venturini, R., *Compressed weighted de Bruijn graphs in CPM 2021-32nd Annual Symposium on Combinatorial Pattern Matching* **191** (2021), 1–16.

79. Bowe, A., Onodera, T., Sadakane, K. & Shibuya, T., *Succinct de Bruijn graphs in Algorithms in Bioinformatics: 12th International Workshop, WABI 2012, Ljubljana, Slovenia, September 10-12, 2012. Proceedings* **12** (2012), 225–235.
<figure><img src="image_57.png" /></figure>
**Titre :** Moteur de recherche pour données de séquençage génomique

**Mot clés :** requêtes d'appartenance approchée, structure de données, indexation, *k*-mers, filtres

**Résumé :** Les technologies de séquençage à haut débit génèrent des quantités massives de jeux de données de séquences biologiques à mesure que les coûts diminuent. L'un des défis actuels pour exploiter ces données consiste à développer des moteurs de recherche pour ces jeux d'une taille de l'ordre du pétaoctet. La plupart des méthodes existantes reposent sur l'indexation des séquences via leurs mots de longueur *k*, appelés *k*-mers. Dans de nombreux domaines de la bioinformatique, il est nécessaire de retrouver l'abondance d'un *k*-mer dans un ensemble de données.

Des structures de données, appelées AMQ, sont largement utilisées pour représenter ces grands ensembles de *k*-mers. D'autres

structures de données similaires, les cAMQ, représentent des multiensembles, de façon à pouvoir retrouver l'abondance d'un *k*-mer dans un jeu. Cependant, par nature, ces AMQs renvoient des faux positifs et, dans le cas d'un multiensemble, ont tendance à surestimer l'abondance des *k*-mers.

Dans ce manuscrit, nous présentons deux contributions, *findere* et *fimpera*, qui permettent d'améliorer les performances des (c)AMQs. Appliqué au filtre de Bloom, qui est largement utilisé en bioinformatique, *findere* réduit son taux de faux positifs de deux ordres de grandeur tout en accélérant ses requêtes. *fimpera* réduit le taux de faux positifs d'un filtre de Bloom avec comptage tout en améliorant la précision des abondances renvoyées.

**Title:** Search engine for genomic sequencing data

**Keywords:** approximate membership query, data structures, indexation, *k*-mers, filters

**Abstract:** High throughput sequencing technologies generate massive amounts of biological sequence datasets as costs fall. One of the current algorithmic challenges for exploiting these data on a global scale consists in providing efficient query engines on these petabyte-scale datasets. Most methods indexing those datasets rely on indexing sequence datasets through their constituent words of fixed length *k*, called *k*-mers. In many applications, it is required to retrieve the abundance of a *k*-mer in a dataset.

Approximate membership query (AMQ) data structures are widely used for representing these large sets of *k*-mers. A counting

AMQ (cAMQ) can index the abundance of *k*-mers along with their presence in a dataset. However, these (c)AMQs suffer by nature from non-avoidable false-positive calls and overestimated calls that bias downstream analyses.

In this work, we propose two contributions, *findere* and *fimpera*, that enable the improvement of any (c)AMQ performance. Applied to the widely used Bloom filter, *findere* reduces the false positive rate by two orders of magnitude while speeding up the queries. *fimpera* reduces the false positive rate of a counting Bloom filter while improving the precision of the reported abundances.