{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,1]],"date-time":"2026-05-01T06:02:01Z","timestamp":1777615321620,"version":"3.51.4"},"reference-count":24,"publisher":"Oxford University Press (OUP)","issue":"22","funder":[{"DOI":"10.13039\/501100001868","name":"National Science Council","doi-asserted-by":"crossref","award":["103-2221-E-009-128-MY2"],"award-info":[{"award-number":["103-2221-E-009-128-MY2"]}],"id":[{"id":"10.13039\/501100001868","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100001868","name":"National Science Council","doi-asserted-by":"crossref","award":["104-2311-B-009 -002 -MY3"],"award-info":[{"award-number":["104-2311-B-009 -002 -MY3"]}],"id":[{"id":"10.13039\/501100001868","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016,11,15]]},"abstract":"<jats:p>Motivation: The Full-text index in Minute space (FM-index) derived from the Burrows\u2013Wheeler transform (BWT) is broadly used for fast string matching in large genomes or a huge set of sequencing reads. Several graphic processing unit (GPU) accelerated aligners based on the FM-index have been proposed recently; however, the construction of the index is still handled by central processing unit (CPU), only parallelized in data level (e.g. by performing blockwise suffix sorting in GPU), or not scalable for large genomes.<\/jats:p>\n               <jats:p>Results: To fulfill the need for a more practical, hardware-parallelizable indexing and matching approach, we herein propose sBWT based on a BWT variant (i.e. Schindler transform) that can be built with highly simplified hardware-acceleration-friendly algorithms and still suffices accurate and fast string matching in repetitive references. In our tests, the implementation achieves significant speedups in indexing and searching compared with other BWT-based tools and can be applied to a variety of domains.<\/jats:p>\n               <jats:p>Availability and implementation: sBWT is implemented in C\u2009++\u2009with CPU-only and GPU-accelerated versions. sBWT is open-source software and is available at http:\/\/jhhung.github.io\/sBWT\/<\/jats:p>\n               <jats:p>Supplementary information: \u00a0Supplementary data are available at Bioinformatics online.<\/jats:p>\n               <jats:p>Contact: \u00a0chyee@ntu.edu.tw or jhhung@nctu.edu.tw (also juihunghung@gmail.com)<\/jats:p>","DOI":"10.1093\/bioinformatics\/btw419","type":"journal-article","created":{"date-parts":[[2016,7,14]],"date-time":"2016-07-14T06:18:47Z","timestamp":1468477127000},"page":"3498-3500","source":"Crossref","is-referenced-by-count":11,"title":["sBWT: memory efficient implementation of the hardware-acceleration-friendly Schindler transform for the fast biological sequence mapping"],"prefix":"10.1093","volume":"32","author":[{"given":"Chia-Hua","family":"Chang","sequence":"first","affiliation":[{"name":"1Institute of Bioinformatics and Systems Biology"},{"name":"2Institute of Biomedical Engineering"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Min-Te","family":"Chou","sequence":"additional","affiliation":[{"name":"1Institute of Bioinformatics and Systems Biology"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yi-Chung","family":"Wu","sequence":"additional","affiliation":[{"name":"4Department of Electrical Engineering, National Taiwan University, Taipei, Taiwan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ting-Wei","family":"Hong","sequence":"additional","affiliation":[{"name":"1Institute of Bioinformatics and Systems Biology"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yun-Lung","family":"Li","sequence":"additional","affiliation":[{"name":"1Institute of Bioinformatics and Systems Biology"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Chia-Hsiang","family":"Yang","sequence":"additional","affiliation":[{"name":"4Department of Electrical Engineering, National Taiwan University, Taipei, Taiwan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jui-Hung","family":"Hung","sequence":"additional","affiliation":[{"name":"1Institute of Bioinformatics and Systems Biology"},{"name":"2Institute of Biomedical Engineering"},{"name":"3Department of Biological Science and Technology, National Chiao Tung University, Hsin-Chu, Taiwan"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2016,7,13]]},"reference":[{"key":"2023020113530403200_btw419-B1","doi-asserted-by":"crossref","first-page":"449","DOI":"10.1007\/3-540-45784-4_35","article-title":"The enhanced suffix array and its applications to genome analysis","volume":"2452","author":"Abouelhoda","year":"2002","journal-title":"Lect. Notes Comput. Sci"},{"key":"2023020113530403200_btw419-B2","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1007\/978-0-387-78909-5_6","volume-title":"The Burrows-Wheeler Transform: Data Compression, Suffix Arrays, and Pattern Matching","author":"Adjeroh","year":"2008"},{"key":"2023020113530403200_btw419-B3","doi-asserted-by":"crossref","first-page":"134","DOI":"10.1016\/j.tcs.2012.02.002","article-title":"Lightweight algorithms for constructing and inverting the BWT of string collections","volume":"483","author":"Bauer","year":"2013","journal-title":"Theor. Comput. Sci"},{"key":"2023020113530403200_btw419-B4","first-page":"55","article-title":"Fast lightweight suffix array construction and checking","volume":"2676","author":"Burkhardt","year":"2003","journal-title":"Comb. Pattern Match. Proc"},{"key":"2023020113530403200_btw419-B25","doi-asserted-by":"crossref","first-page":"1415","DOI":"10.1093\/bioinformatics\/bts173","article-title":"Large-scale compression of genomic sequence databases with the Burrows\u2013Wheeler transform","volume":"28","author":"Cox","year":"2012","journal-title":"Bioinformatics"},{"key":"2023020113530403200_btw419-B5","doi-asserted-by":"crossref","first-page":"1037","DOI":"10.1002\/spe.1112","article-title":"Revisiting bounded context block-sorting transformations","volume":"42","author":"Culpepper","year":"2012","journal-title":"Softw. Pract. Exp."},{"key":"2023020113530403200_btw419-B6","first-page":"390","article-title":"Opportunistic data structures with applications","author":"Ferragina","year":"2000","journal-title":"Ann. Ieee Symp. Found"},{"key":"2023020113530403200_btw419-B7","doi-asserted-by":"crossref","first-page":"688","DOI":"10.1101\/gr.168450.113","article-title":"Reconstructing complex regions of genomes using long-read sequencing technology","volume":"24","author":"Huddleston","year":"2014","journal-title":"Genome Res"},{"key":"2023020113530403200_btw419-B8","doi-asserted-by":"crossref","first-page":"249","DOI":"10.1016\/j.tcs.2007.07.018","article-title":"Fast BWT in small space by blockwise suffix sorting","volume":"387","author":"Karkkainen","year":"2007","journal-title":"Theor. Comput. Sci"},{"key":"2023020113530403200_btw419-B9","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1186\/1756-0500-5-27","article-title":"BarraCUDA - a fast short read sequence aligner using graphics processing units","volume":"5","author":"Klus","year":"2012","journal-title":"BMC Res. Notes"},{"key":"2023020113530403200_btw419-B10","doi-asserted-by":"crossref","first-page":"357","DOI":"10.1038\/nmeth.1923","article-title":"Fast gapped-read alignment with Bowtie 2","volume":"9","author":"Langmead","year":"2012","journal-title":"Nat. Methods"},{"key":"2023020113530403200_btw419-B11","doi-asserted-by":"crossref","first-page":"3274","DOI":"10.1093\/bioinformatics\/btu541","article-title":"Fast construction of FM-index for long sequence reads","volume":"30","author":"Li","year":"2014","journal-title":"Bioinformatics"},{"key":"2023020113530403200_btw419-B12","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":"2023020113530403200_btw419-B13","doi-asserted-by":"crossref","first-page":"473","DOI":"10.1093\/bib\/bbq015","article-title":"A survey of sequence alignment algorithms for next-generation sequencing","volume":"11","author":"Li","year":"2010","journal-title":"Brief. Bioinformatics"},{"key":"2023020113530403200_btw419-B14","article-title":"GPU-Accelerated BWT construction for large collection of short reads","author":"Liu","year":"2014","journal-title":"arXiv"},{"key":"2023020113530403200_btw419-B15","doi-asserted-by":"crossref","first-page":"1830","DOI":"10.1093\/bioinformatics\/bts276","article-title":"CUSHAW: a CUDA compatible short read aligner to large genomes based on the Burrows-Wheeler transform","volume":"28","author":"Liu","year":"2012","journal-title":"Bioinformatics"},{"key":"2023020113530403200_btw419-B16","doi-asserted-by":"crossref","first-page":"e65632","DOI":"10.1371\/journal.pone.0065632","article-title":"SOAP3-dp: fast, accurate and sensitive GPU-based short read aligner","volume":"8","author":"Luo","year":"2013","journal-title":"PloS One"},{"key":"2023020113530403200_btw419-B17","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/1367064.1367072","article-title":"Dynamic entropy-compressed sequences and full-text indexes","volume":"4","author":"Makinen","year":"2008","journal-title":"Acm T Algorithms"},{"key":"2023020113530403200_btw419-B18","doi-asserted-by":"crossref","first-page":"464","DOI":"10.1109\/DCC.2006.81","article-title":"Unifying the burrows-wheeler and the Schindler transforms","author":"Nong","year":"2006","journal-title":"Ieee Data Compression Conference"},{"key":"2023020113530403200_btw419-B19","doi-asserted-by":"crossref","first-page":"1564","DOI":"10.1109\/TC.2007.70762","article-title":"Efficient algorithms for the inverse sort transform","volume":"56","author":"Nong","year":"2007","journal-title":"Ieee. Trans. Comput"},{"key":"2023020113530403200_btw419-B26","doi-asserted-by":"crossref","first-page":"549","DOI":"10.1101\/gr.126953.111","article-title":"Efficient de novo assembly of large genomes using compressed data structures","volume":"22","author":"Simpson","year":"2012","journal-title":"Genome Res"},{"key":"2023020113530403200_btw419-B20","volume-title":"Method and apparatus for sorting data blocks","author":"Schindler","year":"2001"},{"key":"2023020113530403200_btw419-B21","doi-asserted-by":"crossref","first-page":"1245","DOI":"10.1109\/TCBB.2012.49","article-title":"Using GPUs for the Exact Alignment of Short-Read Genetic Sequences by Means of the Burrows-Wheeler Transform","volume":"9","author":"Torres","year":"2012","journal-title":"Ieee Acm Trans. Comput. Biol"},{"key":"2023020113530403200_btw419-B22","doi-asserted-by":"crossref","first-page":"6993","DOI":"10.1093\/nar\/gks408","article-title":"Prospects and limitations of full-text index structures in genome analysis","volume":"40","author":"Vyverman","year":"2012","journal-title":"Nucleic Acids Res"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/32\/22\/3498\/49027222\/bioinformatics_32_22_3498.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/32\/22\/3498\/49027222\/bioinformatics_32_22_3498.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,1]],"date-time":"2023-02-01T23:56:32Z","timestamp":1675295792000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/32\/22\/3498\/2525596"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,7,13]]},"references-count":24,"journal-issue":{"issue":"22","published-print":{"date-parts":[[2016,11,15]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btw419","relation":{},"ISSN":["1367-4803","1367-4811"],"issn-type":[{"value":"1367-4803","type":"print"},{"value":"1367-4811","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2016,11,15]]},"published":{"date-parts":[[2016,7,13]]}}}