Small-world networks and RNA secondary structures

Abstract : Let $S_n$ denote the network of all RNA secondary structures of length $n$, in which undirected edges exist between structures $s$, $t$ such that $t$ is obtained from $s$ by the addition, removal or shift of a single base pair. Using context-free grammars, generating functions and complex analysis, we show that the asymptotic average degree is $O(n)$ and that the asymptotic clustering coefficient is $O(1/n)$, from which it follows that the family $S_n$, $n = 1, 2, 3,\ldots$ of secondary structure networks is not small-world.
Document type :
Journal articles
Complete list of metadatas

Cited literature [22 references]  Display  Hide  Download

https://hal.inria.fr/hal-01424452
Contributor : Yann Ponty <>
Submitted on : Tuesday, September 11, 2018 - 3:25:51 PM
Last modification on : Friday, October 4, 2019 - 1:52:35 AM
Long-term archiving on : Wednesday, December 12, 2018 - 3:36:10 PM

File

main2018.pdf
Files produced by the author(s)

Licence


Distributed under a Creative Commons Attribution 4.0 International License

Identifiers

Citation

Defne Surujon, Yann Ponty, Peter Clote. Small-world networks and RNA secondary structures. Journal of computational biology : a journal of computational molecular cell biology, Mary Ann Liebert 2019, 26 (1), pp.16--26. ⟨10.1089/cmb.2018.0125⟩. ⟨hal-01424452v2⟩

Share

Metrics

Record views

526

Files downloads

545