{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,3]],"date-time":"2026-06-03T05:46:20Z","timestamp":1780465580240,"version":"3.54.1"},"reference-count":80,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2021,3,8]],"date-time":"2021-03-08T00:00:00Z","timestamp":1615161600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by-nd\/4.0\/"}],"funder":[{"name":"Fulbright Visiting Scholar Program"},{"name":"OP VVV MEYS","award":["CZ.02.1.01\/0.0\/0.0\/16_019\/0000765"],"award-info":[{"award-number":["CZ.02.1.01\/0.0\/0.0\/16_019\/0000765"]}]},{"DOI":"10.13039\/100018240","name":"\u201cResearch Center for Informatics\u201d","doi-asserted-by":"crossref","id":[{"id":"10.13039\/100018240","id-type":"DOI","asserted-by":"crossref"}]},{"name":"NSF","award":["DBI-1356529, CCF-551439057, IIS-1453527, and IIS-1421908"],"award-info":[{"award-number":["DBI-1356529, CCF-551439057, IIS-1453527, and IIS-1421908"]}]},{"name":"National Institute Of General Medical Sciences of the National Institutes of Health","award":["R01GM130691"],"award-info":[{"award-number":["R01GM130691"]}]},{"name":"INCEPTION","award":["PIA\/ANR-16-CONV-0005"],"award-info":[{"award-number":["PIA\/ANR-16-CONV-0005"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Comput. Surv."],"published-print":{"date-parts":[[2022,1,31]]},"abstract":"<jats:p>\n            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\n            <jats:italic>k<\/jats:italic>\n            -mers, which are short fixed-length strings present in a dataset. While these approaches are rather diverse, storing and querying a\n            <jats:italic>k<\/jats:italic>\n            -mer set has emerged as a shared underlying component. A set of\n            <jats:italic>k<\/jats:italic>\n            -mers has unique features and applications that, over the past 10 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\n            <jats:italic>k<\/jats:italic>\n            -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.\n          <\/jats:p>","DOI":"10.1145\/3445967","type":"journal-article","created":{"date-parts":[[2021,3,8]],"date-time":"2021-03-08T17:11:54Z","timestamp":1615223514000},"page":"1-22","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":36,"title":["Data Structures to Represent a Set of\n            <i>k<\/i>\n            -long DNA Sequences"],"prefix":"10.1145","volume":"54","author":[{"given":"Rayan","family":"Chikhi","sequence":"first","affiliation":[{"name":"Center of Bioinformatics and Biostatistics and Integrative Biology, Paris, France"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jan","family":"Holub","sequence":"additional","affiliation":[{"name":"Department of Theoretical Computer Science, Czech Technical University in Prague, Th\u00e1kurova, Prague"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Paul","family":"Medvedev","sequence":"additional","affiliation":[{"name":"Center for Computational Biology and Bioinformatics, PA, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2021,3,8]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-17083-7_1"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1101\/138016"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/bty292"},{"key":"e_1_2_1_4_1","volume-title":"Gutin","author":"Bang-Jensen J\u00f8rgen","year":"2009","unstructured":"J\u00f8rgen Bang-Jensen and Gregory Z . Gutin . 2009 . Digraphs : Theory, Algorithms and Applications. Springer Science & Business Media . DOI:https:\/\/doi.org\/10.1007\/978-1-84800-998-1 10.1007\/978-1-84800-998-1 J\u00f8rgen Bang-Jensen and Gregory Z. Gutin. 2009. Digraphs: Theory, Algorithms and Applications. Springer Science & Business Media. DOI:https:\/\/doi.org\/10.1007\/978-1-84800-998-1"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1089\/cmb.2012.0021"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2012.02.002"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-04128-0_61"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-46049-9_14"},{"key":"e_1_2_1_9_1","volume-title":"Puglisi","author":"Belazzougui Djamal","year":"2016","unstructured":"Djamal Belazzougui , Travis Gagie , Veli M\u00e4kinen , Marco Previtali , and Simon J . Puglisi . 2016 b. Bidirectional variable-order de Bruijn graphs. In LATIN 2016: Theoretical Informatics (Lecture Notes in Computer Science), Evangelos Kranakis, Gonzalo Navarro, and Edgar Ch\u00e1vez (Eds.), Vol. 9644 . Springer , 164--178. DOI:https:\/\/doi.org\/10.1007\/978-3-662-49529-2_13 10.1007\/978-3-662-49529-2_13 Djamal Belazzougui, Travis Gagie, Veli M\u00e4kinen, Marco Previtali, and Simon J. Puglisi. 2016b. Bidirectional variable-order de Bruijn graphs. In LATIN 2016: Theoretical Informatics (Lecture Notes in Computer Science), Evangelos Kranakis, Gonzalo Navarro, and Edgar Ch\u00e1vez (Eds.), Vol. 9644. Springer, 164--178. DOI:https:\/\/doi.org\/10.1007\/978-3-662-49529-2_13"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.14778\/2350229.2350275"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-32686-9_21"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/362686.362692"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/DCC.2015.70"},{"key":"e_1_2_1_14_1","volume-title":"WABI 2012: Algorithms in Bioinformatics (Lecture Notes in Computer Science)","author":"Bowe Alexander","unstructured":"Alexander Bowe , Taku Onodera , Kunihiko Sadakane , and Tetsuo Shibuya . 2012. Succinct de Bruijn graphs . In WABI 2012: Algorithms in Bioinformatics (Lecture Notes in Computer Science) , Ben Raphael and Jijun Tang (Eds.), Vol. 7534 . Springer-Verlag , 225--235. DOI:https:\/\/doi.org\/10.1007\/978-3-642-33122-0_18 10.1007\/978-3-642-33122-0_18 Alexander Bowe, Taku Onodera, Kunihiko Sadakane, and Tetsuo Shibuya. 2012. Succinct de Bruijn graphs. In WABI 2012: Algorithms in Bioinformatics (Lecture Notes in Computer Science), Ben Raphael and Jijun Tang (Eds.), Vol. 7534. Springer-Verlag, 225--235. DOI:https:\/\/doi.org\/10.1007\/978-3-642-33122-0_18"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1038\/s41587-018-0010-1"},{"key":"e_1_2_1_16_1","volume-title":"Rayan Chikhi et\u00a0al","author":"Bradnam Keith R.","year":"2013","unstructured":"Keith R. Bradnam , Joseph N. Fass , Anton Alexandrov , Paul Baranay , Michael Bechner , Inan\u00e7 Birol , S\u00e9bastien Boisvert , Jarrod A. Chapman , Guillaume Chapuis , Rayan Chikhi et\u00a0al . 2013 . Assemblathon 2: Evaluating de novo methods of genome assembly in three vertebrate species. GigaScience 2, 1 (2013). DOI:https:\/\/doi.org\/10.1186\/2047-217X-2-10 10.1186\/2047-217X-2-10 Keith R. Bradnam, Joseph N. Fass, Anton Alexandrov, Paul Baranay, Michael Bechner, Inan\u00e7 Birol, S\u00e9bastien Boisvert, Jarrod A. Chapman, Guillaume Chapuis, Rayan Chikhi et\u00a0al. 2013. Assemblathon 2: Evaluating de novo methods of genome assembly in three vertebrate species. GigaScience 2, 1 (2013). DOI:https:\/\/doi.org\/10.1186\/2047-217X-2-10"},{"key":"e_1_2_1_18_1","volume-title":"Simplitigs as an efficient and scalable representation of de Bruijn graphs. bioRxiv 903443","author":"B\u0159inda Karel","year":"2020","unstructured":"Karel B\u0159inda , Michael Baym , and Gregory Kucherov . 2020. Simplitigs as an efficient and scalable representation of de Bruijn graphs. bioRxiv 903443 ( 2020 ). DOI:https:\/\/doi.org\/10.1101\/2020.01.12.903443 10.1101\/2020.01.12.903443 Karel B\u0159inda, Michael Baym, and Gregory Kucherov. 2020. Simplitigs as an efficient and scalable representation of de Bruijn graphs. bioRxiv 903443 (2020). DOI:https:\/\/doi.org\/10.1101\/2020.01.12.903443"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1080\/15427951.2004.10129096"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-05269-4_4"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btw279"},{"key":"e_1_2_1_22_1","volume-title":"WABI 2012: Algorithms in Bioinformatics (Lecture Notes in Computer Science)","author":"Chikhi Rayan","unstructured":"Rayan Chikhi and Guillaume Rizk . 2012. Space-efficient and exact de Bruijn graph representation based on a Bloom filter . In WABI 2012: Algorithms in Bioinformatics (Lecture Notes in Computer Science) , Ben Raphael and Jijun Tang (Eds.), Vol. 7534 . Springer , 236--248. DOI:https:\/\/doi.org\/10.1007\/978-3-642-33122-0_19 10.1007\/978-3-642-33122-0_19 Rayan Chikhi and Guillaume Rizk. 2012. Space-efficient and exact de Bruijn graph representation based on a Bloom filter. In WABI 2012: Algorithms in Bioinformatics (Lecture Notes in Computer Science), Ben Raphael and Jijun Tang (Eds.), Vol. 7534. Springer, 236--248. DOI:https:\/\/doi.org\/10.1007\/978-3-642-33122-0_19"},{"key":"e_1_2_1_23_1","volume-title":"Improving on hash-based probabilistic sequence classification using multiple spaced seeds and multi-index Bloom filters. bioRxiv","author":"Chu Justin","year":"2018","unstructured":"Justin Chu , Hamid Mohamadi , Emre Erhan , Jeffery Tse , Readman Chiu , Sarah Yeo , and Inan\u00e7 Birol . 2018. Improving on hash-based probabilistic sequence classification using multiple spaced seeds and multi-index Bloom filters. bioRxiv ( 2018 ), 434795. DOI:https:\/\/doi.org\/10.1101\/434795 10.1101\/434795 Justin Chu, Hamid Mohamadi, Emre Erhan, Jeffery Tse, Readman Chiu, Sarah Yeo, and Inan\u00e7 Birol. 2018. Improving on hash-based probabilistic sequence classification using multiple spaced seeds and multi-index Bloom filters. bioRxiv (2018), 434795. DOI:https:\/\/doi.org\/10.1101\/434795"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/872757.872787"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btq697"},{"key":"e_1_2_1_26_1","volume-title":"Introduction to Algorithms","author":"Cormen Thomas H.","unstructured":"Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest , and Clifford Stein . 2009. Introduction to Algorithms . The MIT Press . Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. 2009. Introduction to Algorithms. The MIT Press."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.is.2015.01.002"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/321812.321820"},{"key":"e_1_2_1_29_1","volume-title":"Proceedings of the 10th ACM International on Conference on Emerging Networking Experiments and Technologies. Association for Computing Machinery, 75--88","author":"Fan Bin","unstructured":"Bin Fan , Dave G. Andersen , Michael Kaminsky , and Michael D. Mitzenmacher . 2014. Cuckoo filter: Practically better than bloom . In Proceedings of the 10th ACM International on Conference on Emerging Networking Experiments and Technologies. Association for Computing Machinery, 75--88 . DOI:https:\/\/doi.org\/10.1145\/2674005.2674994 10.1145\/2674005.2674994 Bin Fan, Dave G. Andersen, Michael Kaminsky, and Michael D. Mitzenmacher. 2014. Cuckoo filter: Practically better than bloom. In Proceedings of the 10th ACM International on Conference on Emerging Networking Experiments and Technologies. Association for Computing Machinery, 75--88. DOI:https:\/\/doi.org\/10.1145\/2674005.2674994"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/90.851975"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/1613676.1613680"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2000.892127"},{"key":"e_1_2_1_33_1","article-title":"Compressed representations of sequences and full-text indexes","volume":"3","author":"Ferragina Paolo","year":"2007","unstructured":"Paolo Ferragina , Giovanni Manzini , Veli M\u00e4kinen , and Gonzalo Navarro . 2007 . Compressed representations of sequences and full-text indexes . ACM Trans. Algor. 3 , 2 (2007). DOI:https:\/\/doi.org\/10.1145\/1240233.1240243 10.1145\/1240233.1240243 Paolo Ferragina, Giovanni Manzini, Veli M\u00e4kinen, and Gonzalo Navarro. 2007. Compressed representations of sequences and full-text indexes. ACM Trans. Algor. 3, 2 (2007). DOI:https:\/\/doi.org\/10.1145\/1240233.1240243","journal-title":"ACM Trans. Algor."},{"key":"e_1_2_1_34_1","first-page":"2913932","article-title":"deGSM: Memory scalable construction of large scale de Bruijn Graph. IEEE\/ACM","volume":"2019","author":"Guo Hongzhe","year":"2019","unstructured":"Hongzhe Guo , Yilei Fu , Yan Gao , Junyi Li , Yadong Wang , and Bo Liu . 2019 . deGSM: Memory scalable construction of large scale de Bruijn Graph. IEEE\/ACM Trans. Comput. Biol. Bioinf. (2019), Early access. DOI:https:\/\/doi.org\/10.1109\/TCBB. 2019 . 2913932 10.1109\/TCBB.2019.2913932 Hongzhe Guo, Yilei Fu, Yan Gao, Junyi Li, Yadong Wang, and Bo Liu. 2019. deGSM: Memory scalable construction of large scale de Bruijn Graph. IEEE\/ACM Trans. Comput. Biol. Bioinf. (2019), Early access. DOI:https:\/\/doi.org\/10.1109\/TCBB.2019.2913932","journal-title":"DOI:https:\/\/doi.org\/10.1109\/TCBB."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btz662"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/506309.506312"},{"key":"e_1_2_1_37_1","volume-title":"Bifrost--Highly parallel construction and indexing of colored and compacted de Bruijn graphs. bioRxiv","author":"Holley Guillaume","year":"2019","unstructured":"Guillaume Holley and P\u00e1ll Melsted . 2019. Bifrost--Highly parallel construction and indexing of colored and compacted de Bruijn graphs. bioRxiv ( 2019 ), 695338. DOI:https:\/\/doi.org\/10.1101\/695338 10.1101\/695338 Guillaume Holley and P\u00e1ll Melsted. 2019. Bifrost--Highly parallel construction and indexing of colored and compacted de Bruijn graphs. bioRxiv (2019), 695338. DOI:https:\/\/doi.org\/10.1101\/695338"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1186\/s13015-016-0066-8"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1038\/ng.1028"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1101\/gr.214346.116"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.csl.2009.12.001"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ymeth.2016.02.020"},{"key":"e_1_2_1_43_1","volume-title":"Read mapping on de Bruijn graphs. BMC Bioinf. 17","author":"Limasset Antoine","year":"2016","unstructured":"Antoine Limasset , Bastien Cazaux , Eric Rivals , and Pierre Peterlongo . 2016. Read mapping on de Bruijn graphs. BMC Bioinf. 17 ( 2016 ). DOI:https:\/\/doi.org\/10.1186\/s12859-016-1103-9 10.1186\/s12859-016-1103-9 Antoine Limasset, Bastien Cazaux, Eric Rivals, and Pierre Peterlongo. 2016. Read mapping on de Bruijn graphs. BMC Bioinf. 17 (2016). DOI:https:\/\/doi.org\/10.1186\/s12859-016-1103-9"},{"key":"e_1_2_1_44_1","volume-title":"Proceedings of the 16th International Symposium on Experimental Algorithms (SEA\u201917) (Leibniz International Proceedings in Informatics (LIPIcs)), Costas S","author":"Limasset Antoine","unstructured":"Antoine Limasset , Guillaume Rizk , Rayan Chikhi , and Pierre Peterlongo . 2017. Fast and scalable minimal perfect hashing for massive key sets . In Proceedings of the 16th International Symposium on Experimental Algorithms (SEA\u201917) (Leibniz International Proceedings in Informatics (LIPIcs)), Costas S . Iliopoulos, Solon P. Pissis, Simon J. Puglisi, and Rajeev Raman (Eds.), Vol. 75 . Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik , 25:1--25:16. DOI:https:\/\/doi.org\/10.4230\/LIPIcs.SEA.2017.25 10.4230\/LIPIcs.SEA.2017.25 Antoine Limasset, Guillaume Rizk, Rayan Chikhi, and Pierre Peterlongo. 2017. Fast and scalable minimal perfect hashing for massive key sets. In Proceedings of the 16th International Symposium on Experimental Algorithms (SEA\u201917) (Leibniz International Proceedings in Informatics (LIPIcs)), Costas S. Iliopoulos, Solon P. Pissis, Simon J. Puglisi, and Rajeev Raman (Eds.), Vol. 75. Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 25:1--25:16. DOI:https:\/\/doi.org\/10.4230\/LIPIcs.SEA.2017.25"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btx432"},{"key":"e_1_2_1_46_1","volume-title":"Tomescu","author":"M\u00e4kinen Veli","year":"2015","unstructured":"Veli M\u00e4kinen , Djamal Belazzougui , Fabio Cunial , and Alexandru I . Tomescu . 2015 . Genome-scale Algorithm\u00a0Design. Cambridge University Press . DOI:https:\/\/doi.org\/10.1017\/CBO9781139940023 10.1017\/CBO9781139940023 Veli M\u00e4kinen, Djamal Belazzougui, Fabio Cunial, and Alexandru I. Tomescu. 2015. Genome-scale Algorithm\u00a0Design. Cambridge University Press. DOI:https:\/\/doi.org\/10.1017\/CBO9781139940023"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1109\/DCC.2005.13"},{"key":"e_1_2_1_48_1","volume-title":"Data structures based on k-mers for querying large collections of sequencing datasets. bioRxiv 866756","author":"Marchet Camille","year":"2019","unstructured":"Camille Marchet , Christina Boucher , Simon J. Puglisi , Paul Medvedev , Mika\u00ebl Salson , and Rayan Chikhi . 2019a. Data structures based on k-mers for querying large collections of sequencing datasets. bioRxiv 866756 ( 2019 ). DOI:https:\/\/doi.org\/10.1101\/866756 10.1101\/866756 Camille Marchet, Christina Boucher, Simon J. Puglisi, Paul Medvedev, Mika\u00ebl Salson, and Rayan Chikhi. 2019a. Data structures based on k-mers for querying large collections of sequencing datasets. bioRxiv 866756 (2019). DOI:https:\/\/doi.org\/10.1101\/866756"},{"key":"e_1_2_1_49_1","volume-title":"Indexing de Bruijn graphs with minimizers. bioRxiv","author":"Marchet Camille","year":"2019","unstructured":"Camille Marchet , Ma\u00ebl Kerbiriou , and Antoine Limasset . 2019b. Indexing de Bruijn graphs with minimizers. bioRxiv ( 2019 ), 546309. DOI:https:\/\/doi.org\/10.1101\/546309 10.1101\/546309 Camille Marchet, Ma\u00ebl Kerbiriou, and Antoine Limasset. 2019b. Indexing de Bruijn graphs with minimizers. bioRxiv (2019), 546309. DOI:https:\/\/doi.org\/10.1101\/546309"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2018.03.035"},{"key":"e_1_2_1_51_1","unstructured":"Paul Medvedev Rayan Chikhi and Antoine Limasset. 2019. Bi-directed graphs in BCALM 2. Retrieved from https:\/\/github.com\/GATB\/bcalm\/blob\/master\/bidirected-graphs-in-bcalm2\/bidirected-graphs-in-bcalm2.md.  Paul Medvedev Rayan Chikhi and Antoine Limasset. 2019. Bi-directed graphs in BCALM 2. Retrieved from https:\/\/github.com\/GATB\/bcalm\/blob\/master\/bidirected-graphs-in-bcalm2\/bidirected-graphs-in-bcalm2.md."},{"key":"e_1_2_1_52_1","volume-title":"WABI 2007: Algorithms in Bioinformatics (Lecture Notes in Computer Science)","author":"Medvedev Paul","unstructured":"Paul Medvedev , Konstantinos Georgiou , Gene Myers , and Michael Brudno . 2007. Computability of models for sequence assembly . In WABI 2007: Algorithms in Bioinformatics (Lecture Notes in Computer Science) , Raffaele Giancarlo and Sridhar Hannenhalli (Eds.), Vol. 4645 . Springer , 289--301. DOI:https:\/\/doi.org\/10.1007\/978-3-540-74126-8_27 10.1007\/978-3-540-74126-8_27 Paul Medvedev, Konstantinos Georgiou, Gene Myers, and Michael Brudno. 2007. Computability of models for sequence assembly. In WABI 2007: Algorithms in Bioinformatics (Lecture Notes in Computer Science), Raffaele Giancarlo and Sridhar Hannenhalli (Eds.), Vol. 4645. Springer, 289--301. DOI:https:\/\/doi.org\/10.1007\/978-3-540-74126-8_27"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2002.803864"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btx067"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/bty632"},{"key":"e_1_2_1_56_1","volume-title":"Compact Data Structures: A Practical Approach","author":"Navarro Gonzalo","unstructured":"Gonzalo Navarro . 2016. Compact Data Structures: A Practical Approach . Cambridge University Press . DOI:https:\/\/doi.org\/10.1017\/CBO9781316588284 10.1017\/CBO9781316588284 Gonzalo Navarro. 2016. Compact Data Structures: A Practical Approach. Cambridge University Press. DOI:https:\/\/doi.org\/10.1017\/CBO9781316588284"},{"key":"e_1_2_1_57_1","article-title":"Fully functional static and dynamic succinct trees","volume":"10","author":"Navarro Gonzalo","year":"2014","unstructured":"Gonzalo Navarro and Kunihiko Sadakane . 2014 . Fully functional static and dynamic succinct trees . ACM Trans. Algor. 10 , 3 (2014), 16:1--16:39. DOI:https:\/\/doi.org\/10.1145\/2601073 10.1145\/2601073 Gonzalo Navarro and Kunihiko Sadakane. 2014. Fully functional static and dynamic succinct trees. ACM Trans. Algor. 10, 3 (2014), 16:1--16:39. DOI:https:\/\/doi.org\/10.1145\/2601073","journal-title":"ACM Trans. Algor."},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972870.6"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCBB.2018.2858797"},{"key":"e_1_2_1_60_1","volume-title":"Mantis: A fast, small, and exact large-scale sequence search index. Cell Syst.","author":"Pandey Prashant","year":"2018","unstructured":"Prashant Pandey , Fatemeh Almodaresi , Michael A. Bender , Michael Ferdman , Rob Johnson , and Rob Patro . 2018 . Mantis: A fast, small, and exact large-scale sequence search index. Cell Syst. (2018), 201--207. DOI:https:\/\/doi.org\/10.1016\/j.cels.2018.05.021 10.1016\/j.cels.2018.05.021 Prashant Pandey, Fatemeh Almodaresi, Michael A. Bender, Michael Ferdman, Rob Johnson, and Rob Patro. 2018. Mantis: A fast, small, and exact large-scale sequence search index. Cell Syst. (2018), 201--207. DOI:https:\/\/doi.org\/10.1016\/j.cels.2018.05.021"},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btx261"},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3035963"},{"key":"e_1_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btx636"},{"key":"e_1_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1089\/cmb.2016.0155"},{"key":"e_1_2_1_65_1","volume-title":"Representation of k-mer sets using spectrum-preserving string sets. bioRxiv 896928","author":"Rahman Amatur","year":"2020","unstructured":"Amatur Rahman and Paul Medvedev . 2020. Representation of k-mer sets using spectrum-preserving string sets. bioRxiv 896928 ( 2020 ). DOI:https:\/\/doi.org\/10.1101\/2020.01.07.896928 10.1101\/2020.01.07.896928 Amatur Rahman and Paul Medvedev. 2020. Representation of k-mer sets using spectrum-preserving string sets. bioRxiv 896928 (2020). DOI:https:\/\/doi.org\/10.1101\/2020.01.07.896928"},{"key":"e_1_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1145\/1290672.1290680"},{"key":"e_1_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/bth408"},{"key":"e_1_2_1_68_1","volume-title":"WABI 2013: Algorithms in Bioinformatics (Lecture Notes in Computer Science)","author":"Salikhov Kamil","unstructured":"Kamil Salikhov , Gustavo Sacomoto , and Gregory Kucherov . 2013. Using cascading Bloom filters to improve the memory usage for de Brujin graphs . In WABI 2013: Algorithms in Bioinformatics (Lecture Notes in Computer Science) , Aaron Darling and Jens Stoye (Eds.), Vol. 8126 . Springer , 364--376. DOI:https:\/\/doi.org\/10.1007\/978-3-642-40453-5_28 10.1007\/978-3-642-40453-5_28 Kamil Salikhov, Gustavo Sacomoto, and Gregory Kucherov. 2013. Using cascading Bloom filters to improve the memory usage for de Brujin graphs. In WABI 2013: Algorithms in Bioinformatics (Lecture Notes in Computer Science), Aaron Darling and Jens Stoye (Eds.), Vol. 8126. Springer, 364--376. DOI:https:\/\/doi.org\/10.1007\/978-3-642-40453-5_28"},{"key":"e_1_2_1_69_1","doi-asserted-by":"publisher","DOI":"10.1145\/872757.872770"},{"key":"e_1_2_1_70_1","doi-asserted-by":"publisher","DOI":"10.1038\/nmeth.4458"},{"key":"e_1_2_1_71_1","doi-asserted-by":"publisher","DOI":"10.1089\/cmb.2009.0062"},{"key":"e_1_2_1_72_1","doi-asserted-by":"publisher","DOI":"10.1146\/annurev-genom-090314-050032"},{"key":"e_1_2_1_73_1","doi-asserted-by":"publisher","DOI":"10.1038\/nbt.3442"},{"key":"e_1_2_1_74_1","doi-asserted-by":"publisher","DOI":"10.1089\/cmb.2017.0265"},{"key":"e_1_2_1_75_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btq230"},{"key":"e_1_2_1_76_1","doi-asserted-by":"publisher","DOI":"10.1089\/cmb.2017.0258"},{"key":"e_1_2_1_77_1","doi-asserted-by":"publisher","DOI":"10.1109\/SURV.2011.031611.00024"},{"key":"e_1_2_1_78_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-38036-5_24"},{"key":"e_1_2_1_79_1","doi-asserted-by":"publisher","DOI":"10.1186\/gb-2014-15-3-r46"},{"key":"e_1_2_1_80_1","volume-title":"SeqOthello: Query over RNA-seq experiments at scale. Genome Biol. 19","author":"Yu Ye","year":"2018","unstructured":"Ye Yu , Jinpeng Liu , Xinan Liu , Yi Zhang , Eamonn Magner , Chen Qian , and Jinze Liu . 2018. SeqOthello: Query over RNA-seq experiments at scale. Genome Biol. 19 ( 2018 ). DOI:https:\/\/doi.org\/10.1186\/s13059-018-1535-9 10.1186\/s13059-018-1535-9 Ye Yu, Jinpeng Liu, Xinan Liu, Yi Zhang, Eamonn Magner, Chen Qian, and Jinze Liu. 2018. SeqOthello: Query over RNA-seq experiments at scale. Genome Biol. 19 (2018). DOI:https:\/\/doi.org\/10.1186\/s13059-018-1535-9"},{"key":"e_1_2_1_81_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976007.15"}],"container-title":["ACM Computing Surveys"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3445967","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3445967","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T21:24:34Z","timestamp":1750195474000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3445967"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,3,8]]},"references-count":80,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2022,1,31]]}},"alternative-id":["10.1145\/3445967"],"URL":"https:\/\/doi.org\/10.1145\/3445967","relation":{},"ISSN":["0360-0300","1557-7341"],"issn-type":[{"value":"0360-0300","type":"print"},{"value":"1557-7341","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,3,8]]},"assertion":[{"value":"2019-04-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-10-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-03-08","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}