Data structures based on k-mers for querying large collections of sequencing data sets
- Camille Marchet1,
- Christina Boucher2,
- Simon J. Puglisi3,
- Paul Medvedev4,5,6,
- Mikaël Salson1 and
- Rayan Chikhi7
- 1Université de Lille, CNRS, CRIStAL UMR 9189, F-59000 Lille, France;
- 2Department of Computer and Information Science and Engineering, University of Florida, Gainesville, Florida 32611, USA;
- 3Department of Computer Science, University of Helsinki, FI-00014, Helsinki, Finland;
- 4Department of Computer Science, The Pennsylvania State University, University Park, Pennsylvania 16802, USA;
- 5Department of Biochemistry and Molecular Biology, The Pennsylvania State University, University Park, Pennsylvania 16802, USA;
- 6Center for Computational Biology and Bioinformatics, The Pennsylvania State University, University Park, Pennsylvania 16802, USA;
- 7Institut Pasteur & CNRS, C3BI USR 3756, F-75015 Paris, France
Abstract
High-throughput sequencing data sets are usually deposited in public repositories (e.g., the European Nucleotide Archive) to ensure reproducibility. As the amount of data has reached petabyte scale, repositories do not allow one to perform online sequence searches, yet, such a feature would be highly useful to investigators. Toward this goal, in the last few years several computational approaches have been introduced to index and query large collections of data sets. Here, we propose an accessible survey of these approaches, which are generally based on representing data sets as sets of k-mers. We review their properties, introduce a classification, and present their general intuition. We summarize their performance and highlight their current strengths and limitations.
Footnotes
-
[Supplemental material is available for this article.]
-
Article published online before print. Article, supplemental material, and publication date are at http://www.genome.org/cgi/doi/10.1101/gr.260604.119.
- Received December 29, 2019.
- Accepted September 14, 2020.
This article is distributed exclusively by Cold Spring Harbor Laboratory Press for the first six months after the full-issue publication date (see http://genome.cshlp.org/site/misc/terms.xhtml). After six months, it is available under a Creative Commons License (Attribution-NonCommercial 4.0 International), as described at http://creativecommons.org/licenses/by-nc/4.0/.
