Alignment of Flexible Protein Structures

Proceedings of the Twentieth International Conference on Machine Learning, 2000

Volume

Proceedings of the Twentieth International Conference on Machine Learning, 2000

Contents

We present two algorithms which align exible protein structures. Both apply efficient structural pattern detection and graph theoretic techniques. The FlexProt algorithm simultaneously detects the hinge regions and aligns the rigid subparts of the molecules. It does it by efficiently detecting maximal congruent rigid fragments in both molecules and calculating their optimal arrangement which does not violate the protein sequence order. The FlexMol algorithm is sequence order independent, yet requires as input the hypothesized hinge positions. Due its sequence order independence it can also be applied to protein-protein interface matching and drug molecule alignment. It aligns the rigid parts of the molecule using the Geometric Hashing method and calculates optimal connectivity among these parts by graphtheoretic techniques. Both algorithms are highly efficient even compared with rigid structure alignment algorithms. Typical running times on a standard desktop PC (400MHz) are about 7 seconds for FlexProt and about 1 minute for FlexMol.