zbMATH — the first resource for mathematics

Are RNA networks scale-free? (English) Zbl 1437.62174
Author’s abstract: 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 A.-L. Barabási and R. Albert [Science 286, No. 5439, 509–512 (1999; Zbl 1226.05223)], 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.
62G32 Statistics of extreme values; tail inference
62G07 Density estimation
05C82 Small world graphs, complex networks (graph-theoretic aspects)
68R05 Combinatorics in computer science
92D20 Protein sequences, DNA sequences
62P10 Applications of statistics to biology and medical sciences; meta analysis
Full Text: DOI
[1] Abkevich VI, Gutin AM, Shakhnovich EI (1997) Computer simulations of prebiotic evolution. In: The Pacific symposium on biocomputing, pp 27-38
[2] Albert, R.; Barabási, A-L, Statistical mechanics of complex networks, Rev Mod Phys, 74, 47-97 (2002) · Zbl 1205.82086
[3] Alstott, J.; Bullmore, E.; Plenz, D., Powerlaw: a Python package for analysis of heavy-tailed distributions, PLoS ONE, 9, 1, e85777 (2014)
[4] Barabasi, Al; Albert, R., Emergence of scaling in random networks, Science, 286, 5439, 509-512 (1999) · Zbl 1226.05223
[5] Bayegan A, Clote P (2015) Network properties of the ensemble of RNA structures. PLoS ONE 10(10):e0139471 (preprint available at arxiv:1508.05499)
[6] Bowman, Gr; Pande, Vs, Protein folded states are kinetic hubs, Proc Natl Acad Sci USA, 107, 24, 10890-10895 (2010)
[7] Broido, Ad; Clauset, A., Scale-free networks are rare, Nat Commun, 10, 1, 1-10 (2019)
[8] Budroni, Ma; Baronchelli, A.; Pastor-Satorras, R., Scale-free networks emerging from multifractal time series, Phys Rev E, 95, 5-1, 052311 (2017)
[9] Cancherini, Dv; Franca, Gs; De Souza, Sj, The role of exon shuffling in shaping protein-protein interaction networks, BMC Genom, 11, S11 (2010)
[10] Clauset, A.; Shalizi, Cr; Newman, Mej, Power-law distributions in empirical data, SIAM Rev, 51, 4, 661-703 (2009) · Zbl 1176.62001
[11] Clote, P., Expected degree for RNA secondary structure networks, J Comput Chem, 36, 2, 103-117 (2015)
[12] Clote P (2018) On the scale-free nature of RNA secondary structure networks, pp 1-26
[13] Clote, P.; Bayegan, A., Network properties of the ensemble of RNA structures, PLoS ONE, 10, 10, e0139476 (2015)
[14] Cossio, P.; Trovato, A.; Pietrucci, F.; Seno, F.; Maritan, A.; Laio, A., Exploring the universe of protein structures beyond the Protein Data Bank, PLoS Comput Biol, 6, 11, e1000957 (2010)
[15] Day, R.; Beck, Da; Armen, Rs; Daggett, V., A consensus view of fold space: combining SCOP, CATH, and the Dali Domain Dictionary, Protein Sci, 12, 10, 2150-2160 (2003)
[16] Flamm, C.; Fontana, W.; Hofacker, Il; Schuster, P., RNA folding at elementary step resolution, RNA, 6, 325-338 (2000)
[17] Gilbert, W., Why genes in pieces?, Nature, 271, 5645, 501 (1978)
[18] Ito, T.; Tashiro, K.; Muta, S.; Ozawa, R.; Chiba, T.; Nishizawa, M.; Yamamoto, K.; Kuhara, S.; Sakaki, Y., 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, Proc Natl Acad Sci USA, 97, 3, 1143-1147 (2000)
[19] Jeong, H.; Tombor, B.; Albert, R.; Oltvai, Zn; Barabasi, Al, The large-scale organization of metabolic networks, Nature, 407, 6804, 651-654 (2000)
[20] Juhling, F.; Morl, M.; Hartmann, Rk; Sprinzl, M.; Stadler, Pf; Putz, J., tRNAdb 2009: compilation of tRNA sequences and tRNA genes, Nucl Acids Res, 37, Database, D159-D162 (2009)
[21] Khanin, R.; Wit, E., How scale-free are biological networks, J Comput Biol, 13, 3, 810-818 (2006)
[22] Kihara, D.; Skolnick, J., The PDB is a covering set of small protein structures, J Mol Biol, 334, 4, 793-802 (2003)
[23] Lorenz, R.; Bernhart, Sh; Höner Zu Siederdissen, C.; Tafer, H.; Flamm, C.; Stadler, Pf; Hofacker, Il, Viennarna package 2.0, Algorithms Mol Biol, 6, 26 (2011)
[24] Ma, Hw; Zeng, Ap, The connectivity structure, giant strong component and centrality of metabolic networks, Bioinformatics, 19, 11, 1423-1430 (2003)
[25] Malefaki, S.; Iliopoulos, G., Simulating from a multinomial distribution with large number of categories, Comput Stat Data Anal, 51, 5471-5476 (2007) · Zbl 1365.62058
[26] Mccowan, B.; Doyle, Lr; Hanser, Sf, Using information theory to assess the diversity, complexity, and development of communicative repertoires, J Comput Psychol, 116, 2, 166-172 (2002)
[27] Mitzenmacher, M., A brief history of generative models for power law and lognormal distributions, Internet Math., 1, 2, 226-251 (2004) · Zbl 1063.68526
[28] Newman, Mej, The structure and function of complex networks, SIAM Rev, 45, 2, 167-256 (2006) · Zbl 1029.68010
[29] Newman, Mej, Networks: an introduction (2010), Oxford: Oxford University Press, Oxford
[30] Nussinov, R.; Jacobson, Ab, Fast algorithm for predicting the secondary structure of single stranded RNA, Proc Natl Acad Sci USA, 77, 11, 6309-6313 (1980)
[31] Porter, Ll; Looger, Ll, Extant fold-switching proteins are widespread, Proc Natl Acad Sci USA, 115, 23, 5968-5973 (2018)
[32] Schwikowski, P.; Uetz, Band; Fields, S., A network of protein-protein interactions in yeast, Nat Biotechnol, 18, 1257-1261 (2000)
[33] Stein, Pr; Waterman, Ms, On some new sequences generalizing the Catalan and Motzkin numbers, Discrete Math, 26, 261-272 (1978) · Zbl 0405.10009
[34] Tong, Ah; Lesage, G.; Bader, Gd; Ding, H.; Xu, H.; Xin, X.; Young, J.; Berriz, Gf; Brost, Rl; Chang, M.; Chen, Y.; Cheng, X.; Chua, G.; Friesen, H.; Goldberg, Ds; Haynes, J.; Humphries, C.; He, G.; Hussein, S.; Ke, L.; Krogan, N.; Li, Z.; Levinson, Jn; Lu, H.; Menard, P.; Munyana, C.; Parsons, Ab; Ryan, O.; Tonikian, R.; Roberts, T.; Sdicu, Am; Shapiro, J.; Sheikh, B.; Suter, B.; Wong, Sl; Zhang, Lv; Zhu, H.; Burd, Cg; Munro, S.; Sander, C.; Rine, J.; Greenblatt, J.; Peter, M.; Bretscher, A.; Bell, G.; Roth, Fp; Brown, Gw; Andrews, B.; Bussey, H.; Boone, C., Global mapping of the yeast genetic interaction network, Science, 303, 5659, 808-813 (2004)
[35] Van Noort, V.; Snel, B.; Huynen, Ma, The yeast coexpression network has a small-world, scale-free architecture and can be explained by a simple model, EMBO Rep, 5, 3, 280-284 (2004)
[36] Wuchty, S., Small worlds in RNA structures, Nucl Acids Res, 31, 3, 1108-1117 (2003)
[37] Zipf, Gk, Human behavior and the principle of least effort (1949), Boston: Addison Wesley, Boston
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.