{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,17]],"date-time":"2026-02-17T15:30:51Z","timestamp":1771342251144,"version":"3.50.1"},"reference-count":35,"publisher":"Oxford University Press (OUP)","issue":"3","license":[{"start":{"date-parts":[[2024,2,20]],"date-time":"2024-02-20T00:00:00Z","timestamp":1708387200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["92270116"],"award-info":[{"award-number":["92270116"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["62071155"],"award-info":[{"award-number":["62071155"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Major Key Project of Peng Cheng Laboratory","award":["PCL2023AS7-1"],"award-info":[{"award-number":["PCL2023AS7-1"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2024,3,4]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:sec>\n                  <jats:title>Motivation<\/jats:title>\n                  <jats:p>Seeding is a rate-limiting stage in sequence alignment for next-generation sequencing reads. The existing optimization algorithms typically utilize hardware and machine-learning techniques to accelerate seeding. However, an efficient solution provided by professional next-generation sequencing compressors has been largely overlooked by far. In addition to achieving remarkable compression ratios by reordering reads, these compressors provide valuable insights for downstream alignment that reveal the repetitive computations accounting for more than 50% of seeding procedure in commonly used short read aligner BWA-MEM at typical sequencing coverage. Nevertheless, the exploited redundancy information is not fully realized or utilized.<\/jats:p>\n               <\/jats:sec>\n               <jats:sec>\n                  <jats:title>Results<\/jats:title>\n                  <jats:p>In this study, we present a compressive seeding algorithm, named CompSeed, to fill the gap. CompSeed, in collaboration with the existing reordering-based compression tools, finishes the BWA-MEM seeding process in about half the time by caching all intermediate seeding results in compact trie structures to directly answer repetitive inquiries that frequently cause random memory accesses. Furthermore, CompSeed demonstrates better performance as sequencing coverage increases, as it focuses solely on the small informative portion of sequencing reads after compression. The innovative strategy highlights the promising potential of integrating sequence compression and alignment to tackle the ever-growing volume of sequencing data.<\/jats:p>\n               <\/jats:sec>\n               <jats:sec>\n                  <jats:title>Availability and implementation<\/jats:title>\n                  <jats:p>CompSeed is available at https:\/\/github.com\/i-xiaohu\/CompSeed.<\/jats:p>\n               <\/jats:sec>","DOI":"10.1093\/bioinformatics\/btae100","type":"journal-article","created":{"date-parts":[[2024,2,19]],"date-time":"2024-02-19T13:30:26Z","timestamp":1708349426000},"source":"Crossref","is-referenced-by-count":2,"title":["A compressive seeding algorithm in conjunction with reordering-based compression"],"prefix":"10.1093","volume":"40","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-8318-835X","authenticated-orcid":false,"given":"Fahu","family":"Ji","sequence":"first","affiliation":[{"name":"School of Computer Science and Technology, Harbin Institute of Technology , Nan Gang District, Harbin 150080, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Qian","family":"Zhou","sequence":"additional","affiliation":[{"name":"Peng Cheng Laboratory , Nanshan District, Shenzhen 518055, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3713-3192","authenticated-orcid":false,"given":"Jue","family":"Ruan","sequence":"additional","affiliation":[{"name":"Shenzhen Branch, Guangdong Laboratory of Lingnan Modern Agriculture, Genome Analysis Laboratory of the Ministry of Agriculture and Rural Affairs, Agricultural Genomics Institute at Shenzhen, Chinese Academy of Agricultural Sciences , Dapeng District, Shenzhen 518120, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8479-6904","authenticated-orcid":false,"given":"Zexuan","family":"Zhu","sequence":"additional","affiliation":[{"name":"College of Computer Science and Software Engineering, Shenzhen University , Nanshan District, Shenzhen 518060, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8857-1785","authenticated-orcid":false,"given":"Xianming","family":"Liu","sequence":"additional","affiliation":[{"name":"School of Computer Science and Technology, Harbin Institute of Technology , Nan Gang District, Harbin 150080, China"},{"name":"Peng Cheng Laboratory , Nanshan District, Shenzhen 518055, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2024,2,20]]},"reference":[{"key":"2024032107582746400_btae100-B1","doi-asserted-by":"crossref","first-page":"3389","DOI":"10.1093\/nar\/25.17.3389","article-title":"Gapped BLAST and PSI-BLAST: a new generation of protein database search programs","volume":"25","author":"Altschul","year":"1997","journal-title":"Nucleic Acids Res"},{"key":"2024032107582746400_btae100-B2","doi-asserted-by":"crossref","first-page":"72","DOI":"10.1145\/2957324","article-title":"Computational biology in the 21st century: scaling with compressive algorithms","volume":"59","author":"Berger","year":"2016","journal-title":"Commun ACM"},{"key":"2024032107582746400_btae100-B3","doi-asserted-by":"crossref","first-page":"2674","DOI":"10.1093\/bioinformatics\/bty1015","article-title":"SPRING: a next-generation compressor for FASTQ data","volume":"35","author":"Chandak","year":"2019","journal-title":"Bioinformatics"},{"key":"2024032107582746400_btae100-B4","doi-asserted-by":"crossref","first-page":"1767","DOI":"10.1093\/nar\/gkp1137","article-title":"The Sanger FASTQ file format for sequences with quality scores, and the Solexa\/Illumina FASTQ variants","volume":"38","author":"Cock","year":"2010","journal-title":"Nucleic Acids Res"},{"key":"2024032107582746400_btae100-B5","doi-asserted-by":"crossref","first-page":"3712","DOI":"10.1093\/bioinformatics\/btaa265","article-title":"Vargas: heuristic-free alignment for assessing linear and graph read aligners","volume":"36","author":"Darby","year":"2020","journal-title":"Bioinformatics"},{"key":"2024032107582746400_btae100-B6","doi-asserted-by":"crossref","first-page":"156","DOI":"10.1093\/bioinformatics\/btl582","article-title":"Striped Smith\u2013Waterman speeds database searches six times over other SIMD implementations","volume":"23","author":"Farrar","year":"2007","journal-title":"Bioinformatics"},{"key":"2024032107582746400_btae100-B7","first-page":"390","author":"Ferragina","year":"2000"},{"key":"2024032107582746400_btae100-B8","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1146\/annurev-biodatasci-072018-021229","article-title":"Genomic data compression","volume":"2","author":"Hernaez","year":"2019","journal-title":"Annu Rev Biomed Data Sci"},{"key":"2024032107582746400_btae100-B9","author":"Ho","year":"2020"},{"key":"2024032107582746400_btae100-B10","first-page":"221","author":"Houtgast","year":"2015"},{"key":"2024032107582746400_btae100-B11","first-page":"130","author":"Houtgast","year":"2016"},{"key":"2024032107582746400_btae100-B12","doi-asserted-by":"crossref","first-page":"2404","DOI":"10.1093\/bioinformatics\/btac137","article-title":"BWA-MEME: BWA-MEM emulated with a machine learning approach","volume":"38","author":"Jung","year":"2022","journal-title":"Bioinformatics"},{"key":"2024032107582746400_btae100-B13","first-page":"656","article-title":"BLAT\u2014the BLAST-like alignment tool","volume":"12","author":"Kent","year":"2002","journal-title":"Genome Res"},{"key":"2024032107582746400_btae100-B14","doi-asserted-by":"crossref","first-page":"744","DOI":"10.1093\/bioinformatics\/btaa911","article-title":"Sapling: accelerating suffix array queries with learned data models","volume":"37","author":"Kirsche","year":"2021","journal-title":"Bioinformatics"},{"key":"2024032107582746400_btae100-B15","doi-asserted-by":"crossref","first-page":"2082","DOI":"10.1093\/bioinformatics\/btz919","article-title":"PgRC: pseudogenome-based read compressor","volume":"36","author":"Kowalski","year":"2020","journal-title":"Bioinformatics"},{"key":"2024032107582746400_btae100-B16","first-page":"489","author":"Kraska","year":"2018"},{"key":"2024032107582746400_btae100-B17","doi-asserted-by":"crossref","first-page":"357","DOI":"10.1038\/nmeth.1923","article-title":"Fast gapped-read alignment with Bowtie 2","volume":"9","author":"Langmead","year":"2012","journal-title":"Nat Methods"},{"key":"2024032107582746400_btae100-B18","doi-asserted-by":"crossref","first-page":"1838","DOI":"10.1093\/bioinformatics\/bts280","article-title":"Exploring single-sample SNP and INDEL calling with whole-genome de novo assembly","volume":"28","author":"Li","year":"2012","journal-title":"Bioinformatics"},{"key":"2024032107582746400_btae100-B19","author":"Li","year":"2013"},{"key":"2024032107582746400_btae100-B20","doi-asserted-by":"crossref","first-page":"1754","DOI":"10.1093\/bioinformatics\/btp324","article-title":"Fast and accurate short read alignment with Burrows\u2013Wheeler transform","volume":"25","author":"Li","year":"2009","journal-title":"Bioinformatics"},{"key":"2024032107582746400_btae100-B21","doi-asserted-by":"crossref","first-page":"2281","DOI":"10.1093\/bioinformatics\/btx189","article-title":"Kart: a divide-and-conquer algorithm for NGS read alignment","volume":"33","author":"Lin","year":"2017","journal-title":"Bioinformatics"},{"key":"2024032107582746400_btae100-B22","doi-asserted-by":"crossref","first-page":"3224","DOI":"10.1093\/bioinformatics\/btw371","article-title":"DeBGA: read alignment with de Bruijn graph-based seed and extension","volume":"32","author":"Liu","year":"2016","journal-title":"Bioinformatics"},{"key":"2024032107582746400_btae100-B23","doi-asserted-by":"crossref","first-page":"e1009229","DOI":"10.1371\/journal.pcbi.1009229","article-title":"Hamming-shifting graph of genomic short reads: efficient construction and its application for compression","volume":"17","author":"Liu","year":"2021","journal-title":"PLoS Comput Biol"},{"key":"2024032107582746400_btae100-B24","doi-asserted-by":"crossref","first-page":"93","DOI":"10.1186\/1756-0500-3-93","article-title":"CUDASW++ 2.0: enhanced Smith-Waterman protein database search on CUDA-enabled GPUs based on SIMT and virtualized SIMD abstractions","volume":"3","author":"Liu","year":"2010","journal-title":"BMC Res Notes"},{"key":"2024032107582746400_btae100-B25","doi-asserted-by":"crossref","first-page":"2066","DOI":"10.1093\/bioinformatics\/bty936","article-title":"Index suffix\u2013prefix overlaps by (w, k)-minimizer to generate long contigs for reads compression","volume":"35","author":"Liu","year":"2019","journal-title":"Bioinformatics"},{"key":"2024032107582746400_btae100-B26","doi-asserted-by":"crossref","first-page":"627","DOI":"10.1038\/nbt.2241","article-title":"Compressive genomics","volume":"30","author":"Loh","year":"2012","journal-title":"Nat Biotechnol"},{"key":"2024032107582746400_btae100-B27","doi-asserted-by":"crossref","first-page":"1185","DOI":"10.1038\/nmeth.2221","article-title":"The gem mapper: fast, accurate and versatile alignment by filtration","volume":"9","author":"Marco-Sola","year":"2012","journal-title":"Nat Methods"},{"key":"2024032107582746400_btae100-B28","first-page":"388","author":"Subramaniyan","year":"2021"},{"key":"2024032107582746400_btae100-B29","doi-asserted-by":"crossref","first-page":"11.10.1","DOI":"10.1002\/0471250953.bi1110s43","article-title":"From FastQ data to high-confidence variant calls: the Genome Analysis Toolkit best practices pipeline","volume":"43","author":"Van der Auwera","year":"2013","journal-title":"Curr Protoc Bioinformatics"},{"key":"2024032107582746400_btae100-B30","first-page":"314","author":"Vasimuddin","year":"2019"},{"key":"2024032107582746400_btae100-B31","doi-asserted-by":"crossref","first-page":"437","DOI":"10.1038\/s41586-022-04601-8","article-title":"The human pangenome project: a global resource to map genomic diversity","volume":"604","author":"Wang","year":"2022","journal-title":"Nature"},{"key":"2024032107582746400_btae100-B32","doi-asserted-by":"crossref","first-page":"2081","DOI":"10.1093\/bioinformatics\/btac066","article-title":"Performance optimization in DNA short-read alignment","volume":"38","author":"Wilton","year":"2022","journal-title":"Bioinformatics"},{"key":"2024032107582746400_btae100-B33","doi-asserted-by":"crossref","first-page":"3294","DOI":"10.1093\/bioinformatics\/btac333","article-title":"CURC: a CUDA-based reference-free read compressor","volume":"38","author":"Xie","year":"2022","journal-title":"Bioinformatics"},{"key":"2024032107582746400_btae100-B34","doi-asserted-by":"crossref","first-page":"374","DOI":"10.1038\/nbt.3511","article-title":"Compressive mapping for next-generation sequencing","volume":"34","author":"Yorukoglu","year":"2016","journal-title":"Nat Biotechnol"},{"key":"2024032107582746400_btae100-B35","doi-asserted-by":"crossref","first-page":"426","DOI":"10.1093\/bioinformatics\/btu656","article-title":"CompMap: a reference-based compression program to speed up read mapping to related reference sequences","volume":"31","author":"Zhu","year":"2015","journal-title":"Bioinformatics"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/advance-article-pdf\/doi\/10.1093\/bioinformatics\/btae100\/56721213\/btae100.pdf","content-type":"application\/pdf","content-version":"am","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/40\/3\/btae100\/57038878\/btae100.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/40\/3\/btae100\/57038878\/btae100.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,21]],"date-time":"2024-03-21T08:54:12Z","timestamp":1711011252000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/doi\/10.1093\/bioinformatics\/btae100\/7611649"}},"subtitle":[],"editor":[{"given":"Peter","family":"Robinson","sequence":"additional","affiliation":[],"role":[{"role":"editor","vocabulary":"crossref"}]}],"short-title":[],"issued":{"date-parts":[[2024,2,20]]},"references-count":35,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2024,3,4]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btae100","relation":{},"ISSN":["1367-4811"],"issn-type":[{"value":"1367-4811","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2024,3,1]]},"published":{"date-parts":[[2024,2,20]]},"article-number":"btae100"}}