The URMS-RMS hybrid algorithm for fast and sensitive local protein structure alignment
We present an efficient and sensitive hybrid algorithm for local structure alignment of a pair of 3D protein structures. The hybrid algorithm employs both the URMS (Unit-vector Root Mean Squared) metric and the RMS metric. Initial transformations (rotations) are identified using the algorithm. These rotations are then clustered and an RMS based dynamic programming algorithm is invoked to find the maximal local similarities for representative rotations of the clusters. Our algorithm searches efficiently the transformation space using a fast screening protocol. Given the transformation based parameters, the algorithm rigorously finds the optimal alignments. Statistical significance of the alignments is estimated using a model that accounts for both the score of the match and the RMS. We tested our algorithm over the SCOP classification of protein domains. Our algorithm performs very well, its main advantages being (1) it combines the RMS and the URMS metrics (2) it searches extensively the transformation space (3) it can detect complex similarities and structural repeats (4) it is symmetric.