Algorithms for optimal protein structure alignment Export

@article{citeulike:5730515, abstract = {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. 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. Contact: poleksic@cs.uni.edu Supplementary information: Supplementary data are available at Bioinformatics online. 10.1093/bioinformatics/btp530}, author = {Poleksic, Aleksandar}, citeulike-article-id = {5730515}, citeulike-linkout-0 = {http://dx.doi.org/10.1093/bioinformatics/btp530}, citeulike-linkout-1 = {http://bioinformatics.oxfordjournals.org/content/25/21/2751.abstract}, citeulike-linkout-2 = {http://bioinformatics.oxfordjournals.org/content/25/21/2751.full.pdf}, citeulike-linkout-3 = {http://view.ncbi.nlm.nih.gov/pubmed/19734152}, citeulike-linkout-4 = {http://www.hubmed.org/display.cgi?uids=19734152}, day = {1}, doi = {10.1093/bioinformatics/btp530}, issn = {1460-2059}, journal = {Bioinformatics}, keywords = {structure\_alignment}, month = {November}, number = {21}, pages = {2751--2756}, posted-at = {2009-10-30 00:17:32}, priority = {2}, title = {Algorithms for optimal protein structure alignment}, url = {http://dx.doi.org/10.1093/bioinformatics/btp530}, volume = {25}, year = {2009} }

TY - JOUR ID - citeulike:5730515 L3 - citeulike-article-id:5730515 N2 - 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. 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. Contact: poleksic@cs.uni.edu Supplementary information: Supplementary data are available at Bioinformatics online. 10.1093/bioinformatics/btp530 IS - 21 JF - Bioinformatics SN - 1460-2059 EP - 2756 TI - Algorithms for optimal protein structure alignment VL - 25 SP - 2751 KW - structure_alignment AU - Poleksic, Aleksandar PY - 2009/11/01/ UR - http://dx.doi.org/10.1093/bioinformatics/btp530 ER -