{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,26]],"date-time":"2026-02-26T20:34:35Z","timestamp":1772138075362,"version":"3.50.1"},"reference-count":25,"publisher":"Oxford University Press (OUP)","issue":"8","license":[{"start":{"date-parts":[[2025,7,24]],"date-time":"2025-07-24T00:00:00Z","timestamp":1753315200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/100000001","name":"US National Science Foundation","doi-asserted-by":"crossref","award":["2019797"],"award-info":[{"award-number":["2019797"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/100000001","name":"US National Science Foundation","doi-asserted-by":"crossref","award":["2145171"],"award-info":[{"award-number":["2145171"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/100000002","name":"US National Institutes of Health","doi-asserted-by":"publisher","award":["R01HG011065"],"award-info":[{"award-number":["R01HG011065"]}],"id":[{"id":"10.13039\/100000002","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2025,8,2]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:sec>\n                    <jats:title>Motivation<\/jats:title>\n                    <jats:p>Seeding is an essential preparatory step for many fundamental computational tasks that require large-scale sequence comparison. Substring-based seeding methods such as kmers are ideal for sequences with low error rates but struggle to achieve high sensitivity while maintaining a reasonable precision for error-prone long reads. SubseqHash, a novel subsequence-based seeding method we recently developed, achieves superior accuracy to substring-based methods in seeding sequences with high mutation\/error rates, while the only drawback is its computation speed.<\/jats:p>\n                  <\/jats:sec>\n                  <jats:sec>\n                    <jats:title>Results<\/jats:title>\n                    <jats:p>We propose SubseqHash2, an improved algorithm that can compute multiple sets of seeds in one run, by defining k orders over all length-k subsequences and finding the optimal subsequence under each of the k orders in a single dynamic programming framework. The algorithm is further accelerated using single instruction, multiple data instructions for parallel computing. The design of SubseqHash2 also allows it to generate the same sets of seeds for a string and its reverse complement by using symmetric random tables. We demonstrate that SubseqHash2 drastically outperforms popular substring-based methods including kmers, minimizers, syncmers, and Strobemers for three fundamental applications. In read mapping, SubseqHash2 can generate adequate seed matches for aligning hard reads that minimap2 fails on. In sequence alignment, SubseqHash2 achieves high coverage of correct seeds and low coverage of incorrect seeds. In overlap detection, seeds produced by SubseqHash2 lead to more correct overlapping pairs at the same false-positive rate. In all experiments, SubseqHash2 achieves a 10\u201350\u00d7 speedup over SubseqHash while maintaining nearly identical high accuracy. With all the algorithmic breakthroughs of SubseqHash2, we clear the path for the wide adoption of subsequence-based seeds in long-read analysis.<\/jats:p>\n                  <\/jats:sec>\n                  <jats:sec>\n                    <jats:title>Availability and implementation<\/jats:title>\n                    <jats:p>SubseqHash2 is available at https:\/\/github.com\/Shao-Group\/SubseqHash2 and have also been archived on Software Heritage (swh:1:dir:86738fc4b919eb6a9a26f7f533c25eb69f9a96d5).<\/jats:p>\n                  <\/jats:sec>","DOI":"10.1093\/bioinformatics\/btaf418","type":"journal-article","created":{"date-parts":[[2025,7,23]],"date-time":"2025-07-23T11:50:21Z","timestamp":1753271421000},"source":"Crossref","is-referenced-by-count":1,"title":["Efficient seeding for error-prone sequences with SubseqHash2"],"prefix":"10.1093","volume":"41","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-8499-4740","authenticated-orcid":false,"given":"Xiang","family":"Li","sequence":"first","affiliation":[{"name":"Department of Computer Science and Engineering, The Pennsylvania State University , Pennsylvania, PA 16802,","place":["United States"]}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5470-6621","authenticated-orcid":false,"given":"Ke","family":"Chen","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Engineering, The Pennsylvania State University , Pennsylvania, PA 16802,","place":["United States"]}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6112-5139","authenticated-orcid":false,"given":"Mingfu","family":"Shao","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Engineering, The Pennsylvania State University , Pennsylvania, PA 16802,","place":["United States"]},{"name":"Huck Institutes of the Life Sciences, The Pennsylvania State University , Pennsylvania, PA 16802,","place":["United States"]}]}],"member":"286","published-online":{"date-parts":[[2025,7,24]]},"reference":[{"key":"2025081319171094300_btaf418-B1","doi-asserted-by":"crossref","first-page":"321","DOI":"10.1016\/j.jda.2004.08.011","article-title":"Chaining algorithms for multiple genome comparison","volume":"3","author":"Abouelhoda","year":"2005","journal-title":"J Discrete Algorithms"},{"key":"2025081319171094300_btaf418-B2","doi-asserted-by":"crossref","first-page":"403","DOI":"10.1016\/S0022-2836(05)80360-2","article-title":"Basic local alignment search tool","volume":"215","author":"Altschul","year":"1990","journal-title":"J Mol Biol"},{"key":"2025081319171094300_btaf418-B3","doi-asserted-by":"publisher","author":"Califano","year":"1993","DOI":"10.1109\/CVPR.1993.341106"},{"key":"2025081319171094300_btaf418-B4","doi-asserted-by":"publisher","first-page":"712","DOI":"10.1145\/2897518.2897577","author":"Chakraborty","year":"2016"},{"key":"2025081319171094300_btaf418-B5","doi-asserted-by":"crossref","first-page":"170","DOI":"10.1038\/s41592-020-01056-5","article-title":"Haplotype-resolved de novo assembly using phased assembly graphs with hifiasm","volume":"18","author":"Cheng","year":"2021","journal-title":"Nat Methods"},{"key":"2025081319171094300_btaf418-B6","author":"Chin","year":"2019"},{"key":"2025081319171094300_btaf418-B7","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":"2025081319171094300_btaf418-B8","first-page":"246","author":"Jain","year":"2022"},{"key":"2025081319171094300_btaf418-B9","doi-asserted-by":"crossref","first-page":"722","DOI":"10.1101\/gr.215087.116","article-title":"Canu: scalable and accurate long-read assembly via adaptive k-mer weighting and repeat separation","volume":"27","author":"Koren","year":"2017","journal-title":"Genome Res"},{"key":"2025081319171094300_btaf418-B10","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":"2025081319171094300_btaf418-B11","doi-asserted-by":"crossref","first-page":"i232","DOI":"10.1093\/bioinformatics\/btad218","article-title":"Seeding with minimized subsequence","volume":"39","author":"Li","year":"2023","journal-title":"Bioinformatics"},{"key":"2025081319171094300_btaf418-B12","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":"2025081319171094300_btaf418-B13","doi-asserted-by":"publisher","first-page":"1162","author":"Maier","DOI":"10.1101\/gr.277645.123"},{"key":"2025081319171094300_btaf418-B14","doi-asserted-by":"crossref","first-page":"e341","DOI":"10.1093\/bioinformatics\/btl263","article-title":"Indel seeds for homology search","volume":"22","author":"Mak","year":"2006","journal-title":"Bioinformatics"},{"key":"2025081319171094300_btaf418-B15","doi-asserted-by":"crossref","first-page":"i13","DOI":"10.1093\/bioinformatics\/bty258","article-title":"Asymptotically optimal minimizers schemes","volume":"34","author":"Mar\u00e7ais","year":"2018","journal-title":"Bioinformatics"},{"key":"2025081319171094300_btaf418-B16","doi-asserted-by":"crossref","first-page":"i127","DOI":"10.1093\/bioinformatics\/btz354","article-title":"Locality-sensitive hashing for the edit distance","volume":"35","author":"Mar\u00e7ais","year":"2019","journal-title":"Bioinformatics"},{"key":"2025081319171094300_btaf418-B17","first-page":"38","author":"Myers","year":"1995"},{"key":"2025081319171094300_btaf418-B18","doi-asserted-by":"crossref","first-page":"1291","DOI":"10.1101\/gr.263566.120","article-title":"HiCanu: accurate assembly of segmental duplications, satellites, and allelic variants from high-fidelity long reads","volume":"30","author":"Nurk","year":"2020","journal-title":"Genome Res"},{"key":"2025081319171094300_btaf418-B19","doi-asserted-by":"publisher","first-page":"lqac092","DOI":"10.1093\/nargab\/lqac092","article-title":"Pbsim3: a simulator for all types of pacbio and ont long reads","volume":"4","author":"Ono","year":"2022","journal-title":"NAR Genom Bioinform"},{"key":"2025081319171094300_btaf418-B20","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":"2025081319171094300_btaf418-B21","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":"2025081319171094300_btaf418-B22","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":"2025081319171094300_btaf418-B23","doi-asserted-by":"publisher","first-page":"76","DOI":"10.1145\/872757.872770","author":"Schleimer","year":"2003"},{"key":"2025081319171094300_btaf418-B24","doi-asserted-by":"publisher","first-page":"1175","author":"Shaw","DOI":"10.1101\/gr.277637.122"},{"key":"2025081319171094300_btaf418-B25","doi-asserted-by":"crossref","first-page":"4838","DOI":"10.1093\/bioinformatics\/btaa252","article-title":"Overlap detection on long, error-prone sequencing reads via smooth q-gram","volume":"36","author":"Song","year":"2020","journal-title":"Bioinformatics"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/advance-article-pdf\/doi\/10.1093\/bioinformatics\/btaf418\/63841215\/btaf418.pdf","content-type":"application\/pdf","content-version":"am","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/41\/8\/btaf418\/63841215\/btaf418.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/41\/8\/btaf418\/63841215\/btaf418.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,13]],"date-time":"2025-08-13T23:17:21Z","timestamp":1755127041000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/doi\/10.1093\/bioinformatics\/btaf418\/8211825"}},"subtitle":[],"editor":[{"given":"Can","family":"Alkan","sequence":"additional","affiliation":[]}],"short-title":[],"issued":{"date-parts":[[2025,7,24]]},"references-count":25,"journal-issue":{"issue":"8","published-print":{"date-parts":[[2025,8,2]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btaf418","relation":{"has-preprint":[{"id-type":"doi","id":"10.1101\/2024.05.30.596711","asserted-by":"object"}]},"ISSN":["1367-4811"],"issn-type":[{"value":"1367-4811","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2025,8]]},"published":{"date-parts":[[2025,7,24]]},"article-number":"btaf418"}}