Are RNA networks scale-free?

A network is scale-free if its connectivity density function is proportional to a power-law distribution. It has been suggested that scale-free networks may provide an explanation for the robustness observed in certain physical and biological phenomena, since the presence of a few highly connected hub nodes and a large number of small-degree nodes may provide alternate paths between any two nodes on average—such robustness has been suggested in studies of metabolic networks, gene interaction networks and protein folding. A theoretical justification for why many networks appear to be scale-free has been provided by Barabási and Albert, who argue that expanding networks, in which new nodes are preferentially attached to highly connected nodes, tend to be scale-free. In this paper, we provide the first efficient algorithm to compute the connectivity density function for the ensemble of all homopolymer secondary structures of a user-specified length—a highly nontrivial result, since the exponential size of such networks precludes their enumeration. Since existent power-law fitting software, such as powerlaw , cannot be used to determine a power-law fit for our exponentially large RNA connectivity data, we also implement efficient code to compute the maximum likelihood estimate for the power-law scaling factor and associated Kolmogorov–Smirnov p value. Hypothesis tests strongly indicate that homopolymer RNA secondary structure networks are not scale-free; moreover, this appears to be the case for real (non-homopolymer) RNA networks.

Related papers:

title: Emergence of scaling in random networks
abstract: Systems as diverse as genetic networks or the World Wide Web are best described as networks with complex topology. A common property of many large networks is that the vertex connectivities follow a scale-free power-law distribution. This feature was found to be a consequence of two generic mechanisms: (i) networks expand continuously by the addition of new vertices, and (ii) new vertices attach preferentially to sites that are already well connected. A model based on these two ingredients reproduces the observed stationary scale-free distributions, which indicates that the development of large networks is governed by robust self-organizing phenomena that go beyond the particulars of the individual systems.

title: Toward a protein-protein interaction map of the budding yeast: A comprehensive system to examine two-hybrid interactions in all possible combinations between the yeast proteins.
abstract: Protein-protein interactions play pivotal roles in various aspects of the structural and functional organization of the cell, and their complete description is indispensable to thorough understanding of the cell. As an approach toward this goal, here we report a comprehensive system to examine two-hybrid interactions in all of the possible combinations between proteins of Saccharomyces cerevisiae. We cloned all of the yeast ORFs individually as a DNA-binding domain fusion ("bait") in a MATa strain and as an activation domain fusion ("prey") in a MATalpha strain, and subsequently divided them into pools, each containing 96 clones. These bait and prey clone pools were systematically mated with each other, and the transformants were subjected to strict selection for the activation of three reporter genes followed by sequence tagging. Our initial examination of approximately 4 x 10(6) different combinations, constituting approximately 10% of the total to be tested, has revealed 183 independent two-hybrid interactions, more than half of which are entirely novel. Notably, the obtained binary data allow us to extract more complex interaction networks, including the one that may explain a currently unsolved mechanism for the connection between distinct steps of vesicular transport. The approach described here thus will provide many leads for integration of various cellular functions and serve as a major driving force in the completion of the protein-protein interaction map.

title: A network of protein–protein interactions in yeast
abstract: A global analysis of 2,709 published interactions between proteins of the yeast Saccharomyces cerevisiae has been performed, enabling the establishment of a single large network of 2,358 interactions among 1,548 proteins. Proteins of known function and cellular location tend to cluster together, with 63% of the interactions occurring between proteins with a common functional assignment and 76% occurring between proteins found in the same subcellular compartment. Possible functions can be assigned to a protein based on the known functions of its interacting partners. This approach correctly predicts a functional category for 72% of the 1,393 characterized proteins with at least one partner of known function, and has been applied to predict functions for 364 previously uncharacterized proteins.

title: The Connectivity Structure, Giant Strong Component and Centrality of Metabolic Networks
abstract: Structural and functional analysis of genome-based large-scale metabolic networks is important for understanding the design principles and regulation of the metabolism at a system level. The metabolic network is conventionally considered to be highly integrated and very complex. A rational reduction of the metabolic network to its core structure and a deeper understanding of its functional modules are important.



