FlexProt: alignment of flexible protein structures without a predefinition of hinge regions

FlexProt is a novel technique for the alignment of flexible proteins. Unlike all previous algorithms designed to solve the problem of structural comparisons allowing hinge-bending motions, FlexProt does not require an a priori knowledge of the location of the hinge(s). FlexProt carries out the flexible alignment, superimposing the matching rigid subpart pairs, and detects the flexible hinge regions simultaneously. A large number of methods are available to handle rigid structural alignment. However, proteins are flexible molecules, which may appear in different conformations. Hence, protein structural analysis requires algorithms that can deal with molecular flexibility. Here, we present a method addressing specifically a flexible protein alignment task. First, the method efficiently detects maximal congruent rigid fragments in both molecules. Transforming the task into a graph theoretic problem, our method proceeds to calculate the optimal arrangement of previously detected maximal congruent rigid fragments. The fragment arrangement does not violate the protein sequence order. A clustering procedure is performed on fragment-pairs which have the same 3-D rigid transformation regardless of insertions and deletions (such as loops and turns) which separate them. Although the theoretical worst case complexity of the algorithm is O(n(6)), in practice FlexProt is highly efficient. It performs a structural comparison of a pair of proteins 300 amino acids long in about seven seconds on a standard desktop PC (400 MHz Pentium II processor with 256MB internal memory). We have performed extensive experiments with the algorithm. An assortment of these results is presented here. FlexProt can be accessed via WWW at bioinfo3d.cs.tau.ac.il/FlexProt/.