{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,6]],"date-time":"2025-11-06T19:54:47Z","timestamp":1762458887573},"reference-count":17,"publisher":"Oxford University Press (OUP)","issue":"10","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2011,5,15]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>Motivation: The introduction of next-generation sequencing techniques and especially the high-throughput systems Solexa (Illumina Inc.) and SOLiD (ABI) made the mapping of short reads to reference sequences a standard application in modern bioinformatics. Short-read alignment is needed for reference based re-sequencing of complete genomes as well as for gene expression analysis based on transcriptome sequencing. Several approaches were developed during the last years allowing for a fast alignment of short sequences to a given template. Methods available to date use heuristic techniques to gain a speedup of the alignments, thereby missing possible alignment positions. Furthermore, most approaches return only one best hit for every query sequence, thus losing the potentially valuable information of alternative alignment positions with identical scores.<\/jats:p>\n               <jats:p>Results: We developed SARUMAN (Semiglobal Alignment of short Reads Using CUDA and NeedleMAN-Wunsch), a mapping approach that returns all possible alignment positions of a read in a reference sequence under a given error threshold, together with one optimal alignment for each of these positions. Alignments are computed in parallel on graphics hardware, facilitating an considerable speedup of this normally time-consuming step. Combining our filter algorithm with CUDA-accelerated alignments, we were able to align reads to microbial genomes in time comparable or even faster than all published approaches, while still providing an exact, complete and optimal result. At the same time, SARUMAN runs on every standard Linux PC with a CUDA-compatible graphics accelerator.<\/jats:p>\n               <jats:p>Availability: \u00a0http:\/\/www.cebitec.uni-bielefeld.de\/brf\/saruman\/saruman.html.<\/jats:p>\n               <jats:p>Contact: \u00a0jblom@cebitec.uni-bielefeld.de<\/jats:p>\n               <jats:p>Supplementary information: \u00a0Supplementary data are available at Bioinformatics online.<\/jats:p>","DOI":"10.1093\/bioinformatics\/btr151","type":"journal-article","created":{"date-parts":[[2011,3,31]],"date-time":"2011-03-31T00:31:59Z","timestamp":1301531519000},"page":"1351-1358","source":"Crossref","is-referenced-by-count":74,"title":["Exact and complete short-read alignment to microbial genomes using Graphics Processing Unit programming"],"prefix":"10.1093","volume":"27","author":[{"given":"Jochen","family":"Blom","sequence":"first","affiliation":[{"name":"1 Computational Genomics, 2Institute for Genome Research and Systems Biology, CeBiTec, 3Genome Informatics, Faculty of Technology, 4Institute for Bioinformatics and 5Bioinformatics Resource Facility, CeBiTec, Bielefeld University, Bielefeld, Germany"}]},{"given":"Tobias","family":"Jakobi","sequence":"additional","affiliation":[{"name":"1 Computational Genomics, 2Institute for Genome Research and Systems Biology, CeBiTec, 3Genome Informatics, Faculty of Technology, 4Institute for Bioinformatics and 5Bioinformatics Resource Facility, CeBiTec, Bielefeld University, Bielefeld, Germany"}]},{"given":"Daniel","family":"Doppmeier","sequence":"additional","affiliation":[{"name":"1 Computational Genomics, 2Institute for Genome Research and Systems Biology, CeBiTec, 3Genome Informatics, Faculty of Technology, 4Institute for Bioinformatics and 5Bioinformatics Resource Facility, CeBiTec, Bielefeld University, Bielefeld, Germany"}]},{"given":"Sebastian","family":"Jaenicke","sequence":"additional","affiliation":[{"name":"1 Computational Genomics, 2Institute for Genome Research and Systems Biology, CeBiTec, 3Genome Informatics, Faculty of Technology, 4Institute for Bioinformatics and 5Bioinformatics Resource Facility, CeBiTec, Bielefeld University, Bielefeld, Germany"}]},{"given":"J\u00f6rn","family":"Kalinowski","sequence":"additional","affiliation":[{"name":"1 Computational Genomics, 2Institute for Genome Research and Systems Biology, CeBiTec, 3Genome Informatics, Faculty of Technology, 4Institute for Bioinformatics and 5Bioinformatics Resource Facility, CeBiTec, Bielefeld University, Bielefeld, Germany"}]},{"given":"Jens","family":"Stoye","sequence":"additional","affiliation":[{"name":"1 Computational Genomics, 2Institute for Genome Research and Systems Biology, CeBiTec, 3Genome Informatics, Faculty of Technology, 4Institute for Bioinformatics and 5Bioinformatics Resource Facility, CeBiTec, Bielefeld University, Bielefeld, Germany"},{"name":"1 Computational Genomics, 2Institute for Genome Research and Systems Biology, CeBiTec, 3Genome Informatics, Faculty of Technology, 4Institute for Bioinformatics and 5Bioinformatics Resource Facility, CeBiTec, Bielefeld University, Bielefeld, Germany"}]},{"given":"Alexander","family":"Goesmann","sequence":"additional","affiliation":[{"name":"1 Computational Genomics, 2Institute for Genome Research and Systems Biology, CeBiTec, 3Genome Informatics, Faculty of Technology, 4Institute for Bioinformatics and 5Bioinformatics Resource Facility, CeBiTec, Bielefeld University, Bielefeld, Germany"},{"name":"1 Computational Genomics, 2Institute for Genome Research and Systems Biology, CeBiTec, 3Genome Informatics, Faculty of Technology, 4Institute for Bioinformatics and 5Bioinformatics Resource Facility, CeBiTec, Bielefeld University, Bielefeld, Germany"},{"name":"1 Computational Genomics, 2Institute for Genome Research and Systems Biology, CeBiTec, 3Genome Informatics, Faculty of Technology, 4Institute for Bioinformatics and 5Bioinformatics Resource Facility, CeBiTec, Bielefeld University, Bielefeld, Germany"}]}],"member":"286","published-online":{"date-parts":[[2011,3,30]]},"reference":[{"key":"2023012511035142500_B1","article-title":"A block-sorting lossless data compression algorithm","volume-title":"Technical Report 124","author":"Burrows","year":"1994"},{"key":"2023012511035142500_B2","first-page":"353","article-title":"FLASH: A fast look-up algorithm for string homology","volume-title":"Computer Vision and Pattern Recognition, 1993. Proceedings CVPR'93., 1993 IEEE Computer Society Conference on.","author":"Califano","year":"2002"},{"key":"2023012511035142500_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":"2023012511035142500_B4","doi-asserted-by":"crossref","first-page":"156","DOI":"10.1093\/bioinformatics\/btl582","article-title":"Striped Smith-Waterman speeds database searches six times over other SIMD implementations","volume":"23","author":"Farrar","year":"2007","journal-title":"Bioinformatics"},{"key":"2023012511035142500_B5","doi-asserted-by":"crossref","first-page":"240","DOI":"10.1007\/3-540-54345-7_67","article-title":"Two algorithms for approximate string matching in static texts","volume":"520\/1991","author":"Jokinen","year":"1991","journal-title":"Lecture Notes in Computer Science"},{"key":"2023012511035142500_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":"2023012511035142500_B7","first-page":"8","article-title":"Bio-sequence database scanning on a GPU","volume-title":"Parallel and Distributed Processing Symposium, 2006. IPDPS 2006. 20th International","author":"Liu","year":"2006"},{"key":"2023012511035142500_B8","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1186\/1756-0500-2-73","article-title":"CUDASW++: optimizing Smith-Waterman sequence database searches for CUDA-enabled graphics processing units","volume":"2","author":"Liu","year":"2009","journal-title":"BMC Res. Notes"},{"key":"2023012511035142500_B9","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":"2023012511035142500_B10","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":"2023012511035142500_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"},{"issue":"Suppl. 2","key":"2023012511035142500_B12","doi-asserted-by":"crossref","first-page":"S10","DOI":"10.1186\/1471-2105-9-S2-S10","article-title":"CUDA compatible GPU cards as efficient hardware accelerators for Smith-Waterman sequence alignment","volume":"9","author":"Manavski","year":"2008","journal-title":"BMC Bioinformatics"},{"key":"2023012511035142500_B13","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":"2023012511035142500_B14","doi-asserted-by":"crossref","first-page":"699","DOI":"10.1093\/bioinformatics\/16.8.699","article-title":"Six-fold speed-up of Smith-Waterman sequence database searches using parallel processing on common microprocessors","volume":"16","author":"Rognes","year":"2000","journal-title":"Bioinformatics"},{"key":"2023012511035142500_B15","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":"2023012511035142500_B16","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":"2023012511035142500_B17","doi-asserted-by":"crossref","first-page":"107","DOI":"10.1186\/1756-0500-1-107","article-title":"SWPS3 - fast multi-threaded vectorized Smith-Waterman for IBM Cell\/B.E. and x86\/SSE2","volume":"1","author":"Szalkowski","year":"2008","journal-title":"BMC Res. Notes"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/27\/10\/1351\/48861634\/bioinformatics_27_10_1351.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/27\/10\/1351\/48861634\/bioinformatics_27_10_1351.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,25]],"date-time":"2023-01-25T11:09:15Z","timestamp":1674644955000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/27\/10\/1351\/260144"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,3,30]]},"references-count":17,"journal-issue":{"issue":"10","published-print":{"date-parts":[[2011,5,15]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btr151","relation":{},"ISSN":["1367-4811","1367-4803"],"issn-type":[{"value":"1367-4811","type":"electronic"},{"value":"1367-4803","type":"print"}],"subject":[],"published-other":{"date-parts":[[2011,5,15]]},"published":{"date-parts":[[2011,3,30]]}}}