{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T13:00:04Z","timestamp":1740142804622,"version":"3.37.3"},"reference-count":23,"publisher":"Oxford University Press (OUP)","issue":"5","license":[{"start":{"date-parts":[[2017,10,13]],"date-time":"2017-10-13T00:00:00Z","timestamp":1507852800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/academic.oup.com\/journals\/pages\/about_us\/legal\/notices"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2018,5,1]]},"DOI":"10.1093\/comjnl\/bxx090","type":"journal-article","created":{"date-parts":[[2017,9,13]],"date-time":"2017-09-13T15:11:30Z","timestamp":1505315490000},"page":"687-713","source":"Crossref","is-referenced-by-count":5,"title":["Formalization of Block Pruning: Reducing the Number of Cells Computed in Exact Biological Sequence Comparison Algorithms"],"prefix":"10.1093","volume":"61","author":[{"given":"Edans F O","family":"Sandes","sequence":"first","affiliation":[{"name":"Department of Computer Science, University of Brasilia (UnB), Predio CIC-EST, Campus UNB, Asa Norte, 70910-900 Brasilia, Brazil"}]},{"given":"George L M","family":"Teodoro","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Brasilia (UnB), Predio CIC-EST, Campus UNB, Asa Norte, 70910-900 Brasilia, Brazil"}]},{"given":"Maria Emilia M T","family":"Walter","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Brasilia (UnB), Predio CIC-EST, Campus UNB, Asa Norte, 70910-900 Brasilia, Brazil"}]},{"given":"Xavier","family":"Martorell","sequence":"additional","affiliation":[{"name":"Department of Computer Architecture, Universitat Politecnica de Catalunya (UPC), C. Jordi Girona 1-3, Universitat Politecnica de Catalunya (UPC), 08034 Barcelona, Spain"}]},{"given":"Eduard","family":"Ayguade","sequence":"additional","affiliation":[{"name":"Department of Computer Architecture, Universitat Politecnica de Catalunya (UPC), C. Jordi Girona 1-3, Universitat Politecnica de Catalunya (UPC), 08034 Barcelona, Spain"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5191-5209","authenticated-orcid":false,"given":"Alba C M A","family":"Melo","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Brasilia (UnB), Predio CIC-EST, Campus UNB, Asa Norte, 70910-900 Brasilia, Brazil"}]}],"member":"286","published-online":{"date-parts":[[2017,10,13]]},"reference":[{"key":"key\n\t\t\t\t20180425035433_bxx090C1","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":"key\n\t\t\t\t20180425035433_bxx090C2","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":"key\n\t\t\t\t20180425035433_bxx090C3","doi-asserted-by":"crossref","first-page":"705","DOI":"10.1016\/0022-2836(82)90398-9","article-title":"An improved algorithm for matching biological sequences","volume":"162","author":"Gotoh","year":"1982","journal-title":"J. Mol. Biol."},{"key":"key\n\t\t\t\t20180425035433_bxx090C4","doi-asserted-by":"crossref","first-page":"341","DOI":"10.1145\/360825.360861","article-title":"A linear space algorithm for computing maximal common subsequences","volume":"18","author":"Hirschberg","year":"1975","journal-title":"Commun. ACM."},{"key":"key\n\t\t\t\t20180425035433_bxx090C5","first-page":"11","article-title":"Optimal alignments in linear space","volume":"4","author":"Myers","year":"1988","journal-title":"Comput. Appl. Biosci."},{"key":"key\n\t\t\t\t20180425035433_bxx090C6","doi-asserted-by":"crossref","first-page":"100","DOI":"10.1016\/S0019-9958(85)80046-2","article-title":"Algorithms for approximate string matching","volume":"64","author":"Ukkonen","year":"1985","journal-title":"Inf. Control"},{"key":"key\n\t\t\t\t20180425035433_bxx090C7","doi-asserted-by":"crossref","first-page":"557","DOI":"10.1137\/S0097539794264810","article-title":"Incremental string comparison","volume":"27","author":"Landau","year":"1985","journal-title":"SIAM J. Comput."},{"year":"2013","author":"Barton","key":"key\n\t\t\t\t20180425035433_bxx090C8"},{"year":"2009","author":"Hsu","key":"key\n\t\t\t\t20180425035433_bxx090C9"},{"year":"2016","author":"Hyyro","key":"key\n\t\t\t\t20180425035433_bxx090C10"},{"key":"key\n\t\t\t\t20180425035433_bxx090C11","doi-asserted-by":"crossref","first-page":"175","DOI":"10.1093\/nar\/12.1Part1.175","article-title":"Fast optimal alignment","volume":"12","author":"Fickett","year":"1984","journal-title":"Nucleic. Acids. Res."},{"year":"2001","author":"Davidson","key":"key\n\t\t\t\t20180425035433_bxx090C12"},{"key":"key\n\t\t\t\t20180425035433_bxx090C13","doi-asserted-by":"crossref","first-page":"403","DOI":"10.1016\/S0022-2836(05)80360-2","article-title":"Basic local alignment search tool","volume":"215","author":"Altschul","year":"1990","journal-title":"J. Mol. Biol."},{"key":"key\n\t\t\t\t20180425035433_bxx090C14","doi-asserted-by":"crossref","first-page":"1009","DOI":"10.1109\/TPDS.2012.194","article-title":"Retrieving Smith\u2013Waterman alignments with optimizations for megabase biological sequences using gpu","volume":"24","author":"Sandes","year":"2013","journal-title":"IEEE Trans. Par. Dist. Syst."},{"key":"key\n\t\t\t\t20180425035433_bxx090C15","doi-asserted-by":"crossref","first-page":"2494","DOI":"10.1093\/bioinformatics\/btt410","article-title":"SW#\u2014GPU-enabled exact alignments on genome scale","volume":"29","author":"Korpar","year":"2013","journal-title":"Bioinformatics"},{"key":"key\n\t\t\t\t20180425035433_bxx090C16","doi-asserted-by":"crossref","first-page":"321","DOI":"10.1186\/s12859-015-0744-4","article-title":"Accelerating the Smith\u2013Waterman algorithm with interpair pruning and band optimization for the all-pairs comparison of base sequences","volume":"16","author":"Okada","year":"2015","journal-title":"BMC. Bioinformatics"},{"key":"key\n\t\t\t\t20180425035433_bxx090C17","first-page":"28.1","article-title":"MASA: a multiplatform architecture for sequence aligners with block pruning","volume":"2","author":"Sandes","year":"2016","journal-title":"ACM Trans. Parallel Comput."},{"volume-title":"Bioinformatics: Sequence and Genome Analysis","year":"2004","author":"Mount","key":"key\n\t\t\t\t20180425035433_bxx090C18"},{"key":"key\n\t\t\t\t20180425035433_bxx090C19","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511790492","volume-title":"Biological Sequence Analysis","author":"Durbin","year":"1998"},{"year":"2014","author":"Schelter","key":"key\n\t\t\t\t20180425035433_bxx090C20"},{"key":"key\n\t\t\t\t20180425035433_bxx090C21","doi-asserted-by":"crossref","first-page":"337","DOI":"10.1089\/cmb.1994.1.337","article-title":"On the complexity of multiple sequence alignment","volume":"1","author":"Wang","year":"1994","journal-title":"J. Comput. Biol."},{"key":"key\n\t\t\t\t20180425035433_bxx090C22","doi-asserted-by":"crossref","first-page":"1073","DOI":"10.1137\/0148063","article-title":"The multiple sequence alignment problem in biology","volume":"48","author":"Carrillo","year":"1988","journal-title":"SIAM J. Appl. Math."},{"key":"key\n\t\t\t\t20180425035433_bxx090C23","doi-asserted-by":"crossref","first-page":"100","DOI":"10.1109\/TSSC.1968.300136","article-title":"A formal basis for the heuristic determination of minimum cost paths","volume":"SSC-4","author":"Hart","year":"1968","journal-title":"IEEE Trans. Syst. Sci. Cybern."}],"container-title":["The Computer Journal"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/academic.oup.com\/comjnl\/article-pdf\/61\/5\/687\/24724563\/bxx090.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,10,3]],"date-time":"2019-10-03T08:38:29Z","timestamp":1570091909000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/comjnl\/article\/61\/5\/687\/4539903"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,10,13]]},"references-count":23,"journal-issue":{"issue":"5","published-online":{"date-parts":[[2017,10,13]]},"published-print":{"date-parts":[[2018,5,1]]}},"URL":"https:\/\/doi.org\/10.1093\/comjnl\/bxx090","relation":{},"ISSN":["0010-4620","1460-2067"],"issn-type":[{"type":"print","value":"0010-4620"},{"type":"electronic","value":"1460-2067"}],"subject":[],"published-other":{"date-parts":[[2018,5]]},"published":{"date-parts":[[2017,10,13]]}}}