MINRMS: an efficient algorithm for determining protein structure similarity using root-mean-squared-distance.
BACKGROUND
Existing algorithms for automated protein structure alignment generate contradictory results and are difficult to interpret. An algorithm which can provide a context for interpreting the alignment and uses a simple method to characterize protein structure similarity is needed.


RESULTS
We describe a heuristic for limiting the search space for structure alignment comparisons between two proteins, and an algorithm for finding minimal root-mean-squared-distance (RMSD) alignments as a function of the number of matching residue pairs within this limited search space. Our alignment algorithm uses coordinates of alpha-carbon atoms to represent each amino acid residue and requires a total computation time of O(m(3) n(2)), where m and n denote the lengths of the protein sequences. This makes our method fast enough for comparisons of moderate-size proteins (fewer than approximately 800 residues) on current workstation-class computers and therefore addresses the need for a systematic analysis of multiple plausible shape similarities between two proteins using a widely accepted comparison metric.
Jewett
Andrew I
AI
Computer Graphics Laboratory, Department of Pharmaceutical Chemistry, University of California at San Fransisco, San Fransisco, CA 94143-0446, USA.
Huang
Conrad C
CC
Ferrin
Thomas E
TE
D000465:Algorithms; D000595:Amino Acid Sequence; D016014:Linear Models; D008969:Molecular Sequence Data; D009113:Muramidase / Q000737:chemistry; D011487:Protein Conformation; D011506:Proteins / Q000737:chemistry* / Q000235:genetics; D011786:Quality Control; D016415:Sequence Alignment / Q000379:methods*; D020539:Sequence Analysis, Protein / Q000379:methods*
D011506:Proteins; D009113:Muramidase