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. P. Chew and K. Kedem, "Finding the Consensus Shape for a Protein Family," Algorithmica, vol. 38, no. 1, pp. 115-129, 2003.
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. J. Ebert and D. Brutlag, "Development and Validation of a Consistency Based Multiple Structure Alignment Algorithm," Bioinformatics, vol. 22, no. 9, pp. 1080-1087, 2006.
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. D. Lupyan, A. Leo-Macias, and A. R. Ortiz, "A New Progressive-Iterative Algorithm for Multiple Structure Alignment," Bioinformatics , vol. 21, no. 15, pp. 3255-3263, 2005.
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. Y. Ye and A. Godzik, "Multiple Flexible Structure Alignment Using Partial Order Graphs," Bioinformatics, vol. 21, no. 10, pp. 2362-2369, 2005.

Index Terms

• Applied computing

  • Life and medical sciences

    • Computational biology

    • Genetics

    • Systems biology

• Computing methodologies

  • Artificial intelligence

    • Search methodologies

      • Heuristic function construction

  • Machine learning

  • Modeling and simulation

    • Model development and analysis

      • Model verification and validation

• Theory of computation

  • Design and analysis of algorithms

    • Approximation algorithms analysis

      • Scheduling algorithms

    • Online algorithms

      • Online learning algorithms

        • Scheduling algorithms

  • Theory and algorithms for application domains

    • Machine learning theory

      • Reinforcement learning

        • Sequential decision making