{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,28]],"date-time":"2026-02-28T19:18:17Z","timestamp":1772306297107,"version":"3.50.1"},"reference-count":22,"publisher":"Oxford University Press (OUP)","issue":"4","license":[{"start":{"date-parts":[[2024,4,5]],"date-time":"2024-04-05T00:00:00Z","timestamp":1712275200000},"content-version":"vor","delay-in-days":7,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100004359","name":"Swedish Research Council","doi-asserted-by":"publisher","award":["2021\u201304000"],"award-info":[{"award-number":["2021\u201304000"]}],"id":[{"id":"10.13039\/501100004359","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2024,3,29]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:sec>\n                    <jats:title>Motivation<\/jats:title>\n                    <jats:p>Substrings of length k, commonly referred to as k-mers, play a vital role in sequence analysis. However, k-mers are limited to exact matches between sequences leading to alternative constructs. We recently introduced a class of new constructs, strobemers, that can match across substitutions and smaller insertions and deletions. Randstrobes, the most sensitive strobemer proposed in Sahlin (Effective sequence similarity detection with strobemers. Genome Res 2021a;31:2080\u201394. https:\/\/doi.org\/10.1101\/gr.275648.121), has been used in several bioinformatics applications such as read classification, short-read mapping, and read overlap detection. Recently, we showed that the more pseudo-random the behavior of the construction (measured in entropy), the more efficient the seeds for sequence similarity analysis. The level of pseudo-randomness depends on the construction operators, but no study has investigated the efficacy.<\/jats:p>\n                  <\/jats:sec>\n                  <jats:sec>\n                    <jats:title>Results<\/jats:title>\n                    <jats:p>In this study, we introduce novel construction methods, including a Binary Search Tree-based approach that improves time complexity over previous methods. To our knowledge, we are also the first to address biases in construction and design three metrics for measuring bias. Our evaluation shows that our methods have favorable speed and sampling uniformity compared to existing approaches. Lastly, guided by our results, we change the seed construction in strobealign, a short-read mapper, and find that the results change substantially. We suggest combining the two results to improve strobealign\u2019s accuracy for the shortest reads in our evaluated datasets. Our evaluation highlights sampling biases that can occur and provides guidance on which operators to use when implementing randstrobes.<\/jats:p>\n                  <\/jats:sec>\n                  <jats:sec>\n                    <jats:title>Availability and implementation<\/jats:title>\n                    <jats:p>All methods and evaluation benchmarks are available in a public Github repository at https:\/\/github.com\/Moein-Karami\/RandStrobes. The scripts for running the strobealign analysis are found at https:\/\/github.com\/NBISweden\/strobealign-evaluation.<\/jats:p>\n                  <\/jats:sec>","DOI":"10.1093\/bioinformatics\/btae187","type":"journal-article","created":{"date-parts":[[2024,4,4]],"date-time":"2024-04-04T12:55:56Z","timestamp":1712235356000},"source":"Crossref","is-referenced-by-count":3,"title":["Designing efficient randstrobes for sequence similarity analyses"],"prefix":"10.1093","volume":"40","author":[{"given":"Moein","family":"Karami","sequence":"first","affiliation":[{"name":"Department of Mathematics, Science for Life Laboratory, Stockholm University , Stockholm 106 91, Sweden"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Aryan","family":"Soltani Mohammadi","sequence":"additional","affiliation":[{"name":"Department of Mathematics, Science for Life Laboratory, Stockholm University , Stockholm 106 91, Sweden"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0680-200X","authenticated-orcid":false,"given":"Marcel","family":"Martin","sequence":"additional","affiliation":[{"name":"Department of Biochemistry and Biophysics, National Bioinformatics Infrastructure Sweden, Science for Life Laboratory, Stockholm University , Solna SE-17121, Sweden"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bar\u0131\u015f","family":"Ekim","sequence":"additional","affiliation":[{"name":"Computer Science and Artificial Intelligence Laboratory (CSAIL), Massachusetts Institute of Technology (MIT) , Cambridge, MA 02139, United States"},{"name":"Broad Institute of MIT and Harvard , Cambridge, MA 02142, United States"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8099-8258","authenticated-orcid":false,"given":"Wei","family":"Shen","sequence":"additional","affiliation":[{"name":"Department of Infectious Diseases, Key Laboratory of Molecular Biology for Infectious Diseases (Ministry of Education), Institute for Viral Hepatitis, The Second Affiliated Hospital of Chongqing Medical University , Chongqing 400010, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lidong","family":"Guo","sequence":"additional","affiliation":[{"name":"BGI Research , Qingdao 266555, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4487-7088","authenticated-orcid":false,"given":"Mengyang","family":"Xu","sequence":"additional","affiliation":[{"name":"BGI Research , Shenzhen 518083, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Giulio Ermanno","family":"Pibiri","sequence":"additional","affiliation":[{"name":"Department of Environmental Sciences, Informatics and Statistics, Ca\u2019 Foscari University of Venice , Venice 30172, Italy"},{"name":"ISTI-CNR , Pisa 56124, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8463-1675","authenticated-orcid":false,"given":"Rob","family":"Patro","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Center for Bioinformatics and Computational Biology, University of Maryland , College Park, MD 20742, United States"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7378-2320","authenticated-orcid":false,"given":"Kristoffer","family":"Sahlin","sequence":"additional","affiliation":[{"name":"Department of Mathematics, Science for Life Laboratory, Stockholm University , Stockholm 106 91, Sweden"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2024,4,5]]},"reference":[{"key":"2024042222161888300_btae187-B1","doi-asserted-by":"crossref","first-page":"249","DOI":"10.1186\/s13059-021-02443-7","article-title":"Technology dictates algorithms: recent developments in read alignment","volume":"22","author":"Alser","year":"2021","journal-title":"Genome Biol"},{"key":"2024042222161888300_btae187-B2","author":"Chin","year":"2019"},{"key":"2024042222161888300_btae187-B3","doi-asserted-by":"crossref","first-page":"e10805","DOI":"10.7717\/peerj.10805","article-title":"Syncmers are more sensitive than minimizers for selecting conserved k-mers in biological sequences","volume":"9","author":"Edgar","year":"2021","journal-title":"PeerJ"},{"key":"2024042222161888300_btae187-B4","doi-asserted-by":"crossref","first-page":"958","DOI":"10.1016\/j.cels.2021.08.009","article-title":"Minimizer-space de Bruijn graphs: whole-genome assembly of long reads in minutes on a personal computer","volume":"12","author":"Ekim","year":"2021","journal-title":"Cell Syst"},{"key":"2024042222161888300_btae187-B5","first-page":"1188","article-title":"Efficient mapping of accurate long reads in minimizer space with mapquik","volume":"33","author":"Ekim","year":"2023","journal-title":"Genome Res"},{"key":"2024042222161888300_btae187-B6","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1186\/s13015-024-00251-9","article-title":"Fulgor: a fast and compact k-mer index for large-scale matching and color queries","volume":"19","author":"Fan","year":"2024","journal-title":"Algorithms Mol Biol"},{"key":"2024042222161888300_btae187-B7","doi-asserted-by":"crossref","first-page":"lqad004","DOI":"10.1093\/nargab\/lqad004","article-title":"Blend: a fast, memory-efficient and accurate mechanism to find fuzzy seed matches in genome analysis","volume":"5","author":"Firtina","year":"2023","journal-title":"NAR Genom Bioinform"},{"key":"2024042222161888300_btae187-B8","doi-asserted-by":"crossref","first-page":"3094","DOI":"10.1093\/bioinformatics\/bty191","article-title":"Minimap2: pairwise alignment for nucleotide sequences","volume":"34","author":"Li","year":"2018","journal-title":"Bioinformatics"},{"key":"2024042222161888300_btae187-B9","doi-asserted-by":"crossref","first-page":"440","DOI":"10.1093\/bioinformatics\/18.3.440","article-title":"PatternHunter: faster and more sensitive homology search","volume":"18","author":"Ma","year":"2002","journal-title":"Bioinformatics"},{"key":"2024042222161888300_btae187-B10","first-page":"1162","article-title":"Entropy predicts sensitivity of pseudo-random seeds","volume":"33","author":"Maier","year":"2023","journal-title":"Genome Res"},{"key":"2024042222161888300_btae187-B11","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1101\/gr.260604.119","article-title":"Data structures based on k-mers for querying large collections of sequencing data sets","volume":"31","author":"Marchet","year":"2021","journal-title":"Genome Res"},{"key":"2024042222161888300_btae187-B12","doi-asserted-by":"crossref","first-page":"3492","DOI":"10.1093\/bioinformatics\/btw397","article-title":"ntHash: recursive nucleotide hashing","volume":"32","author":"Mohamadi","year":"2016","journal-title":"Bioinformatics"},{"key":"2024042222161888300_btae187-B13","doi-asserted-by":"crossref","first-page":"2940","DOI":"10.1038\/s41467-023-38553-y","article-title":"Reference-free assembly of long-read transcriptome sequencing data with rna-bloom2","volume":"14","author":"Nip","year":"2023","journal-title":"Nat Commun"},{"key":"2024042222161888300_btae187-B14","doi-asserted-by":"crossref","first-page":"44","DOI":"10.1126\/science.abj6987","article-title":"The complete sequence of a human genome","volume":"376","author":"Nurk","year":"2022","journal-title":"Science"},{"key":"2024042222161888300_btae187-B15","doi-asserted-by":"crossref","first-page":"3363","DOI":"10.1093\/bioinformatics\/bth408","article-title":"Reducing storage requirements for biological sequence comparison","volume":"20","author":"Roberts","year":"2004","journal-title":"Bioinformatics"},{"key":"2024042222161888300_btae187-B16","doi-asserted-by":"crossref","first-page":"2080","DOI":"10.1101\/gr.275648.121","article-title":"Effective sequence similarity detection with strobemers","volume":"31","author":"Sahlin","year":"2021","journal-title":"Genome Res"},{"key":"2024042222161888300_btae187-B17","author":"Sahlin","year":"2021"},{"key":"2024042222161888300_btae187-B18","doi-asserted-by":"crossref","first-page":"260","DOI":"10.1186\/s13059-022-02831-7","article-title":"Strobealign: flexible seed size enables ultra-fast and accurate read alignment","volume":"23","author":"Sahlin","year":"2022","journal-title":"Genome Biol"},{"key":"2024042222161888300_btae187-B19","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1038\/s41467-020-20340-8","article-title":"Error correction enables use of Oxford Nanopore technology for reference-free transcriptome analysis","volume":"12","author":"Sahlin","year":"2021","journal-title":"Nat Commun"},{"key":"2024042222161888300_btae187-B20","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1186\/s13059-023-02972-3","article-title":"A survey of mapping algorithms in the long-reads era","volume":"24","author":"Sahlin","year":"2023","journal-title":"Genome Biol"},{"key":"2024042222161888300_btae187-B21","doi-asserted-by":"crossref","first-page":"1175","DOI":"10.1101\/gr.277637.122","article-title":"Proving sequence aligners can guarantee accuracy in almost o(m log n) time through an average-case analysis of the seed-chain-extend heuristic","volume":"33","author":"Shaw","year":"2023","journal-title":"Genome Res"},{"key":"2024042222161888300_btae187-B22","article-title":"Symbiont-screener: a reference-free tool to separate host sequences from symbionts for error-prone long reads","volume":"10","author":"Xu","year":"2023","journal-title":"Front Mar Sci"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/advance-article-pdf\/doi\/10.1093\/bioinformatics\/btae187\/57173696\/btae187.pdf","content-type":"application\/pdf","content-version":"am","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/40\/4\/btae187\/57303432\/btae187.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/40\/4\/btae187\/57303432\/btae187.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,11,15]],"date-time":"2024-11-15T13:18:15Z","timestamp":1731676695000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/doi\/10.1093\/bioinformatics\/btae187\/7641534"}},"subtitle":[],"editor":[{"given":"Alfonso","family":"Valencia","sequence":"additional","affiliation":[],"role":[{"role":"editor","vocabulary":"crossref"}]}],"short-title":[],"issued":{"date-parts":[[2024,3,29]]},"references-count":22,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2024,3,29]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btae187","relation":{"has-preprint":[{"id-type":"doi","id":"10.1101\/2023.10.11.561924","asserted-by":"object"}]},"ISSN":["1367-4811"],"issn-type":[{"value":"1367-4811","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2024,4,1]]},"published":{"date-parts":[[2024,3,29]]},"article-number":"btae187"}}