In this work, we show that the metabolites in a metabolic network are far from fully connected. A connectivity structure consisting of four major subsets of metabolites and reactions, i.e. a fully connected sub-network, a substrate subset, a product subset and an isolated subset is found to exist in metabolic networks of 65 fully sequenced organisms. The largest fully connected part of a metabolic network, called 'the giant strong component (GSC)', represents the most complicated part and the core of the network and has the feature of scale-free networks. The average path length of the whole network is primarily determined by that of the GSC. For most of the organisms, GSC normally contains less than one-third of the nodes of the network. This connectivity structure is very similar to the 'bow-tie' structure of World Wide Web. Our results indicate that the bow-tie structure may be common for large-scale directed networks. More importantly, the uncovered structure feature makes a structural and functional analysis of large-scale metabolic network more amenable. As shown in this work, comparing the closeness centrality of the nodes in the GSC can identify the most central metabolites of a metabolic network. To quantitatively characterize the overall connection structure of the GSC we introduced the term 'overall closeness centralization index (OCCI)'. OCCI correlates well with the average path length of the GSC and is a useful parameter for a system-level comparison of metabolic networks of different organisms.

title: The yeast coexpression network has a small‐world, scale‐free architecture and can be explained by a simple model
abstract: We investigated the gene coexpression network in Saccharomyces cerevisiae, in which genes are linked when they are coregulated. This network is shown to have a scale‐free, small‐world architecture. Such architecture is typical of biological networks in which the nodes are connected when they are involved in the same biological process. Current models for the evolution of intracellular networks do not adequately reproduce the features that we observe in the network. We therefore derive a new model for its evolution based on the observation that there is a positive correlation between the sequence similarity of paralogues and their probability of coexpression or sharing of transcription factor binding sites (TFBSs). The simple, neutralist's model consists of (1) coduplication of genes with their TFBSs, (2) deletion and duplication of individual TFBSs and (3) gene loss. A network is constructed by connecting genes that share multiple TFBSs. Our model reproduces the scale‐free, small‐world architecture of the coregulation network and the homology relations between coregulated genes without the need for selection either at the level of the network structure or at the level of gene regulation.

title: Protein folded states are kinetic hubs
abstract: Understanding molecular kinetics, and particularly protein folding, is a classic grand challenge in molecular biophysics. Network models, such as Markov state models (MSMs), are one potential solution to this problem. MSMs have recently yielded quantitative agreement with experimentally derived structures and folding rates for specific systems, leaving them positioned to potentially provide a deeper understanding of molecular kinetics that can lead to experimentally testable hypotheses. Here we use existing MSMs for the villin headpiece and NTL9, which were constructed from atomistic simulations, to accomplish this goal. In addition, we provide simpler, humanly comprehensible networks that capture the essence of molecular kinetics and reproduce qualitative phenomena like the apparent two-state folding often seen in experiments. Together, these models show that protein dynamics are dominated by stochastic jumps between numerous metastable states and that proteins have heterogeneous unfolded states (many unfolded basins that interconvert more rapidly with the native state than with one another) yet often still appear two-state. Most importantly, we find that protein native states are hubs that can be reached quickly from any other state. However, metastability and a web of nonnative states slow the average folding rate. Experimental tests for these findings and their implications for other fields, like protein design, are also discussed.

title: How Scale-Free Are Biological Networks
abstract: The concept of scale-free network has emerged as a powerful unifying paradigm in the study of complex systems in biology and in physical and social studies. Metabolic, protein, and gene interaction networks have been reported to exhibit scale-free behavior based on the analysis of the distribution of the number of connections of the network nodes. Here we study 10 published datasets of various biological interactions and perform goodness-of-fit tests to determine whether the given data is drawn from the power-law distribution. Our analysis did not identify a single interaction network that has a nonzero probability of being drawn from the power-law distribution.

