MINRMS: An Efficient Algorithm for Determining Protein Structure Similarity Using Root-Mean Squared-Distance

A.I. Jewett, C.C. Huang, and T.E. Ferrin
Computer Graphics Laboratory
University of California
San Francisco, CA 94143-0446

ABSTRACT

Motivation:

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 ~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.

Reprint Availability:

The full-text version of this paper is available on-line.

Additional Information:

See http://www.cgl.ucsf.edu/Research/minrms.

tef@cgl.ucsf.edu / March 2003