{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,21]],"date-time":"2025-09-21T17:27:15Z","timestamp":1758475635917},"reference-count":9,"publisher":"Oxford University Press (OUP)","issue":"6","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2009,3,15]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>Motivation: Alignment of biological sequences is one of the most frequently performed computer tasks. The current state of the art involves the use of (multiple) spaced seeds for producing high quality alignments. A particular important class is that of neighbor seeds which combine high sensitivity with reduced space requirements. Current algorithms for computing good neighbor seeds are very slow (exponential).<\/jats:p>\n               <jats:p>Results: We give a polynomial-time heuristic algorithm that computes better neighbor seeds than previous ones while being several orders of magnitude faster.<\/jats:p>\n               <jats:p>Contact: \u00a0ilie@csd.uwo.ca<\/jats:p>","DOI":"10.1093\/bioinformatics\/btp054","type":"journal-article","created":{"date-parts":[[2009,1,29]],"date-time":"2009-01-29T01:31:13Z","timestamp":1233192673000},"page":"822-823","source":"Crossref","is-referenced-by-count":4,"title":["Fast computation of neighbor seeds"],"prefix":"10.1093","volume":"25","author":[{"given":"Lucian","family":"Ilie","sequence":"first","affiliation":[{"name":"1 Department of Computer Science, University of Western Ontario, London N6A 5B7 and 2Department of Mathematics, Ryerson University, Toronto, M5B 2K3, Ontario, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Silvana","family":"Ilie","sequence":"additional","affiliation":[{"name":"1 Department of Computer Science, University of Western Ontario, London N6A 5B7 and 2Department of Mathematics, Ryerson University, Toronto, M5B 2K3, Ontario, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2009,1,28]]},"reference":[{"key":"2023051209124794300_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":"2023051209124794300_B2","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":"Cs\u0171ur\u00f6s","year":"2007","journal-title":"Algorithmica"},{"key":"2023051209124794300_B3","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":"2023051209124794300_B4","doi-asserted-by":"crossref","first-page":"417","DOI":"10.1142\/S0219720004000661","article-title":"Pattern-HunterII: highly sensitive and fast homology search","volume":"2","author":"Li","year":"2004","journal-title":"J. Bioinform. Comput. Biol."},{"key":"2023051209124794300_B5","doi-asserted-by":"crossref","first-page":"1435","DOI":"10.1126\/science.2983426","article-title":"Rapid and sensitive protein similarity searches","volume":"227","author":"Lipman","year":"1985","journal-title":"Science"},{"key":"2023051209124794300_B6","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":"2023051209124794300_B7","doi-asserted-by":"crossref","first-page":"443","DOI":"10.1016\/0022-2836(70)90057-4","article-title":"A general method applicable to the search for similarities in the amino acid sequence of two proteins","volume":"48","author":"Needleman","year":"1970","journal-title":"J. Mol. Biol."},{"key":"2023051209124794300_B8","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."},{"key":"2023051209124794300_B9","doi-asserted-by":"crossref","first-page":"521","DOI":"10.1142\/S0219720008003527","article-title":"MANGO: multiple alignment with n gapped oligos","volume":"6","author":"Zhang","year":"2008","journal-title":"J. Bioinform. Comput. Biol."}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/25\/6\/822\/50286701\/bioinformatics_25_6_822.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/25\/6\/822\/50286701\/bioinformatics_25_6_822.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,12]],"date-time":"2023-05-12T09:13:29Z","timestamp":1683882809000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/25\/6\/822\/251836"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,1,28]]},"references-count":9,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2009,3,15]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btp054","relation":{},"ISSN":["1367-4811","1367-4803"],"issn-type":[{"value":"1367-4811","type":"electronic"},{"value":"1367-4803","type":"print"}],"subject":[],"published-other":{"date-parts":[[2009,3,15]]},"published":{"date-parts":[[2009,1,28]]}}}