title: Power-Law Distributions in Empirical Data
abstract: Power-law distributions occur in many situations of scientific interest and have significant consequences for our understanding of natural and man-made phenomena. Unfortunately, the detection and characterization of power laws is complicated by the large fluctuations that occur in the tail of the distribution—the part of the distribution representing large but rare events—and by the difficulty of identifying the range over which power-law behavior holds. Commonly used methods for analyzing power-law data, such as least-squares fitting, can produce substantially inaccurate estimates of parameters for power-law distributions, and even in cases where such methods return accurate answers they are still unsatisfactory because they give no indication of whether the data obey a power law at all. Here we present a principled statistical framework for discerning and quantifying power-law behavior in empirical data. Our approach combines maximum-likelihood fitting methods with goodness-of-fit tests based on the Kolmogorov-Smirnov (KS) statistic and likelihood ratios. We evaluate the effectiveness of the approach with tests on synthetic data and give critical comparisons to previous approaches. We also apply the proposed methods to twenty-four real-world data sets from a range of different disciplines, each of which has been conjectured to follow a power-law distribution. In some cases we find these conjectures to be consistent with the data, while in others the power law is ruled out.

title: Small worlds in RNA structures.
abstract: I consider conformational spaces of tRNA(phe) defined by sets of suboptimal structures from the perspective of small-world networks. Herein, the influence of modifications on typical small-world network properties and the shape of energy landscapes is discussed. Results indicate that natural modifications influence the degree of local clustering and mean path lengths far more than random or no modifications. High frequencies in the thermodynamic ensemble coincide with high numbers of neighboring structures that one conformation can adopt by one elementary move. Conformation spaces indicate the existence of modular substructures. It can be shown that modifications leave the nature of small-world topology untouched albeit natural modifications have a reasonable enhancing and streamlining effect on the degree of clustering and therefore on the substructures of the conformational space.

title: Expected degree for RNA secondary structure networks
abstract: Consider the network of all secondary structures of a given RNA sequence, where nodes are connected when the corresponding structures have base pair distance one. The expected degree of the network is the average number of neighbors, where average may be computed with respect to the either the uniform or Boltzmann probability. Here, we describe the first algorithm, RNAexpNumNbors, that can compute the expected number of neighbors, or expected network degree, of an input sequence. For RNA sequences from the Rfam database, the expected degree is significantly less than the constrained minimum free energy structure, defined to have minimum free energy (MFE) over all structures consistent with the Rfam consensus structure. The expected degree of structural RNAs, such as purine riboswitches, paradoxically appears to be smaller than that of random RNA, yet the difference between the degree of the MFE structure and the expected degree is larger than that of random RNA. Expected degree does not seem to correlate with standard structural diversity measures of RNA, such as positional entropy and ensemble defect. The program RNAexpNumNbors is written in C, runs in cubic time and quadratic space, and is publicly available at http://bioinformatics.bc.edu/clotelab/RNAexpNumNbors.

title: RNA folding at elementary step resolution.
abstract: We study the stochastic folding kinetics of RNA sequences into secondary structures with a new algorithm based on the formation, dissociation, and the shifting of individual base pairs. We discuss folding mechanisms and the correlation between the barrier structure of the conformational landscape and the folding kinetics for a number of examples based on artificial and natural sequences, including the influence of base modification in tRNAs.

title: On some new sequences generalizing the Catalan and Motzkin numbers
abstract: Some new sequences are introduced which satisfy quadratic recurrence rules similar to those satisfied by the classical Catalan numbers and the less well-known Motzkin numbers. For each sequence the general term is expressed as a sum of products of Catalan numbers and generalized Fibonacci numbers. In addition, first-order asymptotic formulae are given for the most interesting cases.

title: powerlaw: A Python Package for Analysis of Heavy-Tailed Distributions
abstract: Power laws are theoretically interesting probability distributions that are also frequently used to describe empirical data. In recent years, effective statistical methods for fitting power laws have been developed, but appropriate use of these techniques requires significant programming and statistical insight. In order to greatly decrease the barriers to using good statistical methods for fitting power law distributions, we developed the powerlaw Python package. This software package provides easy commands for basic fitting and statistical analysis of distributions. Notably, it also seeks to support a variety of user needs by being exhaustive in the options available to the user. The source code is publicly available and easily extensible.

