Algorithmic aspects of protein structure similarity
- 20 January 2003
- proceedings article
- Published by Institute of Electrical and Electronics Engineers (IEEE)
Abstract
We show that calculating contact map overlap (a measure of similarity of protein structures) is NP-hard, but can be solved in polynomial time for several interesting and relevant special cases. We identify an important special case of this problem corresponding to self-avoiding walks, and prove a decomposition theorem and a corollary approximation result for this special case. These are the first approximation algorithms with guaranteed error bounds, and NP-completeness results in the literature in the area of protein structure alignment/fold recognition for measures of structure similarity of practical interest.Keywords
This publication has 31 references indexed in Scilit:
- On the Complexity of Protein FoldingJournal of Computational Biology, 1998
- Detection of common three‐dimensional substructures in proteinsProteins-Structure Function and Bioinformatics, 1991
- Database of homology‐derived protein structures and the structural meaning of sequence alignmentProteins-Structure Function and Bioinformatics, 1991
- Protein structure alignmentJournal of Molecular Biology, 1989
- The alignment of protein structures in three dimensionsBulletin of Mathematical Biology, 1989
- A note on the rotational superposition problemActa Crystallographica Section A Foundations of Crystallography, 1988
- Simultaneous Solution of the RNA Folding, Alignment and Protosequence ProblemsSIAM Journal on Applied Mathematics, 1985
- Estimation of effective interresidue contact energies from protein crystal structures: quasi-chemical approximationMacromolecules, 1985
- On the comparison of conformations using linear and quadratic transformationsActa Crystallographica Section A, 1976
- A mathematical procedure for superimposing atomic coordinates of proteinsActa Crystallographica Section A, 1972