Skip to Main content Skip to Navigation
Preprints, Working Papers, ...

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 :
Preprints, Working Papers, ...
Complete list of metadatas
Contributor : Yann Ponty <>
Submitted on : Monday, January 2, 2017 - 12:45:27 PM
Last modification on : Wednesday, September 16, 2020 - 5:11:59 PM
Long-term archiving on: : Tuesday, April 4, 2017 - 12:34:29 AM


Files produced by the author(s)


Distributed under a Creative Commons Attribution 4.0 International License


  • HAL Id : hal-01424452, version 1



Defne Surujon, Yann Ponty, Peter Clote. Small-world networks and RNA secondary structures. 2017. ⟨hal-01424452v1⟩



Record views


Files downloads