{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,1]],"date-time":"2025-11-01T02:08:38Z","timestamp":1761962918200,"version":"build-2065373602"},"reference-count":41,"publisher":"Oxford University Press (OUP)","issue":"18","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010,9,15]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Motivation: Structural alignments of proteins are important for identification of structural similarities, homology detection and functional annotation. The structural alignment problem is well studied and computationally difficult. Many different scoring schemes for structural similarity as well as many algorithms for finding high-scoring alignments have been proposed. Algorithms using contact map overlap (CMO) as scoring function are currently the only practical algorithms able to compute provably optimal alignments.<\/jats:p><jats:p>Results: We propose a new mathematical model for the alignment of inter-residue distance matrices, building upon previous work on maximum CMO. Our model includes all elements needed to emulate various scoring schemes for the alignment of protein distance matrices. The algorithm that we use to compute alignments is practical only for sparse distance matrices. Therefore, we propose a more effective scoring function, which uses a distance threshold and only positive structural scores. We show that even under these restrictions our approach is in terms of alignment accuracy competitive with state-of-the-art structural alignment algorithms, whereas it additionally either proves the optimality of an alignment or returns bounds on the optimal score. Our novel method is freely available and constitutes an important promising step towards truly provably optimal structural alignments of proteins.<\/jats:p><jats:p>Availability: An executable of our program PAUL is available at http:\/\/planet-lisa.net\/<\/jats:p><jats:p>Contact: \u00a0Inken.Wohlers@cwi.nl<\/jats:p><jats:p>Supplementary information: \u00a0Supplementary data are available at Bioinformatics online.<\/jats:p>","DOI":"10.1093\/bioinformatics\/btq420","type":"journal-article","created":{"date-parts":[[2010,7,18]],"date-time":"2010-07-18T00:34:14Z","timestamp":1279413254000},"page":"2273-2280","source":"Crossref","is-referenced-by-count":20,"title":["Towards optimal alignment of protein structure distance matrices"],"prefix":"10.1093","volume":"26","author":[{"given":"Inken","family":"Wohlers","sequence":"first","affiliation":[{"name":"1 CWI, Life Sciences Group, P.O. Box 94079, 1090 GB Amsterdam, The Netherlands and 2Max-Planck-Institut f\u00fcr Informatik, Campus E1 4, 66123 Saarbr\u00fccken, Germany"}]},{"given":"Francisco S.","family":"Domingues","sequence":"additional","affiliation":[{"name":"1 CWI, Life Sciences Group, P.O. Box 94079, 1090 GB Amsterdam, The Netherlands and 2Max-Planck-Institut f\u00fcr Informatik, Campus E1 4, 66123 Saarbr\u00fccken, Germany"}]},{"given":"Gunnar W.","family":"Klau","sequence":"additional","affiliation":[{"name":"1 CWI, Life Sciences Group, P.O. Box 94079, 1090 GB Amsterdam, The Netherlands and 2Max-Planck-Institut f\u00fcr Informatik, Campus E1 4, 66123 Saarbr\u00fccken, Germany"}]}],"member":"286","published-online":{"date-parts":[[2010,7,17]]},"reference":[{"key":"2023012508213165300_B1","doi-asserted-by":"crossref","first-page":"162","DOI":"10.1007\/978-3-540-87361-7_14","article-title":"An efficient Lagrangian relaxation for the contact map overlap problem","volume-title":"Proceedings of the 8th international workshop on Algorithms in Bioinformatics","author":"Andonov","year":"2008"},{"issue":"Database issue","key":"2023012508213165300_B2","doi-asserted-by":"crossref","first-page":"253","DOI":"10.1093\/nar\/gkl746","article-title":"SISYPHUS\u2014structural alignments for proteins with non-trivial relationships","volume":"35","author":"Andreeva","year":"2007","journal-title":"Nucleic Acids Res"},{"key":"2023012508213165300_B3","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":"2023012508213165300_B4","doi-asserted-by":"crossref","first-page":"271","DOI":"10.1186\/1471-2105-8-271","article-title":"Accurate multiple sequence-structure alignment of RNA sequences using combinatorial optimization","volume":"8","author":"Bauer","year":"2007","journal-title":"BMC Bioinformatics"},{"key":"2023012508213165300_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":"2023012508213165300_B6","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1093\/bioinformatics\/btl294","article-title":"Vorolign\u2014fast structural alignment using Voronoi contacts","volume":"23","author":"Birzele","year":"2007","journal-title":"Bioinformatics"},{"key":"2023012508213165300_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":"2023012508213165300_B8","doi-asserted-by":"crossref","first-page":"98","DOI":"10.1093\/bioinformatics\/btn271","article-title":"Protein structure alignment considering phenotypic plasticity","volume":"24","author":"Csaba","year":"2008","journal-title":"Bioinformatics"},{"key":"2023012508213165300_B9","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":"2023012508213165300_B10","doi-asserted-by":"crossref","first-page":"11967","DOI":"10.1021\/bi9605245","article-title":"A pseudo-michaelis quaternary complex in the reverse reaction of a ligase: structure of Escherichia coli B glutathione synthetase complexed with ADP, glutathione, and sulfate at 2.0 A resolution","volume":"35","author":"Hara","year":"1996","journal-title":"Biochemistry"},{"key":"2023012508213165300_B11","doi-asserted-by":"crossref","first-page":"665","DOI":"10.1016\/S0092-8240(83)80020-2","article-title":"The theory and practice of distance geometry","volume":"45","author":"Havel","year":"1983","journal-title":"Bull. Math. Biol"},{"key":"2023012508213165300_B12","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":"2023012508213165300_B13","first-page":"1394","article-title":"Bimal: bipartite matching alignment for the contact map overlap problem","volume-title":"Proceedings of the International Joint Conference on Neural Networks (IJCNN '09)","author":"Jain","year":"2009"},{"key":"2023012508213165300_B14","doi-asserted-by":"crossref","first-page":"535","DOI":"10.1093\/protein\/13.8.535","article-title":"Protein structure alignment using environmental profiles","volume":"13","author":"Jung","year":"2000","journal-title":"Protein Eng"},{"key":"2023012508213165300_B15","doi-asserted-by":"crossref","first-page":"2577","DOI":"10.1002\/bip.360221211","article-title":"Dictionary of protein secondary structure: pattern recognition of hydrogen-bonded and geometrical features","volume":"22","author":"Kabsch","year":"1983","journal-title":"Biopolymers"},{"key":"2023012508213165300_B16","doi-asserted-by":"crossref","first-page":"3367","DOI":"10.1093\/nar\/gkg581","article-title":"MATRAS: a program for protein 3D structure comparison","volume":"31","author":"Kawabata","year":"2003","journal-title":"Nucleic Acids Res"},{"key":"2023012508213165300_B17","doi-asserted-by":"crossref","first-page":"106","DOI":"10.1007\/BFb0029800","article-title":"The maximum weight trace problem in multiple sequence alignment","volume-title":"Proceedings of the Fourth Annual Symposium of Combinatorial Pattern Matching (CPM 93)","author":"Kececioglu","year":"1993"},{"key":"2023012508213165300_B18","doi-asserted-by":"crossref","first-page":"12201","DOI":"10.1073\/pnas.0404383101","article-title":"Approximate protein structural alignment in polynomial time","volume":"101","author":"Kolodny","year":"2004","journal-title":"Proc. Natl Acad. Sci. USA"},{"key":"2023012508213165300_B19","doi-asserted-by":"crossref","first-page":"1059","DOI":"10.1093\/protein\/7.9.1059","article-title":"The protein threading problem with sequence amino acid interaction preferences is NP-complete","volume":"7","author":"Lathrop","year":"1994","journal-title":"Protein Eng"},{"key":"2023012508213165300_B20","first-page":"106","article-title":"Maximum cliques in protein structure comparison","volume-title":"Proceedings of the 9th International Symposium on Experimental Algorithms (SEA'10)","author":"Malod-Dognin","year":"2010"},{"key":"2023012508213165300_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":"2023012508213165300_B22","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":"2023012508213165300_B23","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"},{"key":"2023012508213165300_B24","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1006\/jmbi.2000.4042","article-title":"T-Coffee: a novel method for fast and accurate multiple sequence alignment","volume":"302","author":"Notredame","year":"2000","journal-title":"J. Mol. Biol"},{"key":"2023012508213165300_B25","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":"2023012508213165300_B26","doi-asserted-by":"crossref","first-page":"1605","DOI":"10.1002\/jcc.20084","article-title":"UCSF Chimera\u2014a visualization system for exploratory research and analysis","volume":"25","author":"Pettersen","year":"2004","journal-title":"J. Comput. Chem"},{"key":"2023012508213165300_B27","doi-asserted-by":"crossref","first-page":"3204","DOI":"10.1093\/emboj\/18.12.3204","article-title":"Molecular basis of glutathione synthetase deficiency and a rare gene permutation event","volume":"18","author":"Polekhina","year":"1999","journal-title":"EMBO J"},{"key":"2023012508213165300_B28","doi-asserted-by":"crossref","first-page":"2751","DOI":"10.1093\/bioinformatics\/btp530","article-title":"Algorithms for optimal protein structure alignment","volume":"25","author":"Poleksic","year":"2009","journal-title":"Bioinformatics"},{"key":"2023012508213165300_B29","doi-asserted-by":"crossref","first-page":"1625","DOI":"10.1093\/bioinformatics\/btp296","article-title":"Flexible structural protein alignment by a sequence of local transformations","volume":"25","author":"Rocha","year":"2009","journal-title":"Bioinformatics"},{"key":"2023012508213165300_B30","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":"2023012508213165300_B31","first-page":"2103","article-title":"D\u00e9j\u00e0 vu all over again: finding and analyzing protein structure similarities","volume":"12","author":"Sierk","year":"2004","journal-title":"Structure"},{"key":"2023012508213165300_B32","doi-asserted-by":"crossref","first-page":"116","DOI":"10.1186\/1471-2105-8-116","article-title":"ASH structure alignment package: sensitivity and selectivity in domain classification","volume":"8","author":"Standley","year":"2007","journal-title":"BMC Bioinformatics"},{"key":"2023012508213165300_B33","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":"2023012508213165300_B34","doi-asserted-by":"crossref","first-page":"141","DOI":"10.1016\/0960-9822(93)90255-M","article-title":"Structural similarity of DNA-binding domains of bacteriophage repressors and the globin core","volume":"3","author":"Subbiah","year":"1993","journal-title":"Curr. Biol"},{"key":"2023012508213165300_B35","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0022-2836(89)90084-3","article-title":"Protein structure alignment","volume":"208","author":"Taylor","year":"1989","journal-title":"J. Mol. Biol"},{"key":"2023012508213165300_B36","first-page":"33","article-title":"Aligning protein structures using distance matrices and combinatorial optimization","volume-title":"Proceedings of the German Conference on Bioinformatics (GCB '09)","author":"Wohlers","year":"2009"},{"key":"2023012508213165300_B37","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":"2023012508213165300_B38","doi-asserted-by":"crossref","first-page":"42","DOI":"10.1016\/j.cbpa.2003.12.003","article-title":"Structural proteomics: a tool for genome annotation","volume":"8","author":"Yakunin","year":"2004","journal-title":"Curr. Opin. Chem. Biol"},{"issue":"Suppl. 2","key":"2023012508213165300_B39","doi-asserted-by":"crossref","first-page":"246","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":"2023012508213165300_B40","doi-asserted-by":"crossref","first-page":"3370","DOI":"10.1093\/nar\/gkg571","article-title":"LGA: a method for finding 3D similarities in protein structures","volume":"31","author":"Zemla","year":"2003","journal-title":"Nucleic Acids Res"},{"key":"2023012508213165300_B41","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\/26\/18\/2273\/48857011\/bioinformatics_26_18_2273.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/26\/18\/2273\/48857011\/bioinformatics_26_18_2273.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,6,2]],"date-time":"2023-06-02T05:15:56Z","timestamp":1685682956000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/26\/18\/2273\/208531"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,7,17]]},"references-count":41,"journal-issue":{"issue":"18","published-print":{"date-parts":[[2010,9,15]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btq420","relation":{},"ISSN":["1367-4811","1367-4803"],"issn-type":[{"type":"electronic","value":"1367-4811"},{"type":"print","value":"1367-4803"}],"subject":[],"published-other":{"date-parts":[[2010,9,15]]},"published":{"date-parts":[[2010,7,17]]}}}