The prevailing view concerning protein structure space is that it is composed of a finite number of discrete folds or states. These states have been classified by a number of structural ontologies including the popular CATH (1), SCOP (2), and Pfam (3), which group all known protein structures into fold types based on combinations of sequence homology, structural topology, and function. The recent work by Skolnick et al. (4) challenges this view by constructing a graph based on pair-wise structural relatedness judged by TM score of 5,906 proteins and showing that the average shortest path in this network is seven. This value was arrived at after analyzing the size of the largest strongly connected component in the network as well as how many nodes are within k edges of one another. We believe that this may not necessarily be informative about protein structure space but instead is likely a general network property; the same result can be obtained in a simpler way by using the approximation of Watts and Strogatz (5) for random graphs implying that the average path length is , with N being the total number of nodes and n being the average node degree. We find that the average path length estimated by this method varies considerably with the TM-score threshold for retaining edges but lies between 1.4 and 7 for most graphs. In ref. 4, the outdegree (the number of directed edges originating at a given node) is used, but the total degree (indegree + outdegree) could have been used and would result in decreasing the estimated average shortest path by a factor of ln 2. With increasing TM score, the edge set gets sparser, approaching a cardinality of zero. This is shown in Fig. 1, where the average path length asymptotically approaches infinity as the threshold passes 0.8 (outdegree) or 0.84 (total degree).
Fig. 1.
The relationship between average shortest path computed using the Watts–Strogatz approximation and the TM-score threshold for retaining edges in the graph. Inset shows that most paths belong to [1.4, 7] interval, but once the number of edges approaches the number of nodes, the average shortest path increases sharply. Strict TM-score thresholds result in disconnected graphs.
It is not necessarily true that a short average path means protein structure space is continuous. If the extent of clustering is high, then we would have situations where dense clusters exist that are loosely connected. If this is the case, then either the dataset is not a complete representation of fold space or the space is not continuous.
Acknowledgments.
We acknowledge financial support provided by NIH Grants 5R01GM081680-03 and 2R01GM072014-05.
Footnotes
The authors declare no conflict of interest.
References
- 1.Cuff AL, et al. The CATH classification revisited—Architectures reviewed and new ways to characterize structural divergence in superfamilies. Nucl Acids Res. 2009;37:D310–D314. doi: 10.1093/nar/gkn877. [DOI] [PMC free article] [PubMed] [Google Scholar]
- 2.Murzin A, Brenner SE, Hubbard T, Chothia C. SCOP: A structural classification of proteins database for the investigation of sequences and structures. J Mol Biol. 1995;247:536–540. doi: 10.1006/jmbi.1995.0159. [DOI] [PubMed] [Google Scholar]
- 3.Finn RD, et al. The Pfam protein families database. Nucl Acids Res. 2008;36:D281–D288. doi: 10.1093/nar/gkm960. [DOI] [PMC free article] [PubMed] [Google Scholar]
- 4.Skolnick J, Arakaki AK, Lee SY, Brylinski M. The continuity of protein structure space is an intrinsic property of proteins. Proc Natl Acad Sci USA. 2009;106:15690–15695. doi: 10.1073/pnas.0907683106. [DOI] [PMC free article] [PubMed] [Google Scholar]
- 5.Watts DJ, Strogatz SH. Collective dynamics of “small-world” networks. Nature. 1998;393:440–442. doi: 10.1038/30918. [DOI] [PubMed] [Google Scholar]