title: Simulating from a multinomial distribution with large number of categories
abstract: The multinomial distribution is a key-distribution for several applications. For this reason, many methods have been proposed so far in the literature in order to deal with the problem of simulation from it. A slight modification is suggested which can be used in conjunction with any of the standard schemes. The proposed variation is a two-stage procedure based on the property of the multinomial distribution that for any partition of the set of outcomes the vector of total frequencies of each part follows also a multinomial distribution with parameters adjusted accordingly. It is empirically exhibited that this variation is faster than the original procedures in case the numbers of independent trials and possible outcomes are both large. The time reduction is illustrated via a simulation study for several programming languages such as R, Matlab, and others.

title: Statistical mechanics of complex networks
abstract: The emergence of order in natural systems is a constant source of inspiration for both physical and biological sciences. While the spatial order characterizing for example the crystals has been the basis of many advances in contemporary physics, most complex systems in nature do not offer such high degree of order. Many of these systems form complex networks whose nodes are the elements of the system and edges represent the interactions between them. 
Traditionally complex networks have been described by the random graph theory founded in 1959 by Paul Erdohs and Alfred Renyi. One of the defining features of random graphs is that they are statistically homogeneous, and their degree distribution (characterizing the spread in the number of edges starting from a node) is a Poisson distribution. In contrast, recent empirical studies, including the work of our group, indicate that the topology of real networks is much richer than that of random graphs. In particular, the degree distribution of real networks is a power-law, indicating a heterogeneous topology in which the majority of the nodes have a small degree, but there is a significant fraction of highly connected nodes that play an important role in the connectivity of the network. 
The scale-free topology of real networks has very important consequences on their functioning. For example, we have discovered that scale-free networks are extremely resilient to the random disruption of their nodes. On the other hand, the selective removal of the nodes with highest degree induces a rapid breakdown of the network to isolated subparts that cannot communicate with each other. 
The non-trivial scaling of the degree distribution of real networks is also an indication of their assembly and evolution. Indeed, our modeling studies have shown us that there are general principles governing the evolution of networks. Most networks start from a small seed and grow by the addition of new nodes which attach to the nodes already in the system. This process obeys preferential attachment: the new nodes are more likely to connect to nodes with already high degree. We have proposed a simple model based on these two principles wich was able to reproduce the power-law degree distribution of real networks. Perhaps even more importantly, this model paved the way to a new paradigm of network modeling, trying to capture the evolution of networks, not just their static topology.

title: Using information theory to assess the diversity, complexity, and development of communicative repertoires.
abstract: The application of quantitative and comparative measures from information theory on animal communication can provide novel insights into the ecological, environmental, social, and contextual properties that shape the structure, organization, and function of signal repertoires. Using 2 phylogenetically different mammalian species that share similar ecological and social constraints as examples, the authors quantitatively examined the internal structure and development of a subsystem of these species' vocal repertoires in comparison with that of human language and illustrated that these species exhibit convergent developmental processes. The authors also discussed how predictions on the structure and organization of animal communication systems can be made from this new application of information theoretic measures with respect to behavioral ecology.

title: The large-scale organization of metabolic networks
abstract: In a cell or microorganism, the processes that generate mass, energy, information transfer and cell-fate specification are seamlessly integrated through a complex network of cellular constituents and reactions. However, despite the key role of these networks in sustaining cellular functions, their large-scale structure is essentially unknown. Here we present a systematic comparative mathematical analysis of the metabolic networks of 43 organisms representing all three domains of life. We show that, despite significant variation in their individual constituents and pathways, these metabolic networks have the same topological scaling properties and show striking similarities to the inherent organization of complex non-biological systems. This may indicate that metabolic organization is not only identical for all living organisms, but also complies with the design principles of robust and error-tolerant scale-free networks, and may represent a common blueprint for the large-scale organization of interactions among all cellular constituents.

