Protein3Dfit - The alignment algorithm

The program "Protein3Dfit" detects and evaluates structural similarities in proteins. The method is able to detect geometrical similar substructures between two proteins in an entirely sequence independent way. The theoretical background and the details of the methods were published in Protein Engineering (1994), 7, 1175-1187 entitled "Similarities between protein 3-D structures" by Uta Lessel and Dietmar Schomburg.
At the date of publication the algorithm showed a performance comparable to DALI in detecting structural similarities in the PDB (results are in the paper). Since then the algorithm is integrated in the protein visualization and modeling program BRAGI and works reliable.

Calculating fragment pairs

The detection of of 3D-homologies is based on the use of Calpha distance maps to detect matching fragment pairs between two protein structures. Each fragment of a given minimum length of protein A is compared to each possible fragment of protein B. The required minimum sequence length of such a fragment can be defined by the user. Fragment pairs are required to have a user-definable maximum r.m.s. deviation of the corresponding intramolecular Calpha distances. Detected fragment pairs are elongated to both directions as far as possible without exceeding the defined rms deviation.

Generation of quartets

Following the fragment pair detection the program uses again the off-diagonal distance maps to check the relationships between fragment in space, thereby combining the pairs to fragment quartets consisting of two pairs of matching fragments. To avoid the possible strong influence of similarities it is possible to define the minimum number of residues located between the fragment pairs that may form quartets. Beside saving computer processing time, this parameters allows to favour either local(low parameter value) or global fits. For the definition of the quartets a second (and in may cases higher) maximum rms distance can be defined.

Optimisation of the fit

Based on each detected quartet-fit the program calculates initial reorientation matrices (depending on the number of quartets found this can be a rather large number). Then the programs optimises the superimposition of fragments and quartets by doing several cycles of optimization, in each cycle including all those Calpha-atoms into the calculation of the reorientation matrix that are within a user-defined intermolecular distance. The optimisation is finished when the number of Calpha atoms does not change any more between two consecutive cycles.

Calculating percentage of similarity

Finally the largest number of matching Calpha atoms is selected from the optimisation runs and the percentages fitting Calpha atoms with respect to the number of the Calpha-atoms of the two proteins are calculated. The user may define the minimum percentage value which is needed to display the calculated data. As a final step the program calculates the resulting structural sequence alignment.