{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,30]],"date-time":"2026-03-30T17:59:48Z","timestamp":1774893588234,"version":"3.50.1"},"reference-count":35,"publisher":"Oxford University Press (OUP)","issue":"21","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2009,11,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>Motivation: Structural alignment is an important tool for understanding the evolutionary relationships between proteins. However, finding the best pairwise structural alignment is difficult, due to the infinite number of possible superpositions of two structures. Unlike the sequence alignment problem, which has a polynomial time solution, the structural alignment problem has not been even classified as solvable.<\/jats:p>\n               <jats:p>Results: We study one of the most widely used measures of protein structural similarity, defined as the number of pairs of residues in two proteins that can be superimposed under a predefined distance cutoff. We prove that, for any two proteins, this measure can be optimized for all but finitely many distance cutoffs. Our method leads to a series of algorithms for optimizing other structure similarity measures, including the measures commonly used in protein structure prediction experiments. We also present a polynomial time algorithm for finding a near-optimal superposition of two proteins. Aside from having a relatively low cost, the algorithm for near-optimal solution returns a superposition of provable quality. In other words, the difference between the score of the returned superposition and the score of an optimal superposition can be explicitly computed and used to determine whether the returned superposition is, in fact, the best superposition.<\/jats:p>\n               <jats:p>Contact: \u00a0poleksic@cs.uni.edu<\/jats:p>\n               <jats:p>Supplementary information: \u00a0Supplementary data are available at Bioinformatics online.<\/jats:p>","DOI":"10.1093\/bioinformatics\/btp530","type":"journal-article","created":{"date-parts":[[2009,9,5]],"date-time":"2009-09-05T00:14:25Z","timestamp":1252109665000},"page":"2751-2756","source":"Crossref","is-referenced-by-count":24,"title":["Algorithms for optimal protein structure alignment"],"prefix":"10.1093","volume":"25","author":[{"given":"Aleksandar","family":"Poleksic","sequence":"first","affiliation":[{"name":"Department of Computer Science, University of Northern Iowa, Cedar Falls, IA 50614, USA"}]}],"member":"286","published-online":{"date-parts":[[2009,9,4]]},"reference":[{"key":"2023013112193180900_B1","doi-asserted-by":"crossref","first-page":"D253","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":"2023013112193180900_B2","doi-asserted-by":"crossref","first-page":"5","DOI":"10.1016\/0022-2836(92)91021-G","article-title":"Common spatial arrangements of backbone fragments in homologous and nonhomologous proteins","volume":"225","author":"Alexandrov","year":"1992","journal-title":"J. Mol. Biol."},{"key":"2023013112193180900_B3","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1089\/106652704773416876","article-title":"1001 optimal PDB structure alignments: integer programming methods for finding the maximumcontact map overlap","volume":"11","author":"Caprara","year":"2004","journal-title":"J. Comput. Biol."},{"key":"2023013112193180900_B4","doi-asserted-by":"crossref","first-page":"i98","DOI":"10.1093\/bioinformatics\/btn271","article-title":"Protein structure alignment considering phenotypic plasticity","volume":"24","author":"Csaba","year":"2008","journal-title":"Bioinformatics"},{"key":"2023013112193180900_B5","doi-asserted-by":"crossref","first-page":"685","DOI":"10.1089\/106652701446152","article-title":"Structure comparison and structure patterns","volume":"7","author":"Eidhammer","year":"2000","journal-title":"J. Comput. Biol."},{"issue":"Suppl. 6","key":"2023013112193180900_B6","doi-asserted-by":"crossref","first-page":"503","DOI":"10.1002\/prot.10538","article-title":"CAFASP3: the third critical assessment of fully automated structure prediction methods","volume":"53","author":"Fischer","year":"2003","journal-title":"Proteins"},{"key":"2023013112193180900_B7","doi-asserted-by":"crossref","first-page":"1874","DOI":"10.1093\/nar\/gki327","article-title":"Practical lessons from protein structure prediction","volume":"33","author":"Ginalski","year":"2005","journal-title":"Nucleic Acids Res."},{"key":"2023013112193180900_B8","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":"2023013112193180900_B9","doi-asserted-by":"crossref","first-page":"1813","DOI":"10.1110\/ps.0242903","article-title":"Structural genomics: computational methods for structure analysis","volume":"12","author":"Goldsmith-Fischman","year":"2003","journal-title":"Prot. Sci."},{"key":"2023013112193180900_B10","doi-asserted-by":"crossref","first-page":"10915","DOI":"10.1073\/pnas.89.22.10915","article-title":"Amino acid substitution matrices from protein blocks","volume":"89","author":"Henikoff","year":"1992","journal-title":"Proc. Natl Acad. Sci. USA"},{"key":"2023013112193180900_B11","doi-asserted-by":"crossref","first-page":"6614","DOI":"10.1073\/pnas.89.14.6614","article-title":"Effects of compact volume and chain stiffness on the conformations of native proteins","volume":"89","author":"Hao","year":"1992","journal-title":"Proc. Natl Acad. Sci. USA"},{"key":"2023013112193180900_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":"2023013112193180900_B13","doi-asserted-by":"crossref","first-page":"922","DOI":"10.1107\/S0567739476001873","article-title":"solution for the best rotation to relate two sets of vectors","volume":"32","author":"Kabsch","year":"1976","journal-title":"Acta Crystallographica"},{"key":"2023013112193180900_B14","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":"2003","journal-title":"Proc. Natl Acad. Sci. USA"},{"key":"2023013112193180900_B15","doi-asserted-by":"crossref","first-page":"559","DOI":"10.1002\/prot.20921","article-title":"MUSTANG: multiple structural alignment algorithm","volume":"64","author":"Konagurthu","year":"2006","journal-title":"Proteins"},{"key":"2023013112193180900_B16","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":"2023013112193180900_B17","doi-asserted-by":"crossref","first-page":"88","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 Computat. Biol."},{"key":"2023013112193180900_B18","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1002\/prot.21767","article-title":"Critical assessment of methods of protein structure prediction Round VII","volume":"69","author":"Moult","year":"2007","journal-title":"Proteins"},{"key":"2023013112193180900_B19","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":"2023013112193180900_B20","doi-asserted-by":"crossref","first-page":"514","DOI":"10.1107\/S0907444907000844","article-title":"CAALIGN: a program for pairwise and multiple protein structure alignment","volume":"63","author":"Oldfield","year":"2007","journal-title":"Acta Crystallogr. D Biol. Crystallogr."},{"key":"2023013112193180900_B21","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":"2023013112193180900_B22","doi-asserted-by":"crossref","first-page":"2606","DOI":"10.1110\/ps.0215902","article-title":"MAMMOTH (matching molecular models obtained from theory): an automated method for model comparison","volume":"11","author":"Ortiz","year":"2002","journal-title":"Protein Sci."},{"key":"2023013112193180900_B23","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":"2023013112193180900_B24","doi-asserted-by":"crossref","first-page":"309","DOI":"10.1002\/prot.340140216","article-title":"Multiple protein sequence alignment from tertiary structure comparison: assignment of global and residue confidence levels","volume":"14","author":"Russell","year":"1992","journal-title":"Proteins"},{"key":"2023013112193180900_B25","doi-asserted-by":"crossref","first-page":"779","DOI":"10.1006\/jmbi.1993.1626","article-title":"Comparative protein modeling by satisfaction of spatial restraints","volume":"234","author":"Sali","year":"1993","journal-title":"J. Mol. Biol."},{"key":"2023013112193180900_B26","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":"2023013112193180900_B27","doi-asserted-by":"crossref","first-page":"776","DOI":"10.1093\/bioinformatics\/16.9.776","article-title":"MaxSub: an automated measure for the assessment of protein structure prediction quality","volume":"16","author":"Siew","year":"2000","journal-title":"Bioinformatics"},{"key":"2023013112193180900_B28","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":"2023013112193180900_B29","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":"2023013112193180900_B30","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":"2023013112193180900_B31","doi-asserted-by":"crossref","first-page":"52","DOI":"10.1002\/prot.340110107","article-title":"Detection of common three-dimensional substructures in proteins","volume":"11","author":"Vriend","year":"1991","journal-title":"Proteins"},{"key":"2023013112193180900_B32","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."},{"issue":"Suppl. 2","key":"2023013112193180900_B33","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":"2023013112193180900_B34","doi-asserted-by":"crossref","first-page":"3370","DOI":"10.1093\/nar\/gkg571","article-title":"LGA\u2014a method for finding 3D similarities in protein structures","volume":"31","author":"Zemla","year":"2003","journal-title":"Nucleic Acids Res."},{"key":"2023013112193180900_B35","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\/25\/21\/2751\/48997936\/bioinformatics_25_21_2751.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/25\/21\/2751\/48997936\/bioinformatics_25_21_2751.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,31]],"date-time":"2023-01-31T21:59:05Z","timestamp":1675202345000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/25\/21\/2751\/228079"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,9,4]]},"references-count":35,"journal-issue":{"issue":"21","published-print":{"date-parts":[[2009,11,1]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btp530","relation":{},"ISSN":["1367-4811","1367-4803"],"issn-type":[{"value":"1367-4811","type":"electronic"},{"value":"1367-4803","type":"print"}],"subject":[],"published-other":{"date-parts":[[2009,11,1]]},"published":{"date-parts":[[2009,9,4]]}}}