{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,19]],"date-time":"2025-03-19T10:31:12Z","timestamp":1742380272368},"reference-count":40,"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>\n               <jats:p>Motivation: Searching for structural similarity is a key issue of protein functional annotation. The maximum contact map overlap (CMO) is one of the possible measures of protein structure similarity. Exact and approximate methods known to optimize the CMO are computationally expensive and this hampers their applicability to large-scale comparison of protein structures.<\/jats:p>\n               <jats:p>Results: In this article, we describe a heuristic algorithm (Al-Eigen) for finding a solution to the CMO problem. Our approach relies on the approximation of contact maps by eigendecomposition. We obtain good overlaps of two contact maps by computing the optimal global alignment of few principal eigenvectors. Our algorithm is simple, fast and its running time is independent of the amount of contacts in the map. Experimental testing indicates that the algorithm is comparable to exact CMO methods in terms of the overlap quality, to structural alignment methods in terms of structure similarity detection and it is fast enough to be suited for large-scale comparison of protein structures. Furthermore, our preliminary tests indicates that it is quite robust to noise, which makes it suitable for structural similarity detection also for noisy and incomplete contact maps.<\/jats:p>\n               <jats:p>Availability: Available at http:\/\/bioinformatics.cs.unibo.it\/Al-Eigen<\/jats:p>\n               <jats:p>Contact: \u00a0dilena@cs.unibo.it<\/jats:p>\n               <jats:p>Supplementary information: \u00a0Supplementary data are available at Bioinformatics online.<\/jats:p>","DOI":"10.1093\/bioinformatics\/btq402","type":"journal-article","created":{"date-parts":[[2010,7,8]],"date-time":"2010-07-08T02:50:45Z","timestamp":1278557445000},"page":"2250-2258","source":"Crossref","is-referenced-by-count":34,"title":["Fast overlapping of protein contact maps by alignment of eigenvectors"],"prefix":"10.1093","volume":"26","author":[{"given":"Pietro","family":"Di Lena","sequence":"first","affiliation":[{"name":"1 Department of Computer Science, University of Bologna, Mura Anteo Zamboni 7 and 2Biocomputing Group, University of Bologna, Via S.Giacomo 9\/2, 40127 Bologna, Italy"}]},{"given":"Piero","family":"Fariselli","sequence":"additional","affiliation":[{"name":"1 Department of Computer Science, University of Bologna, Mura Anteo Zamboni 7 and 2Biocomputing Group, University of Bologna, Via S.Giacomo 9\/2, 40127 Bologna, Italy"}]},{"given":"Luciano","family":"Margara","sequence":"additional","affiliation":[{"name":"1 Department of Computer Science, University of Bologna, Mura Anteo Zamboni 7 and 2Biocomputing Group, University of Bologna, Via S.Giacomo 9\/2, 40127 Bologna, Italy"}]},{"given":"Marco","family":"Vassura","sequence":"additional","affiliation":[{"name":"1 Department of Computer Science, University of Bologna, Mura Anteo Zamboni 7 and 2Biocomputing Group, University of Bologna, Via S.Giacomo 9\/2, 40127 Bologna, Italy"}]},{"given":"Rita","family":"Casadio","sequence":"additional","affiliation":[{"name":"1 Department of Computer Science, University of Bologna, Mura Anteo Zamboni 7 and 2Biocomputing Group, University of Bologna, Via S.Giacomo 9\/2, 40127 Bologna, Italy"}]}],"member":"286","published-online":{"date-parts":[[2010,7,7]]},"reference":[{"key":"2023012508235541100_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":"2023012508235541100_B2","doi-asserted-by":"crossref","first-page":"3389","DOI":"10.1093\/nar\/25.17.3389","article-title":"Gapped BLAST and PSI-BLAST: a new generation of protein database search programs","volume":"25","author":"Altschul","year":"1997","journal-title":"Nucleic Acids Res"},{"key":"2023012508235541100_B3","first-page":"162","article-title":"An efficient Lagrangian relaxation for the contact map overlap problem","volume":"5251","author":"Andonov","year":"2008","journal-title":"Lect. Notes Bioinform"},{"key":"2023012508235541100_B4","doi-asserted-by":"crossref","first-page":"419","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":"2023012508235541100_B5","doi-asserted-by":"crossref","first-page":"425","DOI":"10.1109\/TCOM.1976.1093309","article-title":"Singular value decomposition (SVD) image coding","volume":"24","author":"Andrews","year":"1976","journal-title":"IEEE Trans. Commun"},{"key":"2023012508235541100_B6","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1088\/1478-3975\/4\/4\/L01","article-title":"The effect of backbone on the small-world properties of protein contact maps","volume":"4","author":"Bartoli","year":"2007","journal-title":"Phys. Biol"},{"key":"2023012508235541100_B7","first-page":"100","article-title":"Structural alignment of large-size proteins via Lagrangian relaxation","volume-title":"Proceedings of the Annual International Conference on Computational Molecular Biology (RECOMB 2002)","author":"Caprara","year":"2002"},{"key":"2023012508235541100_B8","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":"2023012508235541100_B9","doi-asserted-by":"crossref","first-page":"283","DOI":"10.1186\/1471-2105-11-283","article-title":"Optimal contact definition for reconstruction of contact maps","volume":"11","author":"Duarte","year":"2010","journal-title":"BMC Bioinformatics"},{"key":"2023012508235541100_B10","doi-asserted-by":"crossref","first-page":"96","DOI":"10.1002\/prot.22554","article-title":"Assessment of domain boundary predictions and the prediction of intramolecular contacts in CASP8","volume":"77","author":"Ezkurdia","year":"2009","journal-title":"Proteins"},{"key":"2023012508235541100_B11","first-page":"300","article-title":"Assessing the performance of fold recognition methods by means of a comprehensive benchmark","volume-title":"Proceedings of the Pacific Symposium on Biocomputing 1996","author":"Fischer","year":"1996"},{"key":"2023012508235541100_B12","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":"2023012508235541100_B13","doi-asserted-by":"crossref","first-page":"227","DOI":"10.1016\/0022-2836(92)90693-E","article-title":"Topology fingerprint approach to the inverse protein folding problem","volume":"227","author":"Godzik","year":"1992","journal-title":"J. Mol. Biol"},{"key":"2023012508235541100_B14","first-page":"512","article-title":"Algorithmic aspects of protein structure similarity","volume-title":"Proceedings of the 40th Annual Symposium on Foundations of Computer Science","author":"Goldman","year":"1999"},{"key":"2023012508235541100_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":"2023012508235541100_B16","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":"2023012508235541100_B17","first-page":"410","article-title":"Joining softassign and dynamic programming for the contact map overlap problem","volume":"4414","author":"Jain","year":"2007","journal-title":"Lect. Notes Bioinform"},{"key":"2023012508235541100_B18","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","author":"Jain","year":"2009"},{"key":"2023012508235541100_B19","doi-asserted-by":"crossref","first-page":"922","DOI":"10.1107\/S0567739476001873","article-title":"A solution for the best rotation to relate two sets of vectors","volume":"32","author":"Kabsch","year":"1976","journal-title":"Acta Cryst"},{"key":"2023012508235541100_B20","doi-asserted-by":"crossref","first-page":"1015","DOI":"10.1093\/bioinformatics\/bth031","article-title":"Measuring the similarity of protein structures by means of the universal similarity metric","volume":"20","author":"Krasnogor","year":"2004","journal-title":"Bioinformatics"},{"key":"2023012508235541100_B21","first-page":"193","article-title":"101 Optimal PDB structure alignments: a branch-and-cut algorithm for the maximum contact map overlap problem","volume-title":"Proceedings of the Annual International Conference on Computational Molecular Biology, RECOMB 2001","author":"Lancia","year":"2001"},{"key":"2023012508235541100_B22","doi-asserted-by":"crossref","first-page":"1120","DOI":"10.1109\/34.954602","article-title":"Structural graph matching using the EM algorithm and singular value decomposition","volume":"23","author":"Luo","year":"2001","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell"},{"key":"2023012508235541100_B23","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":"2023012508235541100_B24","doi-asserted-by":"crossref","first-page":"260","DOI":"10.2174\/138920308784534032","article-title":"Search strategies in structural bioinformatics","volume":"9","author":"Oakley","year":"2008","journal-title":"Curr. Protein Pept. Sci"},{"key":"2023012508235541100_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":"2023012508235541100_B26","doi-asserted-by":"crossref","first-page":"218101","DOI":"10.1103\/PhysRevLett.92.218101","article-title":"Reconstruction of protein structures from a vectorial representation","volume":"92","author":"Porto","year":"2004","journal-title":"Phys. Rev. Lett"},{"key":"2023012508235541100_B27","doi-asserted-by":"crossref","first-page":"149","DOI":"10.1504\/IJCBDD.2009.028821","article-title":"Comparing protein contact maps via Universal Similarity Metric: an improvement in the noise-tolerance","volume":"2","author":"Rahmati","year":"2009","journal-title":"Int. J. Comput. Biol. Drug Des"},{"key":"2023012508235541100_B28","doi-asserted-by":"crossref","first-page":"104","DOI":"10.1007\/3-540-70659-3_10","article-title":"String edit distance, random walks and graph matching","volume":"2396","author":"Robles-Kelly","year":"2002","journal-title":"Lect. Notes Comput. Sci"},{"key":"2023012508235541100_B29","doi-asserted-by":"crossref","first-page":"321","DOI":"10.1016\/j.sbi.2009.04.009","article-title":"Discrete-continuous duality of protein structure space","volume":"19","author":"Sadreyev","year":"2009","journal-title":"Curr. Opin. Struct. Biol"},{"key":"2023012508235541100_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":"2023012508235541100_B31","doi-asserted-by":"crossref","first-page":"16","DOI":"10.1007\/978-3-540-71681-5_2","article-title":"Pairwise global alignment of protein interaction networks by matching neighborhood topology","volume":"4453","author":"Singh","year":"2007","journal-title":"Lect. Notes Comput. Sci"},{"key":"2023012508235541100_B32","volume-title":"Introduction to Linear Algebra","author":"Strang","year":"2003"},{"key":"2023012508235541100_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":"2023012508235541100_B34","doi-asserted-by":"crossref","first-page":"695","DOI":"10.1109\/34.6778","article-title":"Eigendecomposition approach to weighted graph matching problems","volume":"10","author":"Umeyama","year":"1988","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell"},{"key":"2023012508235541100_B35","doi-asserted-by":"crossref","first-page":"357","DOI":"10.1109\/TCBB.2008.27","article-title":"Reconstruction of 3D structures from protein contact maps","volume":"5","author":"Vassura","year":"2008","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinform"},{"key":"2023012508235541100_B36","doi-asserted-by":"crossref","first-page":"1313","DOI":"10.1093\/bioinformatics\/btn115","article-title":"FT-COMAR: fault tolerant three-dimensional structure reconstruction from protein contact maps","volume":"24","author":"Vassura","year":"2008","journal-title":"Bioinformatics"},{"key":"2023012508235541100_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":"2023012508235541100_B38","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":"2023012508235541100_B39","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":"22","author":"Zhang","year":"2005","journal-title":"Nucleic Acids Res"},{"key":"2023012508235541100_B40","doi-asserted-by":"crossref","first-page":"1283","DOI":"10.1007\/978-3-540-74171-8_131","article-title":"Using eigen-decomposition method for weighted graph matching","volume":"4453","author":"Zhao","year":"2007","journal-title":"Lect. Notes Comput. Sci"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/26\/18\/2250\/48858452\/bioinformatics_26_18_2250.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/26\/18\/2250\/48858452\/bioinformatics_26_18_2250.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,25]],"date-time":"2023-01-25T08:24:23Z","timestamp":1674635063000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/26\/18\/2250\/207560"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,7,7]]},"references-count":40,"journal-issue":{"issue":"18","published-print":{"date-parts":[[2010,9,15]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btq402","relation":{},"ISSN":["1367-4811","1367-4803"],"issn-type":[{"value":"1367-4811","type":"electronic"},{"value":"1367-4803","type":"print"}],"subject":[],"published-other":{"date-parts":[[2010,9,15]]},"published":{"date-parts":[[2010,7,7]]}}}