Defining and Computing Optimum RMSD for Gapped and Weighted Multiple-Structure Alignment

ABSTRACT

Pairwise structure alignment commonly uses root mean square deviation (RMSD) to measure the structural similarity, and methods for optimizing RMSD are well established. We extend RMSD to weighted RMSD for multiple structures. By using multiplicative weights, we show that weighted RMSD for all pairs is the same as weighted RMSD to an average of the structures. Thus, using RMSD or weighted RMSD implies that the average is a consensus structure. Although we show that in general, the two tasks of finding the optimal translations and rotations for minimizing weighted RMSD cannot be separated for multiple structures like they can for pairs, an inherent difficulty and a fact ignored by previous work, we develop a near-linear iterative algorithm to converge weighted RMSD to a local minimum. 10,000 experiments of gapped alignment done on each of 23 protein families from HOMSTRAD (where each structure starts with a random translation and rotation) converge rapidly to the same minimum. Finally we propose a heuristic method to iteratively remove the effect of outliers and find well-aligned positions that determine the structural conserved region by modeling B-factors and deviations from the average positions as weights and iteratively assigning higher weights to better aligned atoms.

REFERENCES

• 1: R. B. Altman and M. Gerstein, "Finding an Average Core Structure: Application to the Globins," Proc. Second Int'l Conf. Intelligent Systems for Molecular Biology, pp. 19-27, 1994.
• 2: C. Branden and J. Tooze, Introduction to Protein Structure, second ed. Garland Science, 1999.
• 3: L. Paul Chew , Klara Kedem, Finding the Consensus Shape for a Protein Family, Algorithmica, v.38 n.1, p.115-129, October 2003 [doi>10.1007/s00453-003-1045-2]
• 4: O. Dror, H. Benyamini, R. Nussinov, and H. J. Wolfson, "Multiple Structural Alignment by Secondary Structures: Algorithm and Applications," Protein Science, vol. 12, no. 11, pp. 2492-2507, 2003.
• 5: Jessica Ebert , Douglas Brutlag, Development and validation of a consistency based multiple structure alignment algorithm, Bioinformatics, v.22 n.9, p.1080-1087, May 2006 [doi>10.1093/bioinformatics/btl046]
• 6: M. Gerstein and M. Levitt, "Comprehensive Assessment of Automatic Structural Alignment against a Manual Standard, the SCOP Classification of Proteins," Protein Science, vol. 7, no. 2, pp. 445-456, 1998.
• 7: C. Guda, E. D. Scheeff, P. E. Bourne, and I. N. Shindyalov, "A New Algorithm for the Alignment of Multiple Protein Structures Using Monte Carlo Optimization," Proc. Sixth Pacific Symp. Biocomputing (PSB '01), pp. 275-286, 2001.
• 8: B. K. P. Horn, "Closed-Form Solution of Absolute Orientation Using Unit Quaternions," J. Optical Soc. of Am. A, vol. 4, no. 4, pp. 629-642, 1987.
• 9: A. S. Konagurthu, J. C. Whisstock, P. J. Stuckey, and A. M. Lesk, "MUSTANG: A Multiple Structural Alignment Algorithm," Proteins, vol. 64, no. 3, pp. 559-574, 2006.
• 10: N. Leibowitz, R. Nussinov, and H. J. Wolfson, "MUSTA--A General, Efficient, Automated Method for Multiple Structure Alignment and Detection of Common Motifs: Application to Proteins," J. Computational Biology, vol. 8, no. 2, pp. 93-121, 2001.
• 11: Dmitry Lupyan , Alejandra Leo-Macias , Angel R. Ortiz, A new progressive-iterative algorithm for multiple structure alignment, Bioinformatics, v.21 n.15, p.3255-3263, August 2005 [doi>10.1093/bioinformatics/bti527]
• 12: R. Maiti, G. H. V. Domselaar, H. Zhang, and D.S. Wishart, "Super-Pose: A Simple Server for Sophisticated Structural Superposition," Nucleic Acids Research, vol. 32, pp. W590-W594, 2004.
• 13: K. Mizuguchi, C. M. Deane, T. L. Blundell, and J. P. Overington, "HOMSTRAD: A Database of Protein Structure Alignments for Homologous Families," Protein Science, vol. 7, no. 11, pp. 2469-2471, 1998.
• 14: M. E. Ochagavia and S. Wodak, "Progressive Combinatorial Algorithm for Multiple Structural Alignments: Application to Distantly Related Proteins," Proteins, vol. 55, no. 2, pp. 436-454, 2004.
• 15: X. Pennec, "Multiple Registration and Mean Rigid Shapes: Application to the 3D Case," Proc. 16th Leeds Ann. Statistical Research Workshop (LASR '96), pp. 178-185, 1996.
• 16: R. B. Russell and G. J. Barton, "Multiple Protein Sequence Alignment from Tertiary Structure Comparison: Assignment of Global and Residue Confidence Levels," Proteins, vol. 14, no. 2, pp. 309-323, 1992.
• 17: M. Shatsky, R. Nussinov, and H. J. Wolfson, "A Method for Simultaneous Alignment of Multiple Protein Structures," Proteins, vol. 56, no. 1, pp. 143-156, 2004.
• 18: M. J. Sutcliffe, I. Haneef, D. Carney, and T. L. Blundell, "Knowledge Based Modelling of Homologous Proteins, Part I: Three-Dimensional Frameworks Derived from the Simultaneous Superposition of Multiple Structures," Protein Eng., vol. 1, no. 5, pp. 377-384, 1987.
• 19: W. R. Taylor, T. P. Flores, and C. A. Orengo, "Multiple Protein Structure Alignment," Protein Science, vol. 3, no. 10, pp. 1858-1870, 1994.
• 20: P. Verboon and K. R. Gabriel, "Generalized Procrustes Analysis with Iterative Weighting to Achieve Resistance," British J. Math. and Statistical Psychology, vol. 48, no. 1, pp. 57-73, 1995.
• 21: Yuzhen Ye , Adam Godzik, Multiple flexible structure alignment using partial order graphs, Bioinformatics, v.21 n.10, p.2362-2369, May 2005 [doi>10.1093/bioinformatics/bti353]

INDEX TERMS

Primary Classification:
  J. Computer Applications
  J.3 LIFE AND MEDICAL SCIENCES
      Subjects: Biology and genetics

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sequencing and scheduling

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Heuristic methods
  I.5 PATTERN RECOGNITION
      I.5.1 Models
          Subjects: Structural
      I.5.2 Design Methodology
          Subjects: Pattern analysis
  I.6 SIMULATION AND MODELING
      I.6.4 Model Validation and Analysis

General Terms:
Algorithms, Design, Performance, Theory

Keywords:
optimization methods, multiple structure alignment, weighted RMSD, structural conserved region