{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,19]],"date-time":"2025-03-19T14:00:53Z","timestamp":1742392853972},"reference-count":40,"publisher":"World Scientific Pub Co Pte Ltd","issue":"03","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. Bioinform. Comput. Biol."],"published-print":{"date-parts":[[2011,6]]},"abstract":"<jats:p>The problem of finding an optimal structural alignment for a pair of superimposed proteins is often amenable to the Smith\u2013Waterman dynamic programming algorithm, which runs in time proportional to the product of lengths of the sequences being aligned. While the quadratic running time is acceptable for computing a single alignment of two fixed protein structures, the time complexity becomes a bottleneck when running the Smith\u2013Waterman routine multiple times in order to find a globally optimal superposition and alignment of the input proteins. We present a subquadratic running time algorithm capable of computing an alignment that optimizes one of the most widely used measures of protein structure similarity, defined as the number of pairs of residues in two proteins that can be superimposed under a predefined distance cutoff. The algorithm presented in this article can be used to significantly improve the speed\u2013accuracy tradeoff in a number of popular protein structure alignment methods.<\/jats:p>","DOI":"10.1142\/s0219720011005562","type":"journal-article","created":{"date-parts":[[2011,4,20]],"date-time":"2011-04-20T01:52:56Z","timestamp":1303264376000},"page":"367-382","source":"Crossref","is-referenced-by-count":7,"title":["OPTIMAL PAIRWISE ALIGNMENT OF FIXED PROTEIN STRUCTURES IN SUBQUADRATIC TIME"],"prefix":"10.1142","volume":"09","author":[{"given":"ALEKSANDAR","family":"POLEKSIC","sequence":"first","affiliation":[{"name":"Department of Computer Science, University of Northern Iowa, Cedar Falls, Iowa 50613, USA"}]}],"member":"219","published-online":{"date-parts":[[2011,11,21]]},"reference":[{"key":"rf1","doi-asserted-by":"publisher","DOI":"10.1002\/prot.21767"},{"key":"rf2","doi-asserted-by":"publisher","DOI":"10.1002\/prot.21049"},{"key":"rf3","doi-asserted-by":"publisher","DOI":"10.1093\/nar\/gkh468"},{"key":"rf4","doi-asserted-by":"publisher","DOI":"10.1002\/prot.10474"},{"key":"rf5","doi-asserted-by":"publisher","DOI":"10.1002\/prot.20308"},{"key":"rf6","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.0704422105"},{"key":"rf7","doi-asserted-by":"publisher","DOI":"10.1093\/nar\/gkj062"},{"key":"rf8","doi-asserted-by":"publisher","DOI":"10.1142\/S0219720008003424"},{"key":"rf9","first-page":"536","volume":"247","author":"Murzin A. G.","journal-title":"J. Mol. Biol."},{"key":"rf10","doi-asserted-by":"publisher","DOI":"10.1016\/S0969-2126(97)00260-8"},{"key":"rf11","doi-asserted-by":"publisher","DOI":"10.1016\/S1476-9271(02)00098-1"},{"key":"rf13","doi-asserted-by":"publisher","DOI":"10.1089\/106652704773416876"},{"key":"rf15","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.0404383101"},{"key":"rf16","doi-asserted-by":"publisher","DOI":"10.1006\/jmbi.1993.1489"},{"key":"rf17","doi-asserted-by":"publisher","DOI":"10.1002\/prot.340110107"},{"key":"rf18","doi-asserted-by":"publisher","DOI":"10.1016\/0022-2836(89)90084-3"},{"key":"rf19","doi-asserted-by":"publisher","DOI":"10.1016\/S0076-6879(96)66038-8"},{"key":"rf20","doi-asserted-by":"publisher","DOI":"10.1016\/0022-2836(92)91021-G"},{"key":"rf21","doi-asserted-by":"publisher","DOI":"10.1093\/protein\/11.9.739"},{"key":"rf23","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.95.11.5913"},{"key":"rf24","doi-asserted-by":"publisher","DOI":"10.1093\/nar\/gki524"},{"key":"rf25","doi-asserted-by":"publisher","DOI":"10.1107\/S0907444907000844"},{"key":"rf27","doi-asserted-by":"publisher","DOI":"10.1093\/nar\/gkg571"},{"key":"rf28","first-page":"1629","volume":"79","author":"Akutsu T.","journal-title":"IEICE. Trans. Ins. Syst. E"},{"key":"rf29","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btp530"},{"key":"rf31","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-69068-9_7"},{"key":"rf32","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/16.9.776"},{"key":"rf33","doi-asserted-by":"publisher","DOI":"10.1006\/jmbi.1993.1626"},{"key":"rf34","doi-asserted-by":"publisher","DOI":"10.1093\/nar\/gki327"},{"key":"rf35","doi-asserted-by":"publisher","DOI":"10.1002\/prot.10538"},{"key":"rf36","doi-asserted-by":"publisher","DOI":"10.1110\/ps.04888805"},{"key":"rf37","doi-asserted-by":"publisher","DOI":"10.1016\/0022-2836(81)90087-5"},{"key":"rf38","first-page":"1209","volume":"11","author":"Arlazaro V. L.","journal-title":"Soviet. Math. Dokl."},{"key":"rf39","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(80)90002-1"},{"key":"rf40","doi-asserted-by":"crossref","first-page":"417","DOI":"10.4171\/rmi\/178","volume":"11","author":"Chamizo F.","journal-title":"Revista Matem\u00e1tica Iberoamericana"},{"key":"rf41","doi-asserted-by":"publisher","DOI":"10.1145\/359581.359603"},{"key":"rf42","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0255(80)90025-0"},{"key":"rf43","doi-asserted-by":"publisher","DOI":"10.1145\/322033.322044"},{"key":"rf44","doi-asserted-by":"publisher","DOI":"10.1002\/pro.5560011217"},{"key":"rf45","doi-asserted-by":"publisher","DOI":"10.1110\/ps.0215902"}],"container-title":["Journal of Bioinformatics and Computational Biology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0219720011005562","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,4,6]],"date-time":"2024-04-06T07:25:37Z","timestamp":1712388337000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0219720011005562"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,6]]},"references-count":40,"journal-issue":{"issue":"03","published-online":{"date-parts":[[2011,11,21]]},"published-print":{"date-parts":[[2011,6]]}},"alternative-id":["10.1142\/S0219720011005562"],"URL":"https:\/\/doi.org\/10.1142\/s0219720011005562","relation":{},"ISSN":["0219-7200","1757-6334"],"issn-type":[{"value":"0219-7200","type":"print"},{"value":"1757-6334","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,6]]}}}