{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,8,3]],"date-time":"2024-08-03T18:51:46Z","timestamp":1722711106276},"reference-count":18,"publisher":"World Scientific Pub Co Pte Lt","issue":"04","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. Bioinform. Comput. Biol."],"published-print":{"date-parts":[[2012,8]]},"abstract":"<jats:p> Myers' elegant and powerful bit-parallel dynamic programming algorithm for approximate string matching has a restriction that the query length should be within the word size of the computer, typically 64. We propose a modification of Myers' algorithm, in which the modification has a restriction not on the query length but on the maximum number of mismatches (substitutions, insertions, or deletions), which should be less than half of the word size. The time complexity is O(m log |\u03a3|), where m is the query length and |\u03a3| is the size of the alphabet \u03a3. Thus, it is particularly suited for sequences on a small alphabet such as DNA sequences. In particular, it is useful in quickly extending a large number of seed alignments against a reference genome for high-throughput short-read data produced by next-generation DNA sequencers. <\/jats:p>","DOI":"10.1142\/s0219720012500023","type":"journal-article","created":{"date-parts":[[2011,12,29]],"date-time":"2011-12-29T02:31:16Z","timestamp":1325125876000},"page":"1250002","source":"Crossref","is-referenced-by-count":4,"title":["A BIT-PARALLEL DYNAMIC PROGRAMMING ALGORITHM SUITABLE FOR DNA SEQUENCE ALIGNMENT"],"prefix":"10.1142","volume":"10","author":[{"given":"KOUICHI","family":"KIMURA","sequence":"first","affiliation":[{"name":"Central Research Laboratory, Hitachi Ltd., 1-280 Higashi-Koigakubo, Kokubunji Tokyo, 185-8601, Japan"}]},{"given":"ASAKO","family":"KOIKE","sequence":"additional","affiliation":[{"name":"Central Research Laboratory, Hitachi Ltd., 1-280 Higashi-Koigakubo, Kokubunji Tokyo, 185-8601, Japan"}]},{"given":"KENTA","family":"NAKAI","sequence":"additional","affiliation":[{"name":"The Institute of Medical Science, The University of Tokyo, 4-6-1 Shirokane-dai, Minato-ku, Tokyo, 108-8639, Japan"}]}],"member":"219","published-online":{"date-parts":[[2012,7,23]]},"reference":[{"key":"rf1","doi-asserted-by":"publisher","DOI":"10.1038\/nmeth1156"},{"key":"rf2","doi-asserted-by":"publisher","DOI":"10.1101\/gr.073262.107"},{"key":"rf3","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btp324"},{"key":"rf4","doi-asserted-by":"publisher","DOI":"10.1186\/gb-2009-10-3-r25"},{"key":"rf5","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btp336"},{"key":"rf6","doi-asserted-by":"publisher","DOI":"10.1089\/cmb.2008.0146"},{"key":"rf7","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btn032"},{"key":"rf8","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btp698"},{"key":"rf9","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-23038-7_14"},{"key":"rf10","doi-asserted-by":"publisher","DOI":"10.1145\/316542.316550"},{"key":"rf11","volume-title":"The Art of Computer Programming, Volume 4, Fascicle 0: Introduction to Combinatorial Algorithms and Boolean Functions (Art of Computer Programming)","author":"Knuth D. E.","year":"2008"},{"key":"rf12","doi-asserted-by":"publisher","DOI":"10.1186\/1471-2105-8-185"},{"key":"rf13","doi-asserted-by":"publisher","DOI":"10.1186\/1471-2105-9-S2-S10"},{"key":"rf14","doi-asserted-by":"publisher","DOI":"10.1186\/1756-0500-3-93"},{"key":"rf15","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/16.8.699"},{"key":"rf16","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btl582"},{"key":"rf17","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054106004443"},{"key":"rf18","doi-asserted-by":"publisher","DOI":"10.1007\/978-0-387-78909-5"}],"container-title":["Journal of Bioinformatics and Computational Biology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0219720012500023","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,6]],"date-time":"2019-08-06T18:34:18Z","timestamp":1565116458000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0219720012500023"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,7,23]]},"references-count":18,"journal-issue":{"issue":"04","published-online":{"date-parts":[[2012,7,23]]},"published-print":{"date-parts":[[2012,8]]}},"alternative-id":["10.1142\/S0219720012500023"],"URL":"https:\/\/doi.org\/10.1142\/s0219720012500023","relation":{},"ISSN":["0219-7200","1757-6334"],"issn-type":[{"value":"0219-7200","type":"print"},{"value":"1757-6334","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,7,23]]}}}