{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,6]],"date-time":"2026-05-06T07:59:30Z","timestamp":1778054370306,"version":"3.51.4"},"reference-count":28,"publisher":"Oxford University Press (OUP)","issue":"14","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012,7,15]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>Motivation: New high-throughput sequencing technologies have promoted the production of short reads with dramatically low unit cost. The explosive growth of short read datasets poses a challenge to the mapping of short reads to reference genomes, such as the human genome, in terms of alignment quality and execution speed.<\/jats:p>\n               <jats:p>Results: We present CUSHAW, a parallelized short read aligner based on the compute unified device architecture (CUDA) parallel programming model. We exploit CUDA-compatible graphics hardware as accelerators to achieve fast speed. Our algorithm uses a quality-aware bounded search approach based on the Burrows\u2013Wheeler transform (BWT) and the Ferragina\u2013Manzini index to reduce the search space and achieve high alignment quality. Performance evaluation, using simulated as well as real short read datasets, reveals that our algorithm running on one or two graphics processing units achieves significant speedups in terms of execution time, while yielding comparable or even better alignment quality for paired-end alignments compared with three popular BWT-based aligners: Bowtie, BWA and SOAP2. CUSHAW also delivers competitive performance in terms of single-nucleotide polymorphism calling for an Escherichia coli test dataset.<\/jats:p>\n               <jats:p>Availability: \u00a0http:\/\/cushaw.sourceforge.net.<\/jats:p>\n               <jats:p>Contact: \u00a0liuy@uni-mainz.de; bertil.schmidt@uni-mainz.de<\/jats:p>\n               <jats:p>Supplementary information: Supplementary data are available at Bioinformatics online.<\/jats:p>","DOI":"10.1093\/bioinformatics\/bts276","type":"journal-article","created":{"date-parts":[[2012,5,11]],"date-time":"2012-05-11T00:28:30Z","timestamp":1336696110000},"page":"1830-1837","source":"Crossref","is-referenced-by-count":124,"title":["CUSHAW: a CUDA compatible short read aligner to large genomes based on the Burrows\u2013Wheeler transform"],"prefix":"10.1093","volume":"28","author":[{"given":"Yongchao","family":"Liu","sequence":"first","affiliation":[{"name":"1 School of Computer Engineering, Nanyang Technological University, Singapore 639798, Singapore and 2Institut f\u00fcr Informatik, Johannes Gutenberg University Mainz 55099, Germany"},{"name":"1 School of Computer Engineering, Nanyang Technological University, Singapore 639798, Singapore and 2Institut f\u00fcr Informatik, Johannes Gutenberg University Mainz 55099, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bertil","family":"Schmidt","sequence":"additional","affiliation":[{"name":"1 School of Computer Engineering, Nanyang Technological University, Singapore 639798, Singapore and 2Institut f\u00fcr Informatik, Johannes Gutenberg University Mainz 55099, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Douglas L.","family":"Maskell","sequence":"additional","affiliation":[{"name":"1 School of Computer Engineering, Nanyang Technological University, Singapore 639798, Singapore and 2Institut f\u00fcr Informatik, Johannes Gutenberg University Mainz 55099, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2012,5,9]]},"reference":[{"key":"2023012512434049000_B1","doi-asserted-by":"crossref","first-page":"1351","DOI":"10.1093\/bioinformatics\/btr151","article-title":"Exact and complete short read alignment to microbial genomes using GPU programming","volume":"27","author":"Blom","year":"2011","journal-title":"Bioinformatics"},{"key":"2023012512434049000_B2","volume-title":"A block sorting lossless data compression algorithm.","author":"Burrows","year":"1994"},{"key":"2023012512434049000_B3","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":"2023012512434049000_B4","doi-asserted-by":"crossref","first-page":"186","DOI":"10.1101\/gr.8.3.186","article-title":"Base-calling of automated sequencer traces using phred. II. Error probabilities","volume":"8","author":"Ewing","year":"1998","journal-title":"Genome Res."},{"key":"2023012512434049000_B5","doi-asserted-by":"crossref","first-page":"390","DOI":"10.1109\/SFCS.2000.892127","article-title":"Opportunistic data structures with applications","volume-title":"Proceedings of the 41st Annual Symposium on Foundations of Computer Science","author":"Ferragina","year":"2000"},{"key":"2023012512434049000_B6","doi-asserted-by":"crossref","first-page":"4","DOI":"10.1145\/1082036.1082039","article-title":"Indexing compressed text","volume":"52","author":"Ferragina","year":"2005","journal-title":"J. ACM"},{"key":"2023012512434049000_B7","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1137\/S0097539702402354","article-title":"Compressed suffix arrays and suffix trees with applications to text indexing and string matching","volume":"35","author":"Grossi","year":"2005","journal-title":"SIAM J. Comput."},{"key":"2023012512434049000_B8","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":"2023012512434049000_B9","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1007\/s00453-006-1228-8","article-title":"A space and time efficient algorithm for constructing compressed suffix arrays","volume":"48","author":"Hon","year":"2007","journal-title":"Algorithmica"},{"key":"2023012512434049000_B10","doi-asserted-by":"crossref","first-page":"R12","DOI":"10.1186\/gb-2004-5-2-r12","article-title":"Versatile and open software for comparing large genomes","volume":"5","author":"Kurtz","year":"2004","journal-title":"Genome Biol."},{"key":"2023012512434049000_B11","doi-asserted-by":"crossref","first-page":"715","DOI":"10.1093\/bioinformatics\/btq707","article-title":"CompleteMOTIFs: DNA motif discovery platform for transcription factor binding experiments","volume":"27","author":"Kuttippurathu","year":"2011","journal-title":"Bioinformatics"},{"key":"2023012512434049000_B12","doi-asserted-by":"crossref","first-page":"791","DOI":"10.1093\/bioinformatics\/btn032","article-title":"Compressed indexing and local alignment of DNA","volume":"24","author":"Lam","year":"2008","journal-title":"Bioinformatics"},{"key":"2023012512434049000_B13","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":"2023012512434049000_B14","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":"2023012512434049000_B15","doi-asserted-by":"crossref","first-page":"2078","DOI":"10.1093\/bioinformatics\/btp352","article-title":"The sequence alignment\/map format and SAMtools","volume":"25","author":"Li","year":"2009","journal-title":"Bioinformatics"},{"key":"2023012512434049000_B16","doi-asserted-by":"crossref","first-page":"1755","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":"2023012512434049000_B17","doi-asserted-by":"crossref","first-page":"589","DOI":"10.1093\/bioinformatics\/btp698","article-title":"Fast and accurate long-read alignment with Burrows\u2013Wheeler transform","volume":"26","author":"Li","year":"2010","journal-title":"Bioinformatics"},{"key":"2023012512434049000_B18","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":"2023012512434049000_B19","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":"2023012512434049000_B20","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1109\/MM.2008.31","article-title":"NVIDIA Tesla: a unified graphics and computing architecture","volume":"28","author":"Lindholm","year":"2008","journal-title":"IEEE Micro"},{"key":"2023012512434049000_B21","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1186\/1756-0500-2-73","article-title":"CUDASW++: optimizing Smith\u2013Waterman sequence database searches for CUDA-enabled graphics processing units","volume":"2","author":"Liu","year":"2009","journal-title":"BMC Res. Notes"},{"key":"2023012512434049000_B22","doi-asserted-by":"crossref","first-page":"2170","DOI":"10.1016\/j.patrec.2009.10.009","article-title":"CUDA\u2013MEME: accelerating motif discovery in biological sequences using CUDA-enabled graphics processing units","volume":"31","author":"Liu","year":"2010","journal-title":"Pattern Recognit. Lett."},{"key":"2023012512434049000_B23","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1186\/1471-2105-12-85","article-title":"DecGPU: distributed error correction on massively parallel graphics processing units using CUDA and MPI","volume":"12","author":"Liu","year":"2011","journal-title":"BMC Bioinformatics"},{"key":"2023012512434049000_B24","author":"NVIDIA","year":"2009","journal-title":"NVIDIA's next generation CUDA compute architecture: Fermi. NVIDIA Corporation Whitepaper."},{"key":"2023012512434049000_B25","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":"2023012512434049000_B26","doi-asserted-by":"crossref","first-page":"128","DOI":"10.1186\/1471-2105-9-128","article-title":"Using quality scores and longer reads improves accuracy of Solexa read mapping","volume":"9","author":"Smith","year":"2008","journal-title":"BMC Bioinformatics"},{"key":"2023012512434049000_B27","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":"1998","journal-title":"J. Mol. Biol."},{"key":"2023012512434049000_B28","doi-asserted-by":"crossref","first-page":"182","DOI":"10.1093\/bioinformatics\/btq644","article-title":"GPU-BLAST: using graphics processors to accelerate protein sequence alignment","volume":"27","author":"Vouzis","year":"2010","journal-title":"Bioinformatics"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/28\/14\/1830\/48872705\/bioinformatics_28_14_1830.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/28\/14\/1830\/48872705\/bioinformatics_28_14_1830.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,25]],"date-time":"2023-01-25T16:50:59Z","timestamp":1674665459000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/28\/14\/1830\/218764"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,5,9]]},"references-count":28,"journal-issue":{"issue":"14","published-print":{"date-parts":[[2012,7,15]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/bts276","relation":{},"ISSN":["1367-4811","1367-4803"],"issn-type":[{"value":"1367-4811","type":"electronic"},{"value":"1367-4803","type":"print"}],"subject":[],"published-other":{"date-parts":[[2012,7,15]]},"published":{"date-parts":[[2012,5,9]]}}}