title: Scale-free networks emerging from multifractal time series.
abstract: Methods connecting dynamical systems and graph theory have attracted increasing interest in the past few years, with applications ranging from a detailed comparison of different kinds of dynamics to the characterization of empirical data. Here we investigate the effects of the (multi)fractal properties of a signal, common in time series arising from chaotic dynamics or strange attractors, on the topology of a suitably projected network. Relying on the box-counting formalism, we map boxes into the nodes of a network and establish analytic expressions connecting the natural measure of a box with its degree in the graph representation. We single out the conditions yielding to the emergence of a scale-free topology and validate our findings with extensive numerical simulations. We finally present a numerical analysis on the properties of weighted and directed network projections.

title: The role of exon shuffling in shaping protein-protein interaction networks
abstract: BackgroundPhysical protein-protein interaction (PPI) is a critical phenomenon for the function of most proteins in living organisms and a significant fraction of PPIs are the result of domain-domain interactions. Exon shuffling, intron-mediated recombination of exons from existing genes, is known to have been a major mechanism of domain shuffling in metazoans. Thus, we hypothesized that exon shuffling could have a significant influence in shaping the topology of PPI networks.ResultsWe tested our hypothesis by compiling exon shuffling and PPI data from six eukaryotic species: Homo sapiens, Mus musculus, Drosophila melanogaster, Caenorhabditis elegans, Cryptococcus neoformans and Arabidopsis thaliana. For all four metazoan species, genes enriched in exon shuffling events presented on average higher vertex degree (number of interacting partners) in PPI networks. Furthermore, we verified that a set of protein domains that are simultaneously promiscuous (known to interact to multiple types of other domains), self-interacting (able to interact with another copy of themselves) and abundant in the genomes presents a stronger signal for exon shuffling.ConclusionsExon shuffling appears to have been a recurrent mechanism for the emergence of new PPIs along metazoan evolution. In metazoan genomes, exon shuffling also promoted the expansion of some protein domains. We speculate that their promiscuous and self-interacting properties may have been decisive for that expansion.

title: Scale-free networks are rare
abstract: Real-world networks are often claimed to be scale free, meaning that the fraction of nodes with degree k follows a power law k−α, a pattern with broad implications for the structure and dynamics of complex systems. However, the universality of scale-free networks remains controversial. Here, we organize different definitions of scale-free networks and construct a severe test of their empirical prevalence using state-of-the-art statistical tools applied to nearly 1000 social, biological, technological, transportation, and information networks. Across these networks, we find robust evidence that strongly scale-free structure is empirically rare, while for most networks, log-normal distributions fit the data as well or better than power laws. Furthermore, social networks are at best weakly scale free, while a handful of technological and biological networks appear strongly scale free. These findings highlight the structural diversity of real-world networks and the need for new theoretical explanations of these non-scale-free patterns.Real-world networks are often said to be ”scale free”, meaning their degree distribution follows a power law. Broido and Clauset perform statistical tests of this claim using a large and diverse corpus of real-world networks, showing that scale-free structure is far from universal.

title: A Brief History of Generative Models for Power Law and Lognormal Distributions
abstract: Recently, I became interested in a current debate over whether file size distributions are best modelled by a power law distribution or a lognormal distribution. In trying to learn enough about these distributions to settle the question, I found a rich and long history, spanning many fields. Indeed, several recently proposed models from the computer science community have antecedents in work from decades ago. Here, I briefly survey some of this history, focusing on underlying generative models that lead to these distributions. One finding is that lognormal and power law distributions connect quite naturally, and hence, it is not surprising that lognormal distributions have arisen as a possible alternative to power law distributions across many fields.

