Patent ID: 6859736

Claim:
A program storage device accessible by a computer embodying a program of instructions executable by said computer to perform method steps for protein structure alignment, comprising: (a) receiving atomic coordinates of a first protein with N 1 atoms; (b) receiving atomic coordinates of a second protein with N 2 atoms; (c) making an initial alignment of said atoms of said first protein to said atoms of said second protein; (d) calculating all atomic distances between said atomic coordinates of said atoms of said first protein and said atomic coordinates of said atoms of said second protein; (e) defining a matrix with a plurality of binary assignment variables wherein each binary assignment variable corresponding to either a match or to a gap; (f) defining one or more mean field equations wherein said plurality of binary assignment variables are replaced by a plurality of continuous mean field variables, whereby said each mean field variable has a value between 0 and 1, and a plurality of forces that are proportional to said atomic distances squared; (g) formulating an energy function, wherein: said energy function includes a first cost for each said atomic distance wherein said distance is a weighted body transformation using said continuous mean field variables of said first protein while keeping said second protein fixed, said energy function includes a second cost λ for each said gap by either said first protein or said second protein, said energy function includes a third cost δ for a position-independent consecutive said gap, said energy function includes a fourth cost for enforcing a constraint to satisfy that each said atom of said first protein either aligns with said atom of said second protein or to said gap; (h) minimizing by an iterative process of said energy function and updating said continuous mean field variables in said mean field equations for a decreasing set of temperatures T until convergence to a predefined convergence value is reached; and (i) after convergence rounding off said continuous mean field variables to either 0 or 1.