CMU-CS-03-181Computer Science Department School of Computer Science, Carnegie Mellon University
CMU-CS-03-181
Michael A. Erdmann September 2003
CMU-CS-03-181.ps
Keywords: Protein structure, homology, homotopy, writhing, knot
theory, robot motion planning
Shape similarity can be formulated (i) in terms of global metrics, such as RMSD or Hausdorff distance, (ii) in terms of subgraph isomorphisms, such as the detection of shared substructures with similar relative locations, or (iii) purely topologically, in terms of the cohomology of structure-preserving transformations. Existing protein structure detection programs are built on the first two types of similarity. The third forms the foundations of knot theory. The thesis of this paper is: Protein similarity detection leads naturally to an algorithm operating at the metric, relational, and homotopic scales. The paper introduces a definition of similarity based on atomic motions that preserve local backbone topology without incurring significant distance errors. Such motions are motivated by the physical requirements for rearranging subsequences of a protein. Similarity detection then seeks rigid body motions able to overlay pairs of substructures, each related by a substructure-preserving motion, without necessarily requiring global structure preservation. This definition is general enough to span a wide range of questions: One can ask for full rearrangement of one protein into another while preserving global topology, as in drug design; or one can ask for rearrangements of sets of smaller substructures, each of which preserves local but not global topology, as in protein evolution.
In the appendix, we exhibit an algorithm for answering the general
question. That algorithm has the complexity of robot motion planning.
In the text, we consider a more common case in which one seeks protein
similarity by rearrangements of relatively short peptide segments. We
exhibit an algorithm based on writhing numbers that runs in
27 pages
| |

Return to:
SCS Technical Report Collection This page maintained by reports@cs.cmu.edu |