Structure based alignment and clustering of proteins (STRALCP)
View Patent ↗Disclosed are computational methods of clustering a set of protein structures based on local and pair-wise global similarity values. Pair-wise local and global similarity values are generated based on pair-wise structural alignments for each protein in the set of protein structures. Initially, the protein structures are clustered based on pair-wise local similarity values. The protein structures are then clustered based on pair-wise global similarity values. For each given cluster both a representative structure and spans of conserved residues are identified. The representative protein structure is used to assign newly-solved protein structures to a group. The spans are used to characterize conservation and assign a “structural footprint” to the cluster.
1. 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.
2. The method of claim 1 , wherein the first distance cutoff value is a root mean square deviation of 0.5 Angstroms.
3. The method of claim 1 , wherein the candidate span has a minimum number of residue pairs.
4. The method of claim 3 , wherein the minimum number of residue pairs is 3 residue pairs.
5. The method of claim 1 , wherein at least 80% of the fragments of the protein structures in each cluster share candidate spans.
6. The method of claim 1 , further comprising:
for each pair of protein structures in a cluster:
performing a global structural comparison of the distances of structural coordinates of contiguous residue pairs in a first protein structure of the pair and a second protein structure of the pair using a second distance cutoff value;
determining a pair-wise global similarity value for the global structural similarity between the first protein structure and a second protein structure; and
generating a second set of clusters of protein structures from the first set of clusters of protein structures based on the pair-wise global similarity values.
7. The method of claim 6 , wherein the pair-wise global homology value indicates that at least 60% of the residues in the first protein structure and second protein structure form a plurality of residue pairs, wherein a structural coordinate of each member of each residue pair falls within the second distance cutoff value.
8. The method of claim 7 , wherein the second distance cutoff value is 5.0 Angstroms.
9. The method of claim 6 , wherein the pair-wise global homology value is a local-global alignment (LGA_S) score.
10. The method of claim 6 , further comprising:
selecting by the computer a representative protein structure for each cluster in the second set of cluster of protein structures, based on the pair-wise local similarity values and the pair-wise global similarity values.
11. The method of claim 1 wherein a protein structure of the set of protein structures is an experimentally determined protein structure.
12. A non-transitory computer-readable storage medium storing executable computer program instructions for clustering a set of three dimensional protein structures, the computer program instructions comprising instructions for:
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.
13. The computer-readable non-transitory storage medium of claim 12 , wherein the first distance cutoff value is RMSD=0.5 Angstroms.
14. The computer-readable non-transitory storage medium of claim 12 , wherein the candidate span includes a minimum number of residue pairs.
15. The computer-readable non-transitory storage medium of claim 14 , wherein the minimum number of residue pairs is 3 residue pairs.
16. The computer-readable non-transitory storage medium of claim 12 , wherein at least 80% of the fragments of the protein structures in each cluster share candidate spans.
17. The computer-readable non-transitory storage medium of claim 12 , further comprising:
for each pair of protein structures in a cluster:
performing a global structural comparison of the distances of structural coordinates of contiguous residue pairs in a first protein structure of the pair and a second protein structure of the pair using a second distance cutoff value;
determining a pair-wise global similarity value for the global similarity between the first protein structure and a second protein structure; and
generating a second set of clusters of protein structures from the first set of clusters of protein structures based on the pair-wise global similarity values.
18. The computer-readable non-transitory storage medium of claim 17 , wherein the pair-wise global homology value indicates that at least 60% of the residues in the first protein structure and second protein structure form a plurality of residue pairs, wherein a structural coordinate of each member of each residue pair falls within the second distance cutoff value.
19. The computer-readable non-transitory storage medium of claim 18 , wherein the second cutoff distance is 5.0 Angstroms.
20. The computer-readable non-transitory storage medium of claim 17 , wherein the pair-wise global homology value is a local-global alignment (LGA_S) score.
21. The method of claim 1 , wherein a protein structure of the set of protein structures is a computationally modeled protein structure.