{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,12]],"date-time":"2025-11-12T13:48:15Z","timestamp":1762955295622},"reference-count":46,"publisher":"Oxford University Press (OUP)","issue":"9","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014,5,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>Motivation: Protein structure alignment is key for transferring information from well-studied proteins to less studied ones. Structural alignment identifies the most precise mapping of equivalent residues, as structures are more conserved during evolution than sequences. Among the methods for aligning protein structures, maximum Contact Map Overlap (CMO) has received sustained attention during the past decade. Yet, known algorithms exhibit modest performance and are not applicable for large-scale comparison.<\/jats:p>\n               <jats:p>Results: Graphlets are small induced subgraphs that are used to design sensitive topological similarity measures between nodes and networks. By generalizing graphlets to ordered graphs, we introduce GR-Align, a CMO heuristic that is suited for database searches. On the Proteus_300 set (44 850 protein domain pairs), GR-Align is several orders of magnitude faster than the state-of-the-art CMO solvers Apurva, MSVNS and AlEigen7, and its similarity score is in better agreement with the structural classification of proteins. On a large-scale experiment on the Gold-standard benchmark dataset (3 207 270 protein domain pairs), GR-Align is several orders of magnitude faster than the state-of-the-art protein structure comparison tools TM-Align, DaliLite, MATT and Yakusa, while achieving similar classification performances. Finally, we illustrate the difference between GR-Align\u2019s flexible alignments and the traditional ones by querying a flexible protein in the Astral-40 database (11 154 protein domains). In this experiment, GR-Align\u2019s top scoring alignments are not only in better agreement with structural classification of proteins, but also that they allow transferring more information across proteins.<\/jats:p>\n               <jats:p>Availability and implementation: GR-Align is coded in C++. software and supplementary material are available at: http:\/\/bio-nets.doc.ic.ac.uk\/home\/software\/gralign\/.<\/jats:p>\n               <jats:p>Contact: \u00a0n.malod-dognin@imperial.ac.uk<\/jats:p>\n               <jats:p>Supplementary information: \u00a0Supplementary data are available at Bioinformatics online.<\/jats:p>","DOI":"10.1093\/bioinformatics\/btu020","type":"journal-article","created":{"date-parts":[[2014,1,19]],"date-time":"2014-01-19T01:24:37Z","timestamp":1390094677000},"page":"1259-1265","source":"Crossref","is-referenced-by-count":52,"title":["GR-Align: fast and flexible alignment of protein 3D structures using graphlet degree similarity"],"prefix":"10.1093","volume":"30","author":[{"given":"No\u00ebl","family":"Malod-Dognin","sequence":"first","affiliation":[{"name":"Department of Computing, Imperial College London, SW7 2AZ, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nata\u0161a","family":"Pr\u017eulj","sequence":"additional","affiliation":[{"name":"Department of Computing, Imperial College London, SW7 2AZ, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2014,1,17]]},"reference":[{"key":"2023012710512013900_btu020-B1","doi-asserted-by":"crossref","first-page":"131","DOI":"10.1089\/cmb.2007.0004","article-title":"Fast molecular shape matching using contact maps","volume":"14","author":"Agarwal","year":"2007","journal-title":"J. Comput. Biol."},{"key":"2023012710512013900_btu020-B2","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":"2023012710512013900_btu020-B3","first-page":"162","article-title":"An efficient lagrangian relaxation for the contact map overlap problem","volume-title":"WABI\u201908: Proceedings of the 8th International Workshop on Algorithms in Bioinformatics","author":"Andonov","year":"2008"},{"key":"2023012710512013900_btu020-B4","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1089\/cmb.2009.0196","article-title":"Maximum contact map overlap revisited","volume":"18","author":"Andonov","year":"2011","journal-title":"J. Comput. Biol."},{"key":"2023012710512013900_btu020-B5","doi-asserted-by":"crossref","first-page":"254","DOI":"10.1093\/nar\/28.1.254","article-title":"The astral compendium for sequence and structure analysis","volume":"28","author":"Brenner","year":"2000","journal-title":"Nucleic Acids Res."},{"key":"2023012710512013900_btu020-B6","doi-asserted-by":"crossref","first-page":"100","DOI":"10.1145\/565196.565209","article-title":"Structural alignment of large\u2014size proteins via lagrangian relaxation","volume-title":"RECOMB\u201902: Proceedings of the Sixth Annual International Conference on Computational biology","author":"Caprara","year":"2002"},{"key":"2023012710512013900_btu020-B7","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1089\/106652704773416876","article-title":"1001 optimal PDB structure alignments: integer programming methods for finding the maximum contact map overlap","volume":"11","author":"Caprara","year":"2004","journal-title":"J. Comput. Biol."},{"key":"2023012710512013900_btu020-B8","article-title":"Branch-and-cut algorithms for independent set problems: integrality gap and an application to protein structure alignment","volume-title":"Technical report","author":"Carr","year":"2000"},{"key":"2023012710512013900_btu020-B9","doi-asserted-by":"crossref","first-page":"90","DOI":"10.1145\/306198.306210","article-title":"How to find the best approximation results \u2013 a follow-up to Garey and Johnson","volume":"29","author":"Crescenzi","year":"1998","journal-title":"ACM SIGACT News"},{"key":"2023012710512013900_btu020-B10","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1186\/1472-6807-9-23","article-title":"Systematic comparison of SCOP and CATH: a new gold standard for protein structure analysis","volume":"9","author":"Csaba","year":"2009","journal-title":"BMC Struct. Biol."},{"key":"2023012710512013900_btu020-B11","first-page":"233","article-title":"The relationship between precision-recall and roc curves","volume-title":"Proceedings of the 23rd International Conference on Machine learning, ICML\u201906","author":"Davis","year":"2006"},{"key":"2023012710512013900_btu020-B12","doi-asserted-by":"crossref","first-page":"2250","DOI":"10.1093\/bioinformatics\/btq402","article-title":"Fast overlapping of protein contact maps by alignment of eigenvectors","volume":"26","author":"Di Lena","year":"2010","journal-title":"Bioinformatics"},{"key":"2023012710512013900_btu020-B13","doi-asserted-by":"crossref","first-page":"156","DOI":"10.1093\/bioinformatics\/btl582","article-title":"Striped smithwaterman speeds database searches six times over other SIMD implementations","volume":"23","author":"Farrar","year":"2007","journal-title":"Bioinformatics"},{"key":"2023012710512013900_btu020-B14","doi-asserted-by":"crossref","first-page":"861","DOI":"10.1016\/j.patrec.2005.10.010","article-title":"An introduction to ROC analysis","volume":"27","author":"Fawcett","year":"2006","journal-title":"Pattern Recognit. Lett."},{"key":"2023012710512013900_btu020-B15","doi-asserted-by":"crossref","first-page":"377","DOI":"10.1016\/S0959-440X(96)80058-3","article-title":"Surprising similarities in structure comparison","volume":"6","author":"Gibrat","year":"1996","journal-title":"Curr. Opin. Struct. Biol."},{"key":"2023012710512013900_btu020-B16","doi-asserted-by":"crossref","first-page":"1325","DOI":"10.1002\/pro.5560050711","article-title":"The structural alignment between two proteins: Is there a unique answer?","volume":"5","author":"Godzik","year":"1996","journal-title":"Protein Sci."},{"key":"2023012710512013900_btu020-B17","first-page":"587","article-title":"Flexible algorithm for direct multiple alignment of protein structures and seequences","volume":"10","author":"Godzik","year":"1994","journal-title":"CABIOS"},{"key":"2023012710512013900_btu020-B18","first-page":"512","article-title":"Algorithmic aspects of protein structure similarity","volume-title":"FOCS\u201999: Proceedings of the 40th Annual Symposium on Foundations of Computer Science","author":"Goldman","year":"1999"},{"key":"2023012710512013900_btu020-B19","doi-asserted-by":"crossref","first-page":"341","DOI":"10.1016\/j.sbi.2009.04.003","article-title":"Advances and pitfalls of protein structural alignment","volume":"19","author":"Hasegawa","year":"2009","journal-title":"Curr. Opin. Struct. Biol."},{"key":"2023012710512013900_btu020-B20","doi-asserted-by":"crossref","first-page":"4673","DOI":"10.1093\/nar\/22.22.4673","article-title":"CLUSTAL W: improving the sensitivity of progressive multiple sequence alignment through sequence weighting, position-specific gap penalties and weight matrix choice","volume":"22","author":"Higgins","year":"1994","journal-title":"Nucleic Acids Res."},{"key":"2023012710512013900_btu020-B21","doi-asserted-by":"crossref","first-page":"566","DOI":"10.1093\/bioinformatics\/16.6.566","article-title":"Dalilite workbench for protein structure comparison","volume":"16","author":"Holm","year":"2000","journal-title":"Bioinformatics"},{"key":"2023012710512013900_btu020-B22","doi-asserted-by":"crossref","first-page":"123","DOI":"10.1006\/jmbi.1993.1489","article-title":"Protein structure comparison by alignment of distance matrices","volume":"223","author":"Holm","year":"1993","journal-title":"J. Mol. Biol."},{"key":"2023012710512013900_btu020-B23","article-title":"Joining softassign and dynamic programming for the contact map overlap problem","volume-title":"BIRD","author":"Jain","year":"2007"},{"key":"2023012710512013900_btu020-B24","doi-asserted-by":"crossref","first-page":"1390","DOI":"10.1093\/bioinformatics\/btr127","article-title":"Integrative network alignment reveals large regions of global network similarity in yeast and human","volume":"27","author":"Kuchaiev","year":"2011","journal-title":"Bioinformatics"},{"key":"2023012710512013900_btu020-B25","doi-asserted-by":"crossref","first-page":"1585","DOI":"10.1093\/bioinformatics\/btg192","article-title":"Clustalw-mpi: clustalw analysis using distributed and parallel computing","volume":"19","author":"Li","year":"2003","journal-title":"Bioinformatics"},{"key":"2023012710512013900_btu020-B26","doi-asserted-by":"crossref","DOI":"10.1007\/11945918_37","article-title":"Gpu-clustalw: Using graphics hardware to accelerate multiple sequence alignment","volume-title":"High Performance Computing - HiPC 2006","author":"Liu","year":"2006"},{"key":"2023012710512013900_btu020-B27","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1186\/1756-0500-2-73","article-title":"Cudasw++: optimizing Smith-Waterman sequence database searches for CUDA-enabled graphics processing units","volume":"2","author":"Liu","year":"2009","journal-title":"BMC Res. Notes"},{"key":"2023012710512013900_btu020-B28","first-page":"106","article-title":"Maximum clique in protein structure comparison","volume-title":"Proceedings of the 9th International Symposium on Experimental Algorithms, SEA 2010","author":"Malod-Dognin","year":"2010"},{"key":"2023012710512013900_btu020-B29","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":"2023012710512013900_btu020-B30","doi-asserted-by":"crossref","first-page":"e10","DOI":"10.1371\/journal.pcbi.0040010","article-title":"Matt: Local flexibility aids protein multiple structure alignment","volume":"4","author":"Menke","year":"2008","journal-title":"PLoS Comput. Biol."},{"key":"2023012710512013900_btu020-B31","doi-asserted-by":"crossref","first-page":"121","DOI":"10.4137\/CIN.S4744","article-title":"Optimal network alignment with graphlet degree vectors","volume":"9","author":"Milenkovi\u0107","year":"2010","journal-title":"Cancer Inform."},{"key":"2023012710512013900_btu020-B32","doi-asserted-by":"crossref","first-page":"536","DOI":"10.1016\/S0022-2836(05)80134-2","article-title":"Scop: a structural classification of proteins database for the investigation of sequences and structures","volume":"247","author":"Murzin","year":"1995","journal-title":"J. Mol. Biol."},{"key":"2023012710512013900_btu020-B33","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":"2023012710512013900_btu020-B34","doi-asserted-by":"crossref","first-page":"161","DOI":"10.1186\/1471-2105-9-161","article-title":"A simple and fast heuristic for protein structure comparison","volume":"9","author":"Pelta","year":"2008","journal-title":"BMC Bioinformatics"},{"key":"2023012710512013900_btu020-B35","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1093\/bioinformatics\/btl301","article-title":"Biological network comparison using graphlet degree distribution","volume":"23","author":"Pr\u017eulj","year":"2007","journal-title":"Bioinformatics"},{"key":"2023012710512013900_btu020-B36","doi-asserted-by":"crossref","first-page":"3508","DOI":"10.1093\/bioinformatics\/bth436","article-title":"Modeling interactome: scale-free or geometric?","volume":"20","author":"Pr\u017eulj","year":"2004","journal-title":"Bioinformatics"},{"key":"2023012710512013900_btu020-B37","doi-asserted-by":"crossref","first-page":"867","DOI":"10.1109\/TCBB.2011.24","article-title":"A spectral approach to protein structure alignment","volume":"8","author":"Shibberu","year":"2011","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinform."},{"key":"2023012710512013900_btu020-B38","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":"2023012710512013900_btu020-B39","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":"2023012710512013900_btu020-B40","doi-asserted-by":"crossref","first-page":"1348","DOI":"10.1093\/bioinformatics\/btq140","article-title":"A croc stronger than ROC: measuring, visualizing and optimizing early retrieval","volume":"26","author":"Swamidass","year":"2010","journal-title":"Bioinformatics"},{"key":"2023012710512013900_btu020-B41","doi-asserted-by":"crossref","first-page":"404","DOI":"10.1046\/j.1432-1033.2003.03414.x","article-title":"Novel aspects of calmodulin target recognition and activation","volume":"270","author":"Vetter","year":"2003","journal-title":"Eur. J. Biochem"},{"key":"2023012710512013900_btu020-B42","doi-asserted-by":"crossref","first-page":"P2","DOI":"10.1186\/1471-2105-10-S13-P2","article-title":"Paul: protein structural alignment using integer linear programming and lagrangian relaxation","volume":"10","author":"Wohlers","year":"2009","journal-title":"BMC Bioinformatics"},{"key":"2023012710512013900_btu020-B43","doi-asserted-by":"crossref","first-page":"637","DOI":"10.1089\/cmb.2007.R007","article-title":"A reduction-based exact algorithm for the contact map overlap problem","volume":"14","author":"Xie","year":"2007","journal-title":"J. Comput. Biol."},{"key":"2023012710512013900_btu020-B44","doi-asserted-by":"crossref","first-page":"564","DOI":"10.1089\/cmb.2007.R003","article-title":"A parameterized algorithm for protein structure alignment","volume":"14","author":"Xu","year":"2007","journal-title":"J. Comput. Biol."},{"key":"2023012710512013900_btu020-B45","doi-asserted-by":"crossref","first-page":"II246","DOI":"10.1093\/bioinformatics\/btg1086","article-title":"Flexible structure alignment by chaining aligned fragment pairs allowing twists","volume":"19","author":"Ye","year":"2003","journal-title":"Bioinformatics"},{"key":"2023012710512013900_btu020-B46","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\/30\/9\/1259\/48922768\/bioinformatics_30_9_1259.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/30\/9\/1259\/48922768\/bioinformatics_30_9_1259.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,27]],"date-time":"2023-01-27T11:31:15Z","timestamp":1674819075000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/30\/9\/1259\/237301"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,1,17]]},"references-count":46,"journal-issue":{"issue":"9","published-print":{"date-parts":[[2014,5,1]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btu020","relation":{},"ISSN":["1367-4811","1367-4803"],"issn-type":[{"value":"1367-4811","type":"electronic"},{"value":"1367-4803","type":"print"}],"subject":[],"published-other":{"date-parts":[[2014,5,1]]},"published":{"date-parts":[[2014,1,17]]}}}