{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,2]],"date-time":"2026-07-02T23:40:22Z","timestamp":1783035622648,"version":"3.54.6"},"reference-count":17,"publisher":"Oxford University Press (OUP)","issue":"22","license":[{"start":{"date-parts":[[2016,11,7]],"date-time":"2016-11-07T00:00:00Z","timestamp":1478476800000},"content-version":"vor","delay-in-days":832,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014,11,15]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>Motivation: Mapping of high-throughput sequencing data and other bulk sequence comparison applications have motivated a search for high-efficiency sequence alignment algorithms. The bit-parallel approach represents individual cells in an alignment scoring matrix as bits in computer words and emulates the calculation of scores by a series of logic operations composed of AND, OR, XOR, complement, shift and addition. Bit-parallelism has been successfully applied to the longest common subsequence (LCS) and edit-distance problems, producing fast algorithms in practice.<\/jats:p>\n               <jats:p>Results: We have developed BitPAl, a bit-parallel algorithm for general, integer-scoring global alignment. Integer-scoring schemes assign integer weights for match, mismatch and insertion\/deletion. The BitPAl method uses structural properties in the relationship between adjacent scores in the scoring matrix to construct classes of efficient algorithms, each designed for a particular set of weights. In timed tests, we show that BitPAl runs 7\u201325 times faster than a standard iterative algorithm.<\/jats:p>\n               <jats:p>Availability and implementation: Source code is freely available for download at http:\/\/lobstah.bu.edu\/BitPAl\/BitPAl.html . BitPAl is implemented in C and runs on all major operating systems.<\/jats:p>\n               <jats:p>Contact : jloving@bu.edu or yhernand@bu.edu or gbenson@bu.edu<\/jats:p>\n               <jats:p>Supplementary information : Supplementary data are available at Bioinformatics online.<\/jats:p>","DOI":"10.1093\/bioinformatics\/btu507","type":"journal-article","created":{"date-parts":[[2014,7,30]],"date-time":"2014-07-30T00:14:11Z","timestamp":1406679251000},"page":"3166-3173","source":"Crossref","is-referenced-by-count":32,"title":["BitPAl: a bit-parallel, general integer-scoring sequence alignment algorithm"],"prefix":"10.1093","volume":"30","author":[{"given":"Joshua","family":"Loving","sequence":"first","affiliation":[{"name":"1 Laboratory for Biocomputing and Informatics, 2 Graduate Program in Bioinformatics, and 3 Department of Computer Science, Boston University, Boston, MA 02215, USA"},{"name":"1 Laboratory for Biocomputing and Informatics, 2 Graduate Program in Bioinformatics, and 3 Department of Computer Science, Boston University, Boston, MA 02215, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yozen","family":"Hernandez","sequence":"additional","affiliation":[{"name":"1 Laboratory for Biocomputing and Informatics, 2 Graduate Program in Bioinformatics, and 3 Department of Computer Science, Boston University, Boston, MA 02215, USA"},{"name":"1 Laboratory for Biocomputing and Informatics, 2 Graduate Program in Bioinformatics, and 3 Department of Computer Science, Boston University, Boston, MA 02215, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Gary","family":"Benson","sequence":"additional","affiliation":[{"name":"1 Laboratory for Biocomputing and Informatics, 2 Graduate Program in Bioinformatics, and 3 Department of Computer Science, Boston University, Boston, MA 02215, USA"},{"name":"1 Laboratory for Biocomputing and Informatics, 2 Graduate Program in Bioinformatics, and 3 Department of Computer Science, Boston University, Boston, MA 02215, USA"},{"name":"1 Laboratory for Biocomputing and Informatics, 2 Graduate Program in Bioinformatics, and 3 Department of Computer Science, Boston University, Boston, MA 02215, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"286","published-online":{"date-parts":[[2014,7,29]]},"reference":[{"key":"2023012712005671800_btu507-B1","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1016\/0020-0190(86)90091-8","article-title":"A bit-string longest-common-subsequence algorithm","volume":"23","author":"Allison","year":"1986","journal-title":"Inf. Process. Lett."},{"key":"2023012712005671800_btu507-B2","doi-asserted-by":"crossref","first-page":"74","DOI":"10.1145\/135239.135243","article-title":"A new approach to text searching","volume":"35","author":"Baeza-Yates","year":"1992","journal-title":"Commun. ACM"},{"key":"2023012712005671800_btu507-B3","first-page":"50","article-title":"A bit-parallel, general integer-scoring sequence alignment algorithm","volume-title":"Combinatorial Pattern Matching, Vol. 7922 of Lecture Notes in Computer Science","author":"Benson","year":"2013"},{"key":"2023012712005671800_btu507-B4","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1142\/S0129054102000947","article-title":"Vector algorithms for approximate string matching","volume":"13","author":"Bergeron","year":"2002","journal-title":"Int. J. Found. Comput. Sci."},{"key":"2023012712005671800_btu507-B5","doi-asserted-by":"crossref","first-page":"279","DOI":"10.1016\/S0020-0190(01)00182-X","article-title":"A fast and practical bit-vector algorithm for the longest common subsequence problem","volume":"80","author":"Crochemore","year":"2001","journal-title":"Inform. Process. Lett."},{"key":"2023012712005671800_btu507-B6","doi-asserted-by":"crossref","DOI":"10.1093\/nar\/gku642","article-title":"VNTRseek-a computational tool to detect tandem repeat variants in high-throughput sequencing data","author":"Gelfand","year":"2014","journal-title":"Nucleic Acids Res"},{"key":"2023012712005671800_btu507-B7","article-title":"Bit-parallel LCS-length computation revisited","volume-title":"Proceedings of the 15th Australasian Workshop on Combinatorial Algorithms (AWOCA 2004)","author":"Hyyr\u00f6","year":"2004"},{"key":"2023012712005671800_btu507-B8","doi-asserted-by":"crossref","first-page":"203","DOI":"10.1007\/s00453-004-1108-z","article-title":"Bit-parallel witnesses and their applications to approximate string matching","volume":"41","author":"Hyyr\u00f6","year":"2005","journal-title":"Algorithmica"},{"key":"2023012712005671800_btu507-B9","doi-asserted-by":"crossref","first-page":"1325","DOI":"10.1142\/S0129054106004443","article-title":"Bit-parallel computation of local similarity score matrices with unitary weights","volume":"17","author":"Hyyr\u00f6","year":"2006","journal-title":"Int. J. Found. Comput. Sci."},{"key":"2023012712005671800_btu507-B10","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1145\/1064546.1180617","article-title":"Increased bit-parallelism for approximate and multiple string matching","volume":"10","author":"Hyyr\u00f6","year":"2005","journal-title":"J. Exp. Algorithmics"},{"key":"2023012712005671800_btu507-B11","volume-title":"The C Programming Language","author":"Kernighan","year":"1988","edition":"2nd edn"},{"key":"2023012712005671800_btu507-B12","doi-asserted-by":"crossref","first-page":"395","DOI":"10.1145\/316542.316550","article-title":"A fast bit-vector algorithm for approximate string matching based on dynamic programming","volume":"46","author":"Myers","year":"1999","journal-title":"J. ACM"},{"key":"2023012712005671800_btu507-B13","first-page":"356","article-title":"Approximate regular expression searching with arbitrary integer weights","volume":"11","author":"Navarro","year":"2004","journal-title":"Nordic J. Comput."},{"key":"2023012712005671800_btu507-B14","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":"2023012712005671800_btu507-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."},{"key":"2023012712005671800_btu507-B16","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1145\/135239.135244","article-title":"Fast text searching: allowing errors","volume":"35","author":"Wu","year":"1992","journal-title":"Commun. ACM"},{"key":"2023012712005671800_btu507-B17","doi-asserted-by":"crossref","first-page":"50","DOI":"10.1007\/BF01942606","article-title":"A subquadratic algorithm for approximate limited expression matching","volume":"15","author":"Wu","year":"1996","journal-title":"Algorithmica"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/30\/22\/3166\/48931281\/bioinformatics_30_22_3166.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/30\/22\/3166\/48931281\/bioinformatics_30_22_3166.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,27]],"date-time":"2023-01-27T12:57:42Z","timestamp":1674824262000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/30\/22\/3166\/2390221"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,7,29]]},"references-count":17,"journal-issue":{"issue":"22","published-print":{"date-parts":[[2014,11,15]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btu507","relation":{},"ISSN":["1367-4811","1367-4803"],"issn-type":[{"value":"1367-4811","type":"electronic"},{"value":"1367-4803","type":"print"}],"subject":[],"published-other":{"date-parts":[[2014,11,15]]},"published":{"date-parts":[[2014,7,29]]}}}