Patent ID: 8467971

Claim:
A computer-implemented method for clustering a set of three dimensional protein structures, the method comprising: identifying, by a computer, the set of three dimensional protein structures, each three-dimensional protein structure comprising a polypeptide sequence and structural coordinates; generating, by the computer, a structural alignment of the set of three-dimensional protein structures; for each pair of protein structures in the aligned set: designating, by the computer, a first protein structure of the pair as a reference protein structure; generating, by the computer, a first plurality of fragments for the reference protein structure, each fragment comprising a polypeptide subsequence of contiguous residues of a pre-determined length and associated distances of structural coordinates of contiguous residue pairs; generating, by the computer, a second plurality of fragments for a second protein structure in the pair, each fragment comprising a polypeptide subsequence of contiguous residues of the pre-determined length and associated distances of structural coordinates of contiguous residue pairs; performing, by the computer, a local structural comparison of the distances of structural coordinates of contiguous residue pairs between the first plurality of fragments and the second plurality of fragments using a first distance cutoff value; identifying, by the computer, candidate spans consisting of a plurality of contiguous residue pairs from the first plurality of fragments and the second plurality of fragments having structural coordinates within the first distance cutoff value; determining, by the computer, a pair-wise local similarity value that indicates the number of fragments from the first plurality of fragments and from the second plurality of fragments that share candidate spans; assigning, by the computer, the identified candidate spans and the pair-wise local similarity value to the reference protein structure; generating, by the computer, a matrix of identified candidate spans for each of the pairs of protein structures; and generating, by the computer, a first cluster of protein structures based on the matrix of identified candidate spans, each cluster having protein structures with at least a pre-determined number of fragments that share candidate spans, thereby clustering the set of three-dimensional protein structures.