Automated methods for protein three-dimensional structure comparison play an important
role in understanding protein function, evolution and biochemical reaction mechanisms. Since the
tertiary structure of proteins is more conserved than their amino-acid sequences, accurately aligning
three-dimensional structures allows to detect homology between proteins in the “twilight zone”, those
sharing less than ~25% sequence identity. Unfortunately, existing methods for protein structure
comparison are often unable to properly compare and align proteins related by complex structural
modifications, such as circular permutations, large conformational changes and large residue insertions
and deletions. In this paper, we present an algorithm capable of computing biologically meaningful alignments from
structurally homologous but spatially distant fragments. Accurate alignments of proteins that have undergone large
conformational variations are derived from multiple spatial superpositions. For mild to moderate conformational
variations, approximate rigid body superpositions are recursively relaxed to allow matching of spatially distant regions.
The algorithm incorporates an exact procedure for computing alignments of proteins related by circular permutations. We
used two benchmarking datasets to demonstrate that our algorithm compares favorably to some of the most accurate
methods available today. In the most difficult RIPC test set, the median accuracy of our method is 100%. The algorithm is
freely available as a Web service at http://bioinfo.cs.uni.edu.