{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,12]],"date-time":"2026-03-12T06:27:29Z","timestamp":1773296849720,"version":"3.50.1"},"reference-count":16,"publisher":"Oxford University Press (OUP)","issue":"20","license":[{"start":{"date-parts":[[2016,10,2]],"date-time":"2016-10-02T00:00:00Z","timestamp":1475366400000},"content-version":"vor","delay-in-days":2231,"URL":"http:\/\/creativecommons.org\/licenses\/by-nc\/2.0\/uk\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010,10,15]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>Motivation: The rapid development of next-generation sequencing technologies able to produce huge amounts of sequence data is leading to a wide range of new applications. This triggers the need for fast and accurate alignment software. Common techniques often restrict indels in the alignment to improve speed, whereas more flexible aligners are too slow for large-scale applications. Moreover, many current aligners are becoming inefficient as generated reads grow ever larger. Our goal with our new aligner GASSST (Global Alignment Short Sequence Search Tool) is thus 2-fold\u2014achieving high performance with no restrictions on the number of indels with a design that is still effective on long reads.<\/jats:p>\n               <jats:p>Results: We propose a new efficient filtering step that discards most alignments coming from the seed phase before they are checked by the costly dynamic programming algorithm. We use a carefully designed series of filters of increasing complexity and efficiency to quickly eliminate most candidate alignments in a wide range of configurations. The main filter uses a precomputed table containing the alignment score of short four base words aligned against each other. This table is reused several times by a new algorithm designed to approximate the score of the full dynamic programming algorithm. We compare the performance of GASSST against BWA, BFAST, SSAHA2 and PASS. We found that GASSST achieves high sensitivity in a wide range of configurations and faster overall execution time than other state-of-the-art aligners.<\/jats:p>\n               <jats:p>Availability: GASSST is distributed under the CeCILL software license at http:\/\/www.irisa.fr\/symbiose\/projects\/gassst\/<\/jats:p>\n               <jats:p>Contact: \u00a0guillaume.rizk@irisa.fr; dominique.lavenier@irisa.fr<\/jats:p>\n               <jats:p>Supplementary information: \u00a0Supplementary data are available at Bioinformatics online.<\/jats:p>","DOI":"10.1093\/bioinformatics\/btq485","type":"journal-article","created":{"date-parts":[[2010,8,26]],"date-time":"2010-08-26T00:33:02Z","timestamp":1282782782000},"page":"2534-2540","source":"Crossref","is-referenced-by-count":82,"title":["GASSST: global alignment short sequence search tool"],"prefix":"10.1093","volume":"26","author":[{"given":"Guillaume","family":"Rizk","sequence":"first","affiliation":[{"name":"1 Univ-Rennes 1\/IRISA and 2ENS-Cachan\/IRISA, IRISA - Symbiose Campus universitaire de Beaulieu, 35042 Rennes Cedex, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dominique","family":"Lavenier","sequence":"additional","affiliation":[{"name":"1 Univ-Rennes 1\/IRISA and 2ENS-Cachan\/IRISA, IRISA - Symbiose Campus universitaire de Beaulieu, 35042 Rennes Cedex, France"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2010,8,24]]},"reference":[{"key":"2023012507535959200_B1","article-title":"A block-sorting lossless data compression algorithm","volume-title":"Technical report 124","author":"Burrows","year":"1994"},{"key":"2023012507535959200_B2","doi-asserted-by":"crossref","first-page":"967","DOI":"10.1093\/bioinformatics\/btp087","article-title":"PASS: a program to align short sequences","volume":"25","author":"Campagna","year":"2009","journal-title":"Bioinformatics"},{"key":"2023012507535959200_B3","first-page":"390","article-title":"Opportunistic data structures with applications","volume-title":"Proceedings of the 41st Symposium on Foundations of Computer Science (FOCS 2000)","author":"Ferragina","year":"2000"},{"key":"2023012507535959200_B4","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,N.","year":"2009","journal-title":"PLoS ONE"},{"key":"2023012507535959200_B5","doi-asserted-by":"crossref","first-page":"2395","DOI":"10.1093\/bioinformatics\/btn429","article-title":"SeqMap: mapping massive amount of oligonucleotides to the genome","volume":"24","author":"Jiang","year":"2008","journal-title":"Bioinformatics"},{"key":"2023012507535959200_B6","doi-asserted-by":"crossref","first-page":"R25","DOI":"10.1186\/gb-2009-10-3-r25","article-title":"Ultrafast and memory-efficient alignment of short DNA sequences to the human genome","volume":"10","author":"Langmead","year":"2009","journal-title":"Genome Biol."},{"key":"2023012507535959200_B7","doi-asserted-by":"crossref","first-page":"1754","DOI":"10.1093\/bioinformatics\/btp324","article-title":"Fast and accurate short read alignment with Burrows-Wheeler transform","volume":"25","author":"Li","year":"2009","journal-title":"Bioinformatics"},{"key":"2023012507535959200_B8","doi-asserted-by":"crossref","first-page":"589","DOI":"10.1093\/bioinformatics\/btp698","article-title":"Fast and accurate long-read alignment with Burrows-Wheeler transform","volume":"26","author":"Li","year":"2010","journal-title":"Bioinformatics"},{"key":"2023012507535959200_B9","doi-asserted-by":"crossref","first-page":"1851","DOI":"10.1101\/gr.078212.108","article-title":"Mapping short DNA sequencing reads and calling variants using mapping quality scores","volume":"18","author":"Li","year":"2008","journal-title":"Genome Res."},{"key":"2023012507535959200_B10","doi-asserted-by":"crossref","first-page":"713","DOI":"10.1093\/bioinformatics\/btn025","article-title":"SOAP: short oligonucleotide alignment program","volume":"24","author":"Li","year":"2008","journal-title":"Bioinformatics"},{"key":"2023012507535959200_B11","doi-asserted-by":"crossref","first-page":"1966","DOI":"10.1093\/bioinformatics\/btp336","article-title":"SOAP2: an improved ultrafast tool for short read alignment","volume":"25","author":"Li","year":"2009","journal-title":"Bioinformatics"},{"key":"2023012507535959200_B12","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":"2023012507535959200_B13","doi-asserted-by":"crossref","first-page":"1725","DOI":"10.1101\/gr.194201","article-title":"SSAHA: a fast search method for large DNA databases","volume":"11","author":"Ning","year":"2001","journal-title":"Genome Res."},{"key":"2023012507535959200_B14","doi-asserted-by":"crossref","first-page":"e1000386","DOI":"10.1371\/journal.pcbi.1000386","article-title":"SHRiMP: accurate mapping of short color-space reads","volume":"5","author":"Rumble","year":"2009","journal-title":"PLoS Comput. Biol."},{"key":"2023012507535959200_B15","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."},{"issue":"Suppl. 1","key":"2023012507535959200_B16","first-page":"S17","article-title":"Short read DNA fragment anchoring algorithm","volume":"10","author":"Wendi","year":"2009","journal-title":"BMC Bioinformatics"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/26\/20\/2534\/48851664\/bioinformatics_26_20_2534.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/26\/20\/2534\/48851664\/bioinformatics_26_20_2534.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,25]],"date-time":"2023-01-25T07:54:26Z","timestamp":1674633266000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/26\/20\/2534\/194683"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,8,24]]},"references-count":16,"journal-issue":{"issue":"20","published-print":{"date-parts":[[2010,10,15]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btq485","relation":{},"ISSN":["1367-4811","1367-4803"],"issn-type":[{"value":"1367-4811","type":"electronic"},{"value":"1367-4803","type":"print"}],"subject":[],"published-other":{"date-parts":[[2010,10,15]]},"published":{"date-parts":[[2010,8,24]]}}}