{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,29]],"date-time":"2026-03-29T01:13:33Z","timestamp":1774746813236,"version":"3.50.1"},"reference-count":38,"publisher":"Oxford University Press (OUP)","issue":"9","license":[{"start":{"date-parts":[[2020,12,7]],"date-time":"2020-12-07T00:00:00Z","timestamp":1607299200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/academic.oup.com\/journals\/pages\/open_access\/funder_policies\/chorus\/standard_publication_model"}],"funder":[{"name":"NSER","award":["R3143A01"],"award-info":[{"award-number":["R3143A01"]}]},{"name":"Research Tools and Instruments","award":["R3143A07"],"award-info":[{"award-number":["R3143A07"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2021,6,9]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:sec>\n                  <jats:title>Motivation<\/jats:title>\n                  <jats:p>Sequence similarity is the most frequently used procedure in biological research, as proved by the widely used BLAST program. The consecutive seed used by BLAST can be dramatically improved by considering multiple spaced seeds. Finding the best seeds is a hard problem and much effort went into developing heuristic algorithms and software for designing highly sensitive spaced seeds.<\/jats:p>\n               <\/jats:sec>\n               <jats:sec>\n                  <jats:title>Results<\/jats:title>\n                  <jats:p>We introduce a new algorithm and software, ALeS, that produces more sensitive seeds than the current state-of-the-art programs, as shown by extensive testing. We also accurately estimate the sensitivity of a seed, enabling its computation for arbitrary seeds.<\/jats:p>\n               <\/jats:sec>\n               <jats:sec>\n                  <jats:title>Availabilityand implementation<\/jats:title>\n                  <jats:p>The source code is freely available at github.com\/lucian-ilie\/ALeS.<\/jats:p>\n               <\/jats:sec>\n               <jats:sec>\n                  <jats:title>Supplementary information<\/jats:title>\n                  <jats:p>Supplementary data are available at Bioinformatics online.<\/jats:p>\n               <\/jats:sec>","DOI":"10.1093\/bioinformatics\/btaa945","type":"journal-article","created":{"date-parts":[[2020,10,27]],"date-time":"2020-10-27T20:13:52Z","timestamp":1603829632000},"page":"1206-1210","source":"Crossref","is-referenced-by-count":4,"title":["ALeS: adaptive-length spaced-seed design"],"prefix":"10.1093","volume":"37","author":[{"given":"Arnab","family":"Mallik","sequence":"first","affiliation":[{"name":"Department of Computer Science, University of Western Ontario , London, ON N6A 5B7, Canada"}]},{"given":"Lucian","family":"Ilie","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Western Ontario , London, ON N6A 5B7, Canada"}]}],"member":"286","published-online":{"date-parts":[[2020,12,7]]},"reference":[{"key":"2023051706061983800_btaa945-B1","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":"2023051706061983800_btaa945-B2","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":"2023051706061983800_btaa945-B3","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1155\/2015\/196591","article-title":"Spaced seed data structures for de novo assembly","volume":"2015","author":"Birol","year":"2015","journal-title":"Comp. Funct. Genom"},{"key":"2023051706061983800_btaa945-B4","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1038\/nmeth.3176","article-title":"Fast and sensitive protein alignment using diamond","volume":"12","author":"Buchfink","year":"2015","journal-title":"Nat. Methods"},{"key":"2023051706061983800_btaa945-B5","doi-asserted-by":"crossref","first-page":"342","DOI":"10.1016\/j.jcss.2004.12.003","article-title":"Designing seeds for similarity search in genomic DNA","volume":"70","author":"Buhler","year":"2005","journal-title":"J. Comput. Syst. Sci"},{"key":"2023051706061983800_btaa945-B6","doi-asserted-by":"crossref","first-page":"1053","DOI":"10.1093\/bioinformatics\/bth037","article-title":"Good spaced seeds for homology search","volume":"20","author":"Choi","year":"2004","journal-title":"Bioinformatics"},{"key":"2023051706061983800_btaa945-B7","doi-asserted-by":"crossref","first-page":"187","DOI":"10.1007\/s00453-007-0062-y","article-title":"Rapid homology search with neighbor seeds","volume":"48","author":"Csuros","year":"2007","journal-title":"Algorithmica"},{"key":"2023051706061983800_btaa945-B8","doi-asserted-by":"crossref","first-page":"1011","DOI":"10.1093\/bioinformatics\/btr046","article-title":"Shrimp2: sensitive yet practical short read mapping","volume":"27","author":"David","year":"2011","journal-title":"Bioinformatics"},{"key":"2023051706061983800_btaa945-B9","doi-asserted-by":"crossref","first-page":"204","DOI":"10.1007\/978-3-642-32650-9_19","volume-title":"International Conference on Swarm Intelligence (ANTS 2012)","author":"Do Duc","year":"2012"},{"key":"2023051706061983800_btaa945-B10","doi-asserted-by":"crossref","first-page":"1550011","DOI":"10.1142\/S0219720015500110","article-title":"Multiple seeds sensitivity using a single seed with threshold","volume":"13","author":"Egidi","year":"2015","journal-title":"J. Bioinf. Comput. Biol"},{"key":"2023051706061983800_btaa945-B11","doi-asserted-by":"crossref","first-page":"1195","DOI":"10.1093\/bioinformatics\/btm114","article-title":"A fast and flexible approach to oligonucleotide probe design for genomes and gene families","volume":"23","author":"Feng","year":"2007","journal-title":"Bioinformatics"},{"key":"2023051706061983800_btaa945-B12","doi-asserted-by":"crossref","first-page":"88","DOI":"10.1016\/j.tcs.2017.05.023","article-title":"Metagenomic reads binning with spaced seeds","volume":"698","author":"Girotto","year":"2017","journal-title":"Theor. Comput. Sci"},{"key":"2023051706061983800_btaa945-B13","doi-asserted-by":"crossref","first-page":"441","DOI":"10.1186\/s12859-018-2415-8","article-title":"Efficient computation of spaced seed hashing with block indexing","volume":"19","author":"Girotto","year":"2018","journal-title":"BMC Bioinformatics"},{"key":"2023051706061983800_btaa945-B14","doi-asserted-by":"crossref","first-page":"e1005107","DOI":"10.1371\/journal.pcbi.1005107","article-title":"rasbhari: optimizing spaced seeds for database searching, read mapping and alignment-free sequence comparison","volume":"12","author":"Hahn","year":"2016","journal-title":"PLOS Comput. Biol"},{"key":"2023051706061983800_btaa945-B15","doi-asserted-by":"crossref","first-page":"e7767","DOI":"10.1371\/journal.pone.0007767","article-title":"Bfast: an alignment tool for large scale genome resequencing","volume":"4","author":"Homer","year":"2009","journal-title":"PLoS One"},{"key":"2023051706061983800_btaa945-B16","doi-asserted-by":"crossref","first-page":"2969","DOI":"10.1093\/bioinformatics\/btm422","article-title":"Multiple spaced seeds for homology search","volume":"23","author":"Ilie","year":"2007","journal-title":"Bioinformatics"},{"key":"2023051706061983800_btaa945-B17","doi-asserted-by":"crossref","first-page":"822","DOI":"10.1093\/bioinformatics\/btp054","article-title":"Fast computation of neighbor seeds","volume":"25","author":"Ilie","year":"2009","journal-title":"Bioinformatics"},{"key":"2023051706061983800_btaa945-B18","doi-asserted-by":"crossref","first-page":"280","DOI":"10.1186\/1471-2164-12-280","article-title":"Seeds for effective oligonucleotide design","volume":"12","author":"Ilie","year":"2011","journal-title":"BMC Genomics"},{"key":"2023051706061983800_btaa945-B19","doi-asserted-by":"crossref","first-page":"2433","DOI":"10.1093\/bioinformatics\/btr368","article-title":"Speed: fast computation of sensitive spaced seeds","volume":"27","author":"Ilie","year":"2011","journal-title":"Bioinformatics"},{"key":"2023051706061983800_btaa945-B20","doi-asserted-by":"crossref","first-page":"69","DOI":"10.1186\/1471-2105-14-69","article-title":"Bond: basic oligonucleotide design","volume":"14","author":"Ilie","year":"2013","journal-title":"BMC Bioinformatics"},{"key":"2023051706061983800_btaa945-B21","doi-asserted-by":"crossref","first-page":"123","DOI":"10.1186\/1756-0500-5-123","article-title":"Efficient computation of spaced seeds","volume":"5","author":"Ilie","year":"2012","journal-title":"BMC Res. Notes"},{"key":"2023051706061983800_btaa945-B22","doi-asserted-by":"crossref","first-page":"253","DOI":"10.1016\/S0166-218X(03)00382-2","article-title":"On spaced seeds for similarity search","volume":"138","author":"Keich","year":"2004","journal-title":"Discrete Appl. Math"},{"key":"2023051706061983800_btaa945-B23","doi-asserted-by":"crossref","first-page":"487","DOI":"10.1101\/gr.113985.110","article-title":"Adaptive seeds tame genomic sequence comparison","volume":"21","author":"Kie\u0142basa","year":"2011","journal-title":"Genome Res"},{"key":"2023051706061983800_btaa945-B24","doi-asserted-by":"crossref","first-page":"238","DOI":"10.1089\/cmb.2006.0008","article-title":"Generalized correlation functions and their applications in selection of optimal multiple spaced seeds for homology search","volume":"14","author":"Kong","year":"2007","journal-title":"J. Comput. Biol"},{"key":"2023051706061983800_btaa945-B25","doi-asserted-by":"crossref","first-page":"553","DOI":"10.1142\/S0219720006001977","article-title":"A unifying framework for seed sensitivity and its application to subset seeds","volume":"04","author":"Kucherov","year":"2006","journal-title":"J. Bioinf. Comput. Biol"},{"key":"2023051706061983800_btaa945-B26","doi-asserted-by":"crossref","first-page":"giy148","DOI":"10.1093\/gigascience\/giy148","article-title":"Prot-spam: fast alignment-free phylogeny reconstruction based on whole-proteome sequences","volume":"8","author":"Leimeister","year":"2019","journal-title":"GigaScience"},{"key":"2023051706061983800_btaa945-B27","doi-asserted-by":"crossref","first-page":"417","DOI":"10.1142\/S0219720004000661","article-title":"Patternhunter II: highly sensitive and fast homology search","volume":"2","author":"Li","year":"2004","journal-title":"J. Bioinform. Comput. Biol"},{"key":"2023051706061983800_btaa945-B28","doi-asserted-by":"crossref","first-page":"485","DOI":"10.1186\/s12859-017-1871-x","article-title":"SPRINT: ultrafast protein\u2013protein interaction prediction of the entire human interactome","volume":"18","author":"Li","year":"2017","journal-title":"BMC Bioinformatics"},{"key":"2023051706061983800_btaa945-B29","first-page":"btaa750","article-title":"DELPHI: accurate deep ensemble model for protein interaction sites prediction","author":"Li","year":"2020","journal-title":"Bioinformatics"},{"key":"2023051706061983800_btaa945-B30","doi-asserted-by":"crossref","first-page":"1120","DOI":"10.1016\/j.ipl.2009.07.008","article-title":"Seed optimization for IID similarities is no easier than optimal golomb ruler design","volume":"109","author":"Ma","year":"2009","journal-title":"Inf. Process. Lett"},{"key":"2023051706061983800_btaa945-B31","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":"2023051706061983800_btaa945-B32","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1186\/s13015-017-0092-1","article-title":"Best hits of 11110110111: model-free selection and parameter-free sensitivity calculation of spaced seeds","volume":"12","author":"No\u00e9","year":"2017","journal-title":"Algorithms Mol. Biol"},{"key":"2023051706061983800_btaa945-B33","doi-asserted-by":"crossref","first-page":"W540","DOI":"10.1093\/nar\/gki478","article-title":"YASS: enhancing the sensitivity of DNA similarity search","volume":"33","author":"No\u00e9","year":"2005","journal-title":"Nucleic Acids Res"},{"key":"2023051706061983800_btaa945-B34","doi-asserted-by":"crossref","first-page":"947","DOI":"10.1089\/cmb.2014.0173","article-title":"A coverage criterion for spaced seeds and its applications to support vector machine string kernels and k-mer distances","volume":"21","author":"No\u00e9","year":"2014","journal-title":"J. Comput. Biol"},{"key":"2023051706061983800_btaa945-B35","doi-asserted-by":"crossref","first-page":"3823","DOI":"10.1093\/bioinformatics\/btw542","article-title":"Higher classification sensitivity of short metagenomic reads with CLARK-S","volume":"32","author":"Ounit","year":"2016","journal-title":"Bioinformatics"},{"key":"2023051706061983800_btaa945-B36","article-title":"Iterative spaced seed hashing: closing the gap between spaced seed hashing and k-mer hashing","author":"Petrucci","year":"2019","journal-title":"J. Comput. Biol"},{"key":"2023051706061983800_btaa945-B37","doi-asserted-by":"crossref","first-page":"e0228070","DOI":"10.1371\/journal.pone.0228070","article-title":"The number of k-mer matches between two DNA sequences as a function of k and applications to estimate phylogenetic distances","volume":"15","author":"R\u00f6hling","year":"2020","journal-title":"PLoS One"},{"key":"2023051706061983800_btaa945-B38","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1016\/0022-2836(81)90087-5","article-title":"Identification of common molecular subsequences","volume":"147","author":"Smith","year":"1981","journal-title":"J. Mol. Biol"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/academic.oup.com\/bioinformatics\/advance-article-pdf\/doi\/10.1093\/bioinformatics\/btaa945\/34109161\/btaa945.pdf","content-type":"application\/pdf","content-version":"am","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/37\/9\/1206\/50359658\/btaa945.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/37\/9\/1206\/50359658\/btaa945.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,17]],"date-time":"2023-05-17T06:13:07Z","timestamp":1684303987000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/37\/9\/1206\/5952669"}},"subtitle":[],"editor":[{"given":"Valencia","family":"Alfonso","sequence":"additional","affiliation":[]}],"short-title":[],"issued":{"date-parts":[[2020,12,7]]},"references-count":38,"journal-issue":{"issue":"9","published-print":{"date-parts":[[2021,6,9]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btaa945","relation":{},"ISSN":["1367-4803","1367-4811"],"issn-type":[{"value":"1367-4803","type":"print"},{"value":"1367-4811","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2021,5,1]]},"published":{"date-parts":[[2020,12,7]]}}}