{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T21:54:45Z","timestamp":1740174885122,"version":"3.37.3"},"reference-count":34,"publisher":"Wiley","license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/3.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Scientific Programming"],"published-print":{"date-parts":[[2015]]},"abstract":"<jats:p>Finding similarities between protein structures is a crucial task in molecular biology. Most of the existing tools require proteins to be aligned in order-preserving way and only find single alignments even when multiple similar regions exist. We propose a new seed-based approach that discovers multiple pairs of similar regions. Its computational complexity is polynomial and it comes with a quality guarantee\u2014the returned alignments have both root mean squared deviations (coordinate-based as well as internal-distances based) lower than a given threshold, if such exist. We do not require the alignments to be order preserving (i.e., we consider nonsequential alignments), which makes our algorithm suitable for detecting similar domains when comparing multidomain proteins as well as to detect structural repetitions within a single protein. Because the search space for nonsequential alignments is much larger than for sequential ones, the computational burden is addressed by extensive use of parallel computing techniques: a coarse-grain level parallelism making use of available CPU cores for computation and a fine-grain level parallelism exploiting bit-level concurrency as well as vector instructions.<\/jats:p>","DOI":"10.1155\/2015\/279715","type":"journal-article","created":{"date-parts":[[2015,4,9]],"date-time":"2015-04-09T02:42:47Z","timestamp":1428547367000},"page":"1-12","source":"Crossref","is-referenced-by-count":2,"title":["Parallel Seed-Based Approach to Multiple Protein Structure Similarities Detection"],"prefix":"10.1155","volume":"2015","author":[{"given":"Guillaume","family":"Chapuis","sequence":"first","affiliation":[{"name":"INRIA\/IRISA and University of Rennes 1, Campus Universitaire de Beaulieu, 35042 Rennes Cedex, France"}]},{"given":"Mathilde","family":"Le Boudic-Jamin","sequence":"additional","affiliation":[{"name":"INRIA\/IRISA and University of Rennes 1, Campus Universitaire de Beaulieu, 35042 Rennes Cedex, France"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4842-7102","authenticated-orcid":true,"given":"Rumen","family":"Andonov","sequence":"additional","affiliation":[{"name":"INRIA\/IRISA and University of Rennes 1, Campus Universitaire de Beaulieu, 35042 Rennes Cedex, France"}]},{"given":"Hristo","family":"Djidjev","sequence":"additional","affiliation":[{"name":"Los Alamos National Laboratory, Information Sciences, P.O. Box 1663, MS B256, Los Alamos, NM 87545, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2557-680X","authenticated-orcid":true,"given":"Dominique","family":"Lavenier","sequence":"additional","affiliation":[{"name":"INRIA\/IRISA and University of Rennes 1, Campus Universitaire de Beaulieu, 35042 Rennes Cedex, France"}]}],"member":"311","reference":[{"key":"12","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.0404383101"},{"key":"7","doi-asserted-by":"publisher","DOI":"10.1006\/jmbi.1993.1489"},{"key":"20","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btu020"},{"key":"27","doi-asserted-by":"publisher","DOI":"10.1093\/protein\/11.9.739"},{"key":"32","doi-asserted-by":"publisher","DOI":"10.1093\/nar\/gkg571"},{"key":"33","doi-asserted-by":"publisher","DOI":"10.1093\/nar\/gki524"},{"key":"10","doi-asserted-by":"publisher","DOI":"10.1016\/S0959-440X(00)00214-1"},{"key":"18","doi-asserted-by":"publisher","DOI":"10.1371\/journal.pcbi.1001075"},{"key":"16","doi-asserted-by":"publisher","DOI":"10.1093\/protein\/7.9.1059"},{"key":"5","doi-asserted-by":"publisher","DOI":"10.1016\/S0959-440X(96)80058-3"},{"key":"26","doi-asserted-by":"publisher","DOI":"10.1016\/s0022-2836(02)00811-2"},{"key":"13","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btq100"},{"key":"19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"106","DOI":"10.1007\/978-3-642-13193-6_10","volume-title":"Maximum cliques in protein structure comparison","volume":"6049","year":"2010"},{"key":"28","doi-asserted-by":"publisher","DOI":"10.1287\/opre.1040.0189"},{"key":"2","doi-asserted-by":"publisher","DOI":"10.1002\/pro.213"},{"key":"21","doi-asserted-by":"publisher","DOI":"10.1186\/1471-2105-14-24"},{"key":"3","series-title":"Lecture Notes in Computer Science","first-page":"278","volume-title":"Parallel seed-based approach to protein structure similarity detection","volume":"8385","year":"2013"},{"key":"34","doi-asserted-by":"publisher","DOI":"10.1002\/prot.20264"},{"key":"8","doi-asserted-by":"publisher","DOI":"10.1002\/prot.340190302"},{"key":"30","doi-asserted-by":"publisher","DOI":"10.1109\/tcbb.2012.143"},{"key":"31","doi-asserted-by":"publisher","DOI":"10.1186\/1471-2105-10-s13-p2"},{"key":"29","doi-asserted-by":"publisher","DOI":"10.1016\/0960-9822(93)90255-m"},{"key":"11","doi-asserted-by":"publisher","DOI":"10.1016\/j.jmb.2004.12.032"},{"first-page":"606","volume-title":"Finding, counting and listing all triangles in large graphs, an experimental study","year":"2005","key":"25"},{"key":"17","doi-asserted-by":"publisher","DOI":"10.1002\/jcc.21439"},{"key":"9","doi-asserted-by":"publisher","DOI":"10.1137\/s1064827595287997"},{"key":"4","doi-asserted-by":"publisher","DOI":"10.1109\/99.660313"},{"key":"15","doi-asserted-by":"publisher","DOI":"10.1145\/358080.358103"},{"key":"1","doi-asserted-by":"publisher","DOI":"10.1089\/cmb.2009.0196"},{"volume":"1","year":"1999","key":"6"},{"key":"22","doi-asserted-by":"publisher","DOI":"10.1002\/prot.20202"},{"key":"23","doi-asserted-by":"publisher","DOI":"10.1021\/jp402105j"},{"key":"14","doi-asserted-by":"publisher","DOI":"10.1093\/protein\/13.11.745"},{"key":"24","doi-asserted-by":"publisher","DOI":"10.1186\/1748-7188-5-12"}],"container-title":["Scientific Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/downloads.hindawi.com\/journals\/sp\/2015\/279715.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/downloads.hindawi.com\/journals\/sp\/2015\/279715.xml","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/downloads.hindawi.com\/journals\/sp\/2015\/279715.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2017,6,23]],"date-time":"2017-06-23T04:59:37Z","timestamp":1498193977000},"score":1,"resource":{"primary":{"URL":"http:\/\/www.hindawi.com\/journals\/sp\/2015\/279715\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"references-count":34,"alternative-id":["279715","279715"],"URL":"https:\/\/doi.org\/10.1155\/2015\/279715","relation":{},"ISSN":["1058-9244","1875-919X"],"issn-type":[{"type":"print","value":"1058-9244"},{"type":"electronic","value":"1875-919X"}],"subject":[],"published":{"date-parts":[[2015]]}}}