2019/03/29 by Rayan Chikhi, Chikhi, Rayan, Jan Holub +3 · 1 citation
Biochemistry, Genetics and Molecular Biology · Computer Science · #Algorithms and Data Compression #DNA and Biological Computing #Data Structures and Algorithms (cs.DS) #FOS: Biological sciences #FOS: Computer and information sciences #Genomics (q-bio.GN) #Genomics and Phylogenetic Studies
paper · pdf · doi:10.48550/arxiv.1903.12312
openalex publication_date 2019/03/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The analysis of biological sequencing data has been one of the biggest applications of string algorithms. The approaches used in many such applications are based on the analysis of k-mers, which are short fixed-length strings present in a dataset. While these approaches are rather diverse, storing and querying a k-mer set has emerged as a shared underlying component. A set of k-mers has unique features and applications that, over the last ten years, have resulted in many specialized approaches for its representation. In this survey, we give a unified presentation and comparison of the data structures that have been proposed to store and query a k-mer set. We hope this survey will serve as a resource for researchers in the field as well as make the area more accessible to researchers outside the field.