Small-world networks and RNA secondary structures

Defne Surujon 1 Yann Ponty 2, 3, 4 Peter Clote 1, *
* Corresponding author
4 AMIB - Algorithms and Models for Integrative Biology
LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau], LRI - Laboratoire de Recherche en Informatique, UP11 - Université Paris-Sud - Paris 11, Inria Saclay - Ile de France
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 : Saturday, April 27, 2019 - 11:09:57 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

507

Files downloads

388