{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,29]],"date-time":"2026-05-29T09:15:27Z","timestamp":1780046127104,"version":"3.53.1"},"reference-count":40,"publisher":"Oxford University Press (OUP)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016,2,1]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Motivation: The three dimensional tertiary structure of a protein at near atomic level resolution provides insight alluding to its function and evolution. As protein structure decides its functionality, similarity in structure usually implies similarity in function. As such, structure alignment techniques are often useful in the classifications of protein function. Given the rapidly growing rate of new, experimentally determined structures being made available from repositories such as the Protein Data Bank, fast and accurate computational structure comparison tools are required. This paper presents SPalignNS, a non-sequential protein structure alignment tool using a novel asymmetrical greedy search technique.<\/jats:p><jats:p>Results: The performance of SPalignNS was evaluated against existing sequential and non-sequential structure alignment methods by performing trials with commonly used datasets. These benchmark datasets used to gauge alignment accuracy include (i) 9538 pairwise alignments implied by the HOMSTRAD database of homologous proteins; (ii) a subset of 64 difficult alignments from set (i) that have low structure similarity; (iii) 199 pairwise alignments of proteins with similar structure but different topology; and (iv) a subset of 20 pairwise alignments from the RIPC set. SPalignNS is shown to achieve greater alignment accuracy (lower or comparable root-mean squared distance with increased structure overlap coverage) for all datasets, and the highest agreement with reference alignments from the challenging dataset (iv) above, when compared with both sequentially constrained alignments and other non-sequential alignments.<\/jats:p><jats:p>Availability and implementation: SPalignNS was implemented in C++. The source code, binary executable, and a web server version is freely available at: http:\/\/sparks-lab.org<\/jats:p><jats:p>Contact: yaoqi.zhou@griffith.edu.au<\/jats:p>","DOI":"10.1093\/bioinformatics\/btv580","type":"journal-article","created":{"date-parts":[[2015,10,11]],"date-time":"2015-10-11T01:19:15Z","timestamp":1444526355000},"page":"370-377","source":"Crossref","is-referenced-by-count":24,"title":["Fast and accurate non-sequential protein structure alignment using a new asymmetric linear sum assignment heuristic"],"prefix":"10.1093","volume":"32","author":[{"given":"Peter","family":"Brown","sequence":"first","affiliation":[{"name":"1 School of ICT, Griffith University, Gold Coast, QLD 4222, Australia"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Wayne","family":"Pullan","sequence":"additional","affiliation":[{"name":"1 School of ICT, Griffith University, Gold Coast, QLD 4222, Australia"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yuedong","family":"Yang","sequence":"additional","affiliation":[{"name":"2 Institute for Glycomics, Griffith University, Gold Coast, QLD 4222, Australia"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yaoqi","family":"Zhou","sequence":"additional","affiliation":[{"name":"1 School of ICT, Griffith University, Gold Coast, QLD 4222, Australia"},{"name":"2 Institute for Glycomics, Griffith University, Gold Coast, QLD 4222, Australia"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"286","published-online":{"date-parts":[[2015,10,10]]},"reference":[{"key":"2023020110305310800_btv580-B1","doi-asserted-by":"crossref","first-page":"78","DOI":"10.1186\/1472-6807-7-78","article-title":"A comprehensive analysis of non-sequential alignments between all protein structures","volume":"7","author":"Abyzov","year":"2007","journal-title":"BMC Struct. Biol."},{"key":"2023020110305310800_btv580-B2","doi-asserted-by":"crossref","first-page":"727","DOI":"10.1093\/protein\/9.9.727","article-title":"Sarfing the pdb","volume":"9","author":"Alexandrov","year":"1996","journal-title":"Protein Eng."},{"key":"2023020110305310800_btv580-B3","doi-asserted-by":"crossref","first-page":"D419","DOI":"10.1093\/nar\/gkm993","article-title":"Data growth and its impact on the scop database: new developments","volume":"36","author":"Andreeva","year":"2008","journal-title":"Nucleic Acids Res."},{"key":"2023020110305310800_btv580-B4","doi-asserted-by":"crossref","first-page":"279","DOI":"10.1093\/protein\/6.3.279","article-title":"A computer vision based technique for 3-d sequence-independent structural comparison of proteins","volume":"6","author":"Bachar","year":"1993","journal-title":"Protein Eng."},{"key":"2023020110305310800_btv580-B5","doi-asserted-by":"crossref","first-page":"2027","DOI":"10.1002\/pro.213","article-title":"Accuracy analysis of multiple structure alignments","volume":"18","author":"Berbalk","year":"2009","journal-title":"Protein Sci."},{"key":"2023020110305310800_btv580-B6","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1007\/BF02186476","article-title":"The auction algorithm: a distributed relaxation method for the assignment problem","volume":"14","author":"Bertsekas","year":"1988","journal-title":"Ann. Oper. Res."},{"key":"2023020110305310800_btv580-B7","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1007\/978-1-4757-3023-4_2","article-title":"Linear assignment problems and extensions","volume-title":"Handbook of Combinatorial Optimization","author":"Burkard","year":"1999"},{"key":"2023020110305310800_btv580-B8","doi-asserted-by":"crossref","first-page":"932","DOI":"10.1038\/80697","article-title":"An overview of structural genomics","volume":"7","author":"Burley","year":"2000","journal-title":"Nat. Struct. Mol. Biol."},{"key":"2023020110305310800_btv580-B9","doi-asserted-by":"crossref","first-page":"823","DOI":"10.1002\/j.1460-2075.1986.tb04288.x","article-title":"The relation between the divergence of sequence and structure in proteins","volume":"5","author":"Chothia","year":"1986","journal-title":"EMBO J."},{"key":"2023020110305310800_btv580-B10","doi-asserted-by":"crossref","first-page":"i95","DOI":"10.1093\/bioinformatics\/btg1012","article-title":"Mass: multiple structural alignment by secondary structures","volume":"19","author":"Dror","year":"2003","journal-title":"Bioinformatics"},{"key":"2023020110305310800_btv580-B11","doi-asserted-by":"crossref","first-page":"2492","DOI":"10.1110\/ps.03200603","article-title":"Multiple structural alignment by secondary structures: algorithm and applications","volume":"12","author":"Dror","year":"2003","journal-title":"Protein Sci."},{"key":"2023020110305310800_btv580-B12","doi-asserted-by":"crossref","first-page":"125","DOI":"10.1007\/978-94-007-0881-5_7","article-title":"Sequence order independent comparison of protein global backbone structures and local binding surfaces for evolutionary and functional inference","author":"Dundas","year":"2011","journal-title":"Protein Function Prediction for Omics Era"},{"key":"2023020110305310800_btv580-B13","doi-asserted-by":"crossref","first-page":"D291","DOI":"10.1093\/nar\/gkl959","article-title":"The cath domain structure database: new protocols and classification levels give a more comprehensive resource for exploring evolution","volume":"35","author":"Greene","year":"2007","journal-title":"Nucleic Acids Res."},{"key":"2023020110305310800_btv580-B14","doi-asserted-by":"crossref","first-page":"1374","DOI":"10.1110\/ps.035469.108","article-title":"Novel protein folds and their nonsequential structural analogs","volume":"17","author":"Guerler","year":"2008","journal-title":"Protein Sci."},{"key":"2023020110305310800_btv580-B15","doi-asserted-by":"crossref","first-page":"123","DOI":"10.1006\/jmbi.1993.1489","article-title":"Protein structure comparison by alignment of distance matrices","volume":"233","author":"Holm","year":"1993","journal-title":"J. Mol. Biol."},{"key":"2023020110305310800_btv580-B16","doi-asserted-by":"crossref","first-page":"510","DOI":"10.1186\/1471-2105-7-510","article-title":"Connectivity independent protein-structure alignment: a hierarchical approach","volume":"7","author":"Kolbeck","year":"2006","journal-title":"BMC Bioinf."},{"key":"2023020110305310800_btv580-B17","doi-asserted-by":"crossref","first-page":"559","DOI":"10.1002\/prot.20921","article-title":"Mustang: a multiple structural alignment algorithm","volume":"64","author":"Konagurthu","year":"2006","journal-title":"Proteins Struct. Funct. Bioinf."},{"key":"2023020110305310800_btv580-B18","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1002\/nav.3800020109","article-title":"The Hungarian method for the assignment problem","volume":"2","author":"Kuhn","year":"1955","journal-title":"Naval Res. Logistics Q."},{"key":"2023020110305310800_btv580-B19","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1016\/B978-0-12-800168-4.00005-6","article-title":"Algorithms, applications, and challenges of protein structure alignment","volume":"94","author":"Ma","year":"2014","journal-title":"Adv. Protein Chem. Struct. Biol."},{"key":"2023020110305310800_btv580-B20","doi-asserted-by":"crossref","first-page":"569","DOI":"10.1093\/protein\/gzp040","article-title":"Alignment of multiple protein structures based on sequence and structure features","volume":"22","author":"Madhusudhan","year":"2009","journal-title":"Protein Eng. Des. Select."},{"key":"2023020110305310800_btv580-B21","doi-asserted-by":"crossref","first-page":"50","DOI":"10.1186\/1472-6807-7-50","article-title":"Comparative analysis of protein structure alignments","volume":"7","author":"Mayr","year":"2007","journal-title":"BMC Struct. Biol."},{"key":"2023020110305310800_btv580-B22","doi-asserted-by":"crossref","first-page":"24","DOI":"10.1186\/1471-2105-14-24","article-title":"Mican: a protein structure alignment algorithm that can handle multiple-chains, inverse alignments, c \u03b1 only models, alternative alignments, and non-sequential alignments","volume":"14","author":"Minami","year":"2013","journal-title":"BMC Bioinf."},{"key":"2023020110305310800_btv580-B23","doi-asserted-by":"crossref","first-page":"377","DOI":"10.1016\/0959-440X(95)80100-6","article-title":"Seeking significance in three-dimensional protein structure comparisons","volume":"5","author":"Mizuguchi","year":"1995","journal-title":"Curr. Opin. Struct. Biol."},{"key":"2023020110305310800_btv580-B24","doi-asserted-by":"crossref","first-page":"2469","DOI":"10.1002\/pro.5560071126","article-title":"Homstrad: a database of protein structure alignments for homologous families","volume":"7","author":"Mizuguchi","year":"1998","journal-title":"Protein Sci. Publ. Protein Soc."},{"key":"2023020110305310800_btv580-B25","author":"Naiem","year":"2009"},{"key":"2023020110305310800_btv580-B26","author":"Naiem","year":"2013"},{"key":"2023020110305310800_btv580-B27","doi-asserted-by":"crossref","first-page":"e94","DOI":"10.1093\/nar\/gkr348","article-title":"Biological insights from topology independent comparison of protein 3D structures","volume":"39","author":"Nguyen","year":"2011","journal-title":"Nucleic Acids Res."},{"key":"2023020110305310800_btv580-B28","doi-asserted-by":"crossref","first-page":"W24","DOI":"10.1093\/nar\/gkr393","article-title":"CLICK topology-independent comparison of biomolecular 3D structures","volume":"39","author":"Nguyen","year":"2011","journal-title":"Nucleic Acids Res."},{"key":"2023020110305310800_btv580-B29","doi-asserted-by":"crossref","first-page":"617","DOI":"10.1016\/S0076-6879(96)66038-8","article-title":"SSAP: sequential structure alignment program for protein structure comparison","volume":"266","author":"Orengo","year":"1996","journal-title":"Methods Enzymol."},{"key":"2023020110305310800_btv580-B30","doi-asserted-by":"crossref","DOI":"10.1186\/1471-2105-9-531","article-title":"Fr-TM-align: a new protein structural alignment method based on fragment alignments and the TM-score","volume":"9","author":"Pandit","year":"2008","journal-title":"BMC Bioinf."},{"key":"2023020110305310800_btv580-B31","volume-title":"R: A Language and Environment for Statistical Computing","author":"R Core Team","year":"2014"},{"key":"2023020110305310800_btv580-B32","doi-asserted-by":"crossref","first-page":"571","DOI":"10.1142\/S0219720009004205","article-title":"Iterative non-sequential protein structural alignment","volume":"7","author":"Salem","year":"2009","journal-title":"J. Bioinf. Comput. Biol."},{"key":"2023020110305310800_btv580-B33","doi-asserted-by":"crossref","first-page":"12","DOI":"10.1186\/1748-7188-5-12","article-title":"Flexsnap: flexible non-sequential protein structure alignment","volume":"5","author":"Salem","year":"2010","journal-title":"Algorithms Mol. Biol."},{"key":"2023020110305310800_btv580-B34","doi-asserted-by":"crossref","first-page":"779","DOI":"10.1006\/jmbi.1993.1626","article-title":"Comparative protein modelling by satisfaction of spatial restraints","volume":"234","author":"Sali","year":"1993","journal-title":"J. Mol. Biol."},{"key":"2023020110305310800_btv580-B35","first-page":"63","article-title":"Non-sequential protein structure comparisons","volume-title":"Sequence and Genome Analysis: Methods and Applications","author":"Shih","year":"2010"},{"key":"2023020110305310800_btv580-B36","doi-asserted-by":"crossref","first-page":"739","DOI":"10.1093\/protein\/11.9.739","article-title":"Protein structure alignment by incremental combinatorial extension (CE) of the optimal path","volume":"11","author":"Shindyalov","year":"1998","journal-title":"Protein Eng."},{"key":"2023020110305310800_btv580-B37","doi-asserted-by":"crossref","first-page":"389","DOI":"10.1287\/opre.1040.0189","article-title":"Optimal protein structure alignment using maximum cliques","volume":"53","author":"Strickland","year":"2005","journal-title":"Oper. Res."},{"key":"2023020110305310800_btv580-B38","doi-asserted-by":"crossref","first-page":"2080","DOI":"10.1002\/prot.24100","article-title":"A new size-independent score for pairwise protein structure alignment and its application to structure classification and nucleic-acid binding prediction","volume":"80","author":"Yang","year":"2012","journal-title":"Proteins"},{"key":"2023020110305310800_btv580-B39","doi-asserted-by":"crossref","first-page":"W582","DOI":"10.1093\/nar\/gkh430","article-title":"Fatcat: a web server for flexible structure comparison and structure similarity searching","volume":"32","author":"Ye","year":"2004","journal-title":"Nucleic Acids Res."},{"key":"2023020110305310800_btv580-B40","doi-asserted-by":"crossref","first-page":"2302","DOI":"10.1093\/nar\/gki524","article-title":"TM-align: a protein structure alignment algorithm based on the TM-score","volume":"33","author":"Zhang","year":"2005","journal-title":"Nucleic Acids Res."}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/32\/3\/370\/49016763\/bioinformatics_32_3_370.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/32\/3\/370\/49016763\/bioinformatics_32_3_370.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,31]],"date-time":"2025-05-31T00:22:46Z","timestamp":1748650966000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/32\/3\/370\/1743599"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,10,10]]},"references-count":40,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2016,2,1]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btv580","relation":{},"ISSN":["1367-4811","1367-4803"],"issn-type":[{"value":"1367-4811","type":"electronic"},{"value":"1367-4803","type":"print"}],"subject":[],"published-other":{"date-parts":[[2016,2,1]]},"published":{"date-parts":[[2015,10,10]]}}}