title: tRNAdb 2009: compilation of tRNA sequences and tRNA genes
abstract: One of the first specialized collections of nucleic acid sequences in life sciences was the ‘compilation of tRNA sequences and sequences of tRNA genes’ (http://www.trna.uni-bayreuth.de). Here, an updated and completely restructured version of this compilation is presented (http://trnadb.bioinf.uni-leipzig.de). The new database, tRNAdb, is hosted and maintained in cooperation between the universities of Leipzig, Marburg, and Strasbourg. Reimplemented as a relational database, tRNAdb will be updated periodically and is searchable in a highly flexible and user-friendly way. Currently, it contains more than 12 000 tRNA genes, classified into families according to amino acid specificity. Furthermore, the implementation of the NCBI taxonomy tree facilitates phylogeny-related queries. The database provides various services including graphical representations of tRNA secondary structures, a customizable output of aligned or un-aligned sequences with a variety of individual and combinable search criteria, as well as the construction of consensus sequences for any selected set of tRNAs.

title: A consensus view of fold space: Combining SCOP, CATH, and the Dali Domain Dictionary
abstract: We have determined consensus protein‐fold classifications on the basis of three classification methods, SCOP, CATH, and Dali. These classifications make use of different methods of defining and categorizing protein folds that lead to different views of protein‐fold space. Pairwise comparisons of domains on the basis of their fold classifications show that much of the disagreement between the classification systems is due to differing domain definitions rather than assigning the same domain to different folds. However, there are significant differences in the fold assignments between the three systems. These remaining differences can be explained primarily in terms of the breadth of the fold classifications. Many structures may be defined as having one fold in one system, whereas far fewer are defined as having the analogous fold in another system. By comparing these folds for a nonredundant set of proteins, the consensus method breaks up broad fold classifications and combines restrictive fold classifications into metafolds, creating, in effect, an averaged view of fold space. This averaged view requires that the structural similarities between proteins having the same metafold be recognized by multiple classification systems. Thus, the consensus map is useful for researchers looking for fold similarities that are relatively independent of the method used to compare proteins. The 30 most populated metafolds, representing the folds of about half of a nonredundant subset of the PDB, are presented here. The full list of metafolds is presented on the Web.

title: The PDB is a covering set of small protein structures.
abstract: Structure comparisons of all representative proteins have been done. Employing the relative root mean square deviation (RMSD) from native enables the assessment of the statistical significance of structure alignments of different lengths in terms of a Z-score. Two conclusions emerge: first, proteins with their native fold can be distinguished by their Z-score. Second and somewhat surprising, all small proteins up to 100 residues in length have significant structure alignments to other proteins in a different secondary structure and fold class; i.e. 24.0% of them have 60% coverage by a template protein with a RMSD below 3.5A and 6.0% have 70% coverage. If the restriction that we align proteins only having different secondary structure types is removed, then in a representative benchmark set of proteins of 200 residues or smaller, 93% can be aligned to a single template structure (with average sequence identity of 9.8%), with a RMSD less than 4A, and 79% average coverage. In this sense, the current Protein Data Bank (PDB) is almost a covering set of small protein structures. The length of the aligned region (relative to the whole protein length) does not differ among the top hit proteins, indicating that protein structure space is highly dense. For larger proteins, non-related proteins can cover a significant portion of the structure. Moreover, these top hit proteins are aligned to different parts of the target protein, so that almost the entire molecule can be covered when combined. The number of proteins required to cover a target protein is very small, e.g. the top ten hit proteins can give 90% coverage below a RMSD of 3.5A for proteins up to 320 residues long. These results give a new view of the nature of protein structure space, and its implications for protein structure prediction are discussed.

title: On the scale-free nature of RNA secondary structure networks
abstract: A network is scale-free if its connectivity density function is proportional to a power-law distribution. Scale-free networks may provide an explanation for the robustness observed in certain physical and biological phenomena, since the presence of a few highly connected hub nodes and a large number of small- degree nodes may provide alternate paths between any two nodes on average -- such robustness has been suggested in studies of metabolic networks, gene interaction networks and protein folding. A theoretical justification for why biological networks are often found to be scale-free may lie in the well-known fact that expanding networks in which new nodes are preferentially attached to highly connected nodes tend to be scale-free. In this paper, we provide the first efficient algorithm to compute the connectivity density function for the ensemble of all secondary structures of a user-specified length, and show both by computational and theoretical arguments that preferential attachment holds when expanding the network from length n to length n + 1 structures. Since existent power-law fitting software, such as powerlaw, cannot be used to determine a power-law fit for our exponentially large RNA connectivity data, we also implement efficient code to compute the maximum likelihood estimate for the power-law scaling factor and associated Kolmogorov-Smirnov p-value. Statistical goodness-of-fit tests indicate that one must reject the hypothesis that RNA connectivity data follows a power-law distribution. Nevertheless, the power-law fit is visually a good approximation for the tail of connectivity data, and provides a rationale for investigation of preferential attachment in the context of macromolecular folding.

title: Computer simulations of prebiotic evolution.
abstract: This paper is a review of our previous work on the field of possible ways of prebiotic evolution. We propose an algorithm providing sequences of model proteins with rapid folding into a given native conformation. Thermodynamical analysis shows that the increase in speed is matched by an increase in stability: the evolved sequences are much more stable in their native conformation than the initial random sequence. We discuss a possible origin of the first biopolymers, having stable unique structure. We suggest that at the prebiotic stage of evolution, long organic polymers had to be compact in order to avoid hydrolysis and had to be soluble and thus must not be exceedingly hydrophobic. We present an algorithm that generates such sequences of model proteins. The evolved sequences turn out to have a stable unique structure, into which they quickly fold. This result illustrates the idea that the unique three-dimensional native structure of first biopolymers could have evolved as a side effect of a nonspecific physico-chemical factors acting at the prebiotic stage of evolution.

title: Exploring the Universe of Protein Structures beyond the Protein Data Bank
abstract: It is currently believed that the atlas of existing protein structures is faithfully represented in the Protein Data Bank. However, whether this atlas covers the full universe of all possible protein structures is still a highly debated issue. By using a sophisticated numerical approach, we performed an exhaustive exploration of the conformational space of a 60 amino acid polypeptide chain described with an accurate all-atom interaction potential. We generated a database of around 30,000 compact folds with at least of secondary structure corresponding to local minima of the potential energy. This ensemble plausibly represents the universe of protein folds of similar length; indeed, all the known folds are represented in the set with good accuracy. However, we discover that the known folds form a rather small subset, which cannot be reproduced by choosing random structures in the database. Rather, natural and possible folds differ by the contact order, on average significantly smaller in the former. This suggests the presence of an evolutionary bias, possibly related to kinetic accessibility, towards structures with shorter loops between contacting residues. Beside their conceptual relevance, the new structures open a range of practical applications such as the development of accurate structure prediction strategies, the optimization of force fields, and the identification and design of novel folds.

title: Extant fold-switching proteins are widespread
abstract: It is commonly thought that each globular protein has a single 3D structure, or fold, that fosters its function. In contrast, recent studies have identified several fold-switching proteins whose secondary structures can be remodeled in response to cellular stimuli. Although thought to be rare, we found 96 literature-validated fold-switching proteins by exhaustively searching the database of protein structures [Protein Data Bank (PDB)]. Characterizing these proteins led us to hypothesize that their abundance may be underrepresented in the PDB. Thus, we developed a computational method that identifies fold-switching proteins and used it to estimate that 0.5–4% of PDB proteins switch folds. These results suggest that proteins switch folds with significant frequency, which has implications for cell biology, genomics, and human health. A central tenet of biology is that globular proteins have a unique 3D structure under physiological conditions. Recent work has challenged this notion by demonstrating that some proteins switch folds, a process that involves remodeling of secondary structure in response to a few mutations (evolved fold switchers) or cellular stimuli (extant fold switchers). To date, extant fold switchers have been viewed as rare byproducts of evolution, but their frequency has been neither quantified nor estimated. By systematically and exhaustively searching the Protein Data Bank (PDB), we found ∼100 extant fold-switching proteins. Furthermore, we gathered multiple lines of evidence suggesting that these proteins are widespread in nature. Based on these lines of evidence, we hypothesized that the frequency of extant fold-switching proteins may be underrepresented by the structures in the PDB. Thus, we sought to identify other putative extant fold switchers with only one solved conformation. To do this, we identified two characteristic features of our ∼100 extant fold-switching proteins, incorrect secondary structure predictions and likely independent folding cooperativity, and searched the PDB for other proteins with similar features. Reassuringly, this method identified dozens of other proteins in the literature with indication of a structural change but only one solved conformation in the PDB. Thus, we used it to estimate that 0.5–4% of PDB proteins switch folds. These results demonstrate that extant fold-switching proteins are likely more common than the PDB reflects, which has implications for cell biology, genomics